Grand O de tableaux JavaScript

Tableaux en JavaScript sont très faciles à modifier par l'ajout et la suppression d'éléments. Elle a un peu masqué par le fait que la plupart des langues de la matrice sont de taille fixe, et nécessitent des opérations de redimensionnement. Il semble que JavaScript permet d'écrire facilement mal l'exécution de la matrice de code. Cela conduit à la question:

Quelles sont les performances (en termes de big O moment de la complexité) puis-je m'attendre à partir de JavaScript implémentations en ce qui concerne les performances de la baie?

Je suppose que toutes les implémentations de JavaScript ont au moins les éléments suivants big O.

  • Accès - O(1)
  • Ajoutant - O(n)
  • Ajoutant - O(n)
  • D'Insertion, en O(n)
  • Suppression - O(n)
  • Permutation - O(1)

JavaScript vous permet de pré-remplir un tableau à une certaine taille, à l'aide de new Array(length) de la syntaxe. (Question Bonus: Est la création d'un tableau de cette manière O(1) O(n)) C'est plus comme un réseau classique, et si elle est utilisée comme un pré-tableau de taille, peut permettre à O(1) en ajoutant. Si le tampon circulaire logique est ajouté, vous pouvez atteindre O(1) faire précéder. Si une extension dynamique de tableau est utilisé, O(log n) est la moyenne des cas pour les deux.

Puis-je espérer de meilleures performances pour certaines choses que mes suppositions? Je n'attends rien est indiqué dans les spécifications, mais dans la pratique, il se pourrait que toutes les grandes implémentations à l'utilisation optimisée des tableaux de derrière les coulisses. Existe-il une expansion dynamique de tableaux ou de quelque autre matière d'augmentation des performances des algorithmes au travail?

P. S.

La raison pour laquelle je me demande c'est parce que je suis à la recherche de quelques algorithmes de tri, dont la plupart semblent assumer l'ajout et la suppression sont en O(1) opérations lors de la description de l'ensemble de leurs big O.

  • Le constructeur Array avec une taille est à peu près inutile moderne implémentations de JavaScript. Il n'a presque rien dans ce seul paramètre de forme. (Il fixe .length mais c'est tout.) Les tableaux sont vraiment pas très différente de la plaine des instances de l'Objet.
  • Réglage de la length de la propriété et de pré-allouer l'espace sont deux choses complètement différentes.
  • Suis-je en attendre trop quand je m'attends à réglage array[5] sur un new Array(10) est O(1)?
  • Ce n'est probablement pas tout à fait en O(1), mais c'est comme l'ajout d'un élément à une table de hachage plus que c'est un tableau linéaire de ré-allocation.
  • Ouch. Vraiment? Il n'y a pas moyen de pré-dimensionner un tableau à tous?
  • Alors que l'ECMAScript ne définit pas comment faire un Tableau d'objet est mis en œuvre (il ne définit certaines règles sémantiques), il est très possible que les différentes implémentations d'optimiser pour les cas attendus (par exemple, avoir un "vrai tableau" support pour les tableaux de moins que certains n en taille). Je ne suis pas du tout calée sur les implémentations, mais serais vraiment surpris si cela n'a pas été fait quelque part ...
  • C'est le point de vue que j'ai eu.
  • réponse" est susceptible d'écrire quelques jsperf cas de test pour les différents n / modèles d'accès et de voir ce que ça 😉
  • Il serait étonnant de voir un tableau qui avait O(n) pour l'ajout et à la précéder.
  • réglage de la longueur de la propriété prealocate de l'espace. let a = []; a.length = 12 va créer un tableau de undefined x 12. Je ne vous méprenez-vous faire un commentaire ?
  • ce n'est pas nécessairement le cas que la définition de la length de la propriété sera en fait allouer l'espace de stockage. Essayez, par exemple, un programme de test qui initialise les tableaux 1 000 et définit la length propriété de chacun à 2000000000.

InformationsquelleAutor Kendall Frey | 2012-07-16
  1. 101

    Contrairement à la plupart des langues, qui mettent en œuvre des tableaux avec les, bien, tableaux, dans les Tableaux Javascript sont des objets, et les valeurs sont stockées dans une table de hachage, comme des valeurs de l'objet. En tant que tel:

    • Accès - O(1)
    • Ajoutant Amorti O(1) (parfois le redimensionnement de la table de hachage est requis; il est habituellement seulement d'insertion est requise)
    • Ajoutant - O(n) par l'intermédiaire de unshift, car il nécessite la réaffectation de tous les indices
    • Insertion Amorti O(1) si la valeur n'existe pas. O(n) si vous souhaitez modifier les valeurs existantes (par exemple, en utilisant splice).
    • Suppression Amorti O(1) pour supprimer une valeur, O(n) si vous voulez réaffecter les indices via splice.
    • Permutation - O(1)

    En général, le réglage ou la suppression de n'importe quelle touche dans un dict est amorti O(1), et il en va de même pour les tableaux, indépendamment de ce que l'indice est. Une opération qui requiert la renumérotation des valeurs existantes est O(n) tout simplement parce que vous devez mettre à jour tous les affectés de valeurs.

    • Ne pas ajouter en O(n)? Depuis, tous les indices doivent être déplacés. De même pour l'insertion et la suppression (à l'arbitraire de l'index, et décaler/réduire les éléments).
    • Aussi, est length situé sur le Tableau de mutation, ou est le get sur ce qu'il va obtenir la longueur et éventuellement memoize il?
    • Javascript n'a pas de 'ajouter', 'insert', ou 'supprimer' opérations de réaffecter des indices de tableau. Il dispose d'un "splice" l'opération qui fait que, et c'est (évidemment) O(n).
    • Pour length, voir ici.
    • Il ajoute: unshift. Je ne vois pas comment votre réponse n'a rien à voir avec la question.
    • Juste assez, j'ai raté unshift. Je ne sais pas pourquoi vous rencontrez des difficultés concernant ma réponse à la question: il semble assez simple pour moi.
    • Je l'ai mentionné dans mon premier commentaire: je ne comprends pas comment l'insertion et la suppression sont en O(1) amorti. Le seul genre de la "insertion" et "supprimer" qui peut avoir O(1) amorti complexité est d'attribuer de la valeur à l'ensemble.
    • J'ai mis à jour ma réponse avec plus de détails.
    • La peine de mentionner que cette réponse n'est plus correct. Les moteurs modernes ne pas stocker des Tableaux (ou des objets indexées entier clés) comme les tables de hashage (mais aime bien... les tableaux comme en C), sauf s'ils sont rares. Pour vous aider à démarrer ici est un "classique" de référence illustrant ceci
    • Autant que je sache, cela n'affecte pas la complexité ou de comportement, seul le facteur constant (ce qui est au-delà de la portée de la question).
    • Vous avez raison, cette réponse corrige des informations incorrectes qui est au-delà de la portée de la question. Je voulais juste le signaler - je n'ai pas downvote ou quoi que ce soit.
    • Pouvons-nous obtenir une référence à cela? J'aimerais en savoir plus sur la façon dont cela a été dérivée.
    • Les valeurs sont seulement ceux pour une table de hachage, que vous pouvez consulter big-O analyse sur Wikipédia ou ailleurs.
    • Est-ce définies par la norme, ou est-ce juste une mise en œuvre commune dans les moteurs JS? Ce V8?
    • il serait bien si vous pouviez développer un peu sur la façon dont ils sont stockés. Ou donner certaines sources.
    • Je suis toujours confus. Est new Array(100000) plus lent que new Array(10) ?
    • Est-il juste de dire cela signifie qu'il agit comme un efficace/pile FIFO (mais pas comme une file d'attente/FILO)?
    • alors, quelle est la réponse maintenant?
    • Ce n'est amorti signifie? Cela signifierait donc la suppression via .pop est O(1)?

    InformationsquelleAutor Nick Johnson