Les Objets JavaScript Hachages? C'est la complexité plus grande que O(1)?

Pour certains algorithme que j'écrivais récemment, j'ai pensé qu'un hash serait excellent. J'ai pensé que je pourrais probablement juste utiliser les variables dans un objet sous forme de paires clé-valeur. Je ne sais pas si c'est optimal puisque je ne sais pas vraiment ce qui se passe derrière les coulisses. Je suppose que la V8 est-il différent de celui des autres environnements. Je n'ai toutefois imaginer que la recherche de variables de membre serait assez rapide (je l'espère)?

Que tout est dit, je me demande si le temps d'exécution de la complexité de l'écriture, la lecture, la création et la suppression des variables de membre dans les objets JavaScript sont tous O(1). Si il y a des différences dans l'environnement (v8 vs d'autres) que sont-ils?

  • Si vous voulez la recherche de votre objet par un certain domaine, pourquoi s'en faire à propos de l'ajout et de la suppression? L'ID n'est pas censé changer après l'instanciation de l'objet.
  • Je suppose que l'ajout et la suppression n'est pas aussi grande affaire. Je ne vois pas de cas d'utilisation pour plus de quelques millions de paires, et même qui est le plus susceptible de ridicule pour ce cas d'utilisation en particulier. Puis de nouveau, les gens peuvent vouloir utiliser cette fonction pour d'autres choses. Je voudrais donner quelques indications.
  • "utiliser les variables dans un objet en tant que paires clé-valeur" - C'est à peu près ce que les membres de "variables" sont, n'est-ce pas?
  • eh bien, je n'ai pas forcément vu de garanties apportées sur les performances. Ils sont des paires clé-valeur, mais vous pouvez dire que sur n'importe quelle variable dans n'importe quelle langue.
  • "Ils sont des paires clé-valeur, mais vous pouvez dire que sur n'importe quelle variable dans n'importe quelle langue" - Non, vous ne pouvez pas: dans la plupart des langues chaînes de caractères, les nombres et les booléens sont des valeurs sans les touches associées. Mon point était qu'un JS objet de la mission est de maintenir une collection de paires clé/valeur (où la valeur peut être une référence à une fonction ou d'un autre objet). Je constate que ce n'est pas vous aider avec votre question à propos de la performance.
InformationsquelleAutor Parris | 2012-09-03
  1. 58

    Oui, ils sont les tables de hachage. La mise en œuvre est différente dans les navigateurs. Malgré de nombreux articles qui prétendent que les objets ne sont pas des hachages de très bien se comporter comme de la cendre, et par conséquent peut être utilisé en tant que tel.

    J'ai eu à le prouver par l'exécution de tests de performance:

    La façon de lire ces tests est que si il n'y a pas de différence de performances de l'ops/sec lorsque la taille de l'objet augmente, alors cela signifie que les objets sont les tables de hachage. La définition des caractéristiques d'une table de hachage est que la complexité de chaque opération est de O(1), indépendamment du fait qu'il soit plus rapide ou plus lent en comparaison à d'autres opérations.

    Tests:

    http://jsperf.com/objectsashashes/2 (100 clés)

    http://jsperf.com/objectsashashes/3 (100k touches)

    http://jsperf.com/objectsashashes/ (1 million de touches)

    http://jsperf.com/objects-as-hashes-300-mil (10m touches)

    Remarque: Chaque navigateur est plus rapide/lent à différentes opérations. Cela semble avoir changé entre les versions et d'une année à l'autre.

    • Il peut ne pas affecter vos statistiques, mais dans la destruction de la fonction, n est pas défini. Vous avez spécifié un mondial, mais jsPerf a enveloppé le code dans une fonction. Donc la fonction (si on l'appelle) est de lancer une erreur qui semble être ignoré par jsPerf.
    • merci pour cette capture. J'en ai fait une mise à jour sur: jsperf.com/objects-as-hashes-100k/2 Il n'a pas semblé affecter la performance que beaucoup. En fait, il était légèrement plus rapide dans tous les ops. Temps Constant changement. Je pense que je vais le laisser pour l'instant. Bien que, je dois certainement résoudre ce problème.
    • Donc le résumé est qu'il EST temps constant pour toutes les opérations CRUD ?
    • OUI! voir ci-dessous la réponse de Matt Balle. Je ne sais pas pourquoi cette réponse est celle d'en haut, il n'est pas réellement à la viande de la question.
    • au moment de ce post a été créé il n'y a aucune garantie que cela a été le cas. En fait, tous les articles qui existaient il a dit "les objets ne sont pas des hachages de cesser de les traiter comme ils sont". Pour prouver que c'était le cas, j'ai couru quelques tests de perf. Il a montré qu'il était bien vrai que tout était de la constante de temps. Il n'y a pas de spécification qui dit que ce doit être vrai (au moins aucun de ceux que j'ai pu trouver à l'époque). Les objets sont des objets pas de dictionnaire, il se trouve que la mise en commun en JS, c'est qu'ils sont les tables de hachage.
    • Plus j'ai mis à jour afin de la rendre plus utile. En effet, il était trop verbeux.
    • Bon point - vous avez prouvé que les objets CRUD constante de temps qui nous avait aucune garantie de auparavant. Ce qui signifie, nous DEVRIONS être en mesure de les traiter comme de la cendre, droit? allant à l'encontre de ce que les articles de l'époque
    • yup, vous devriez être en mesure de les traiter comme des tables de hachage. Je pense qu'ils ont utilisé de cette façon, très largement. Alors que je suis incertain si il y a un cahier des charges autour de lui je pense qu'il serait fou de régression si différents JS implémentations modifié ce comportement. Il pourrait être le moteur le plus lent JS mise en œuvre. L'essentiel, dans la pratique, oui, c'est une table de hachage, et il devrait toujours être une table de hachage.

    InformationsquelleAutor Parris
  2. 10

    Des objets JavaScript sont les tables de hachage. Je ne peut imaginer sane mise en œuvre qui ne serait pas fournir constante de temps des opérations CRUD sur les propriétés de l'objet.

    Voyez-vous des problèmes de performances spécifiques à cette approche?

    • Pas de problèmes de performances encore. Je vais courir un plus grand test bientôt, et comme @David mentionné dans les commentaires, je vais en faire une référence. Je suppose que cette question était juste de la curiosité. Je fais l'hypothèse que, puisqu'elle fonctionne comme une table de hachage que c'est une table de hachage. N'était pas totalement sûr. Aussi, je ne suis pas certaine si il y a une limite supérieure sur le nombre de variables de membre que vous pourriez éventuellement avoir.
    • Par le casier principe, il y a une durée limite supérieure sur le nombre de variables de membre, vous pouvez avoir avant de dégrader les performances (par exemple, en raison de collisions de hachage). Toutefois, sauf si vous êtes délibérément la cueillette pathologiquement mauvais clés de l'objet, et à l'aide d'un grand nombre d'entre eux, vous êtes tout simplement pas aller voir cette dégradation.
    • Je peux imaginer les implémentations ne sont pas nécessairement représenter des objets Javascript, comme les tables de hashage - JScript.NET utilisée, par exemple, du CLR typesystem, ce qui signifie que chaque domaine a été consulté par un offset de mémoire plutôt que d'une table de hachage de recherche, sans doute par objet de modifications ont été faites en utilisant la réflexion ou au moins une réaffectation des.
    • Merci! Je vais accepter cette réponse (au moins pour l'instant, à moins que quelqu'un a plus de détails). Je crois que @David est en droit de penser qu'une analyse de la performance. Je vais commenter revenir si j'ai des découvertes intéressantes dans les environnements.
    • N'oubliez pas de poster vos résultats dans cette question - personnellement, je suis intéressé par vos résultats!
    • les objets sont de simples paires nom/valeur, le terme de "hachage" peut ainsi en déduire beaucoup plus de fonctionnalités à certains. Peut-être des objets javascript sont mises en œuvre tant que les hachages dessous, qui sait? David commentaire est juste de le tester et de voir. Il se peut que différents aspects ont des performances différentes dans les différents navigateurs. Test doit inclure un hasOwnProperty filtre trop si cela est pertinent pour l'OP.
    • J'ai posté mes résultats de l'analyse!!! Merci encore!
    • Il faut être prudent avec une instruction comme "des objets JavaScript sont hachages". Ils ne sont pas d'une table de hachage connu de nombreux autres langages de programmation (par exemple, dict en python). Dans le cas où les clés sont à venir à partir de douteuses en entrée, il faut vraiment donner devthought.com/2012/01/18/an-object-is-not-a-hash à lire.
    • Merci... Cette réponse est infiniment plus utile que la réponse sommet. Sur le plan conceptuel, quand je pense à des tables de hachage je pense que la constante de temps de recherches et d'inserts, même si je sais qu'il ya plus à l'histoire. Tout ce que je besoin de savoir était de savoir si ces serait effectivement temps constant. Cette réponse répond que, contrairement à la réponse sommet. @Jan-PhilipGehrcke Ils ne sont pas les hachages techniquement, mais ils peuvent toujours fonctionner efficacement comme un seul, car ils fournissent constamment des opérations CRUD.

    InformationsquelleAutor Matt Ball