Si vous imaginez que vous avez un tableau associatif en JavaScript en tant que tel: Que se passe-t-il lorsque vous récupérez une valeur comme celle-ci: P> for (var color in hashTable) {
if (hashTable.hasOwnProperty(color)) {
//look for matching key
}
}
3 Réponses :
JavaScript n'a pas vraiment "des tableaux associatifs". La performance ne sera donc pas tout à fait comme celle d'une table de hachage, car les propriétés peuvent être héritées de leurs objets prototypes et la recherche d'une propriété donnée par nom peut nécessiter une traversée dans l'arborescence des prototypes avant de se trouver.
Ce blog post peut également fournir une idée:
http: //www.devthouxement .COM / 2012/01/18 / an-objet-is-pas-a-hash /
{} renvoie un objet JavaScript
NIT: La matrice associative est un autre nom pour une carte (à ne pas être confondu avec n'importe quel PHP). Un objet JavaScript est une carte avec des clés de cordes - dont implémentations utilise généralement une forme de hachage pour un accès attendu O (1).
Droite, mais mon point est qu'il peut y avoir (essentiellement) plusieurs cartes / objets associatifs / objets qui doivent être traversés si vous envisagez la chaîne prototype, de sorte que la performance peut être différente de celle-ci, une seule carte / objet / autre.
En supposant que la mise en œuvre est O (1) recherche (choisissez-en quelque chose, cela n'a pas d'importance), puis la recherche de C (une liaison finie dans n'importe quel cas pratique) est toujours O (1) complexité. Bien que, il serait intéressant de voir ce que les moteurs modernes d'optimisation de la mise en œuvre s'appliquent .. (c'est-à-dire des liens à la réponse de Trevor). Plus intéressant, je pense que cependant, sont des cas que ne peut pas ou ne sera pas optimisé .
Il est implémenté différemment dans différents moteurs JavaScript et de nos jours, semble-t-il, des objets ne sont pas soutenus par des structures de données "de type dictionnaire".
de https://developers.google.com/v8/design :
JavaScript est un langage de programmation dynamique: les propriétés peuvent être ajoutées et supprimées de, des objets à la volée. Cela signifie que les propriétés d'un objet sont susceptibles de changer. La plupart des moteurs JavaScript utilisent une structure de données de type dictionnaire comme stockage des propriétés d'objet - chaque accès de propriété nécessite une recherche dynamique pour résoudre l'emplacement de la propriété en mémoire. Cette approche permet d'accéder aux propriétés de JavaScript généralement beaucoup plus lentement que d'accéder à des variables d'instance dans des langages de programmation tels que Java et SmallTalk. Dans ces langues, les variables d'instance sont situées à des compensations fixes déterminées par le compilateur en raison de la disposition d'objet fixe définie par la classe de l'objet. L'accès est simplement une question de charge de mémoire ou de magasin, nécessitant souvent une seule instruction.
Pour réduire le temps nécessaire pour accéder aux propriétés JavaScript, V8 n'utilise pas de recherche dynamique pour accéder aux propriétés. Au lieu de cela, V8 crée de manière dynamique des cours cachés dans les coulisses. Cette idée de base n'est pas nouvelle - le langage de programmation de prototypes de la langue de programmation automatique des cartes pour faire quelque chose de similaire. En V8, un objet change sa classe cachée lorsqu'une nouvelle propriété est ajoutée.
L'ionMonkey de Firefox fait quelque chose de similaire. D'une interview avec un développeur à Mozilla ( http://www.infoq.com/news / 2011/05 / ionmonkey ):
Les langues dynamiques n'ont probablement pas d'avantages d'optimisation inhérentes, mais ils ont des optimisations intéressantes que les langues statiques ne le font pas. Par exemple, lorsque vous écrivez JavaScript, les objets apparaissent à l'utilisateur sous forme de tables de hachage, cartographier les noms de propriété aux valeurs. S'ils étaient effectivement mis en œuvre comme ça, ils seraient lents et utilisent beaucoup de mémoire.
Un bon moteur est capable d'obtenir des objets de groupe interne qui ressemblent à la même chose, en quelque sorte extraire une classe de type Java interne. Le JIT peut alors traiter l'objet comme ayant un type réel, générant un code super rapide qui évite une recherche de propriété coûteuse.
NIT: Le dernier paragraphe devrait être lu comme suit: "V8 n'est pas [ TOUJOURS ] Utiliser une recherche dynamique." Il y a des cas où cela ne peut pas exécuter cette optimisation - de manière triviale, lorsqu'il existe de manière triviale lorsqu'il existe des propriétés d'expansion.
Belles liens et extraits. Je me demande quand ces optimisations ne peuvent pas être appliquées et ce qui est fait dans ces cas ..
Le terme Array associatif décrit son utilisation: c'est un conteneur de valeur de clé utilisée pour associer une chose à une autre. Mais le terme Table de hachage décrit sa mise en œuvre: il utilise la fonction de hachage pour localiser des éléments dans la matrice sous-jacente. Il pourrait y avoir Array associatif dans une implémentation utilise une arborescence noire rouge ou une autre structure de données mais pas la table de hachage.
À mesure que la recherche est certainement une zone de performance clé, vous pouvez parier que tout moteur JavaScript moderne va le faire extrêmement efficacement.
C'est dépendant de la mise en œuvre, mais la recherche linéaire serait le moyen le plus stupide de le faire. Il existe de nombreuses stratégies efficaces pour faire des tables de recherche, les tables de hachage ne sont qu'un. Les arbres B sont une autre possibilité.
Ceci est une zone de performance clés comme indiqué par Pointy. Notez simplement que vous n'avez pas de "tableau associatif", mais plutôt d'un objet simple que vous réglez et d'obtenir des valeurs de propriété à partir de la notation du tableau.
Lorsque je veux savoir sur la performance, je construis des tests simples et prenons des mesures. Qu'est-ce qui vous empêche de faire ça?
Vous pouvez penser à l'objet JavaScript comme table de hachage ...
@Paddy Je suis actuellement intéressé par des détails sur sa mise en œuvre, ce n'est pas quelque chose que les points de repère peuvent me dire.