Quel type d'algorithme nécessite un ensemble?

Lors de mes premiers cours de programmation, on m'a dit que je devais utiliser un ensemble chaque fois que je devais faire des choses comme supprimer les doublons de quelque chose. Par exemple: pour supprimer tous les doublons d'un vecteur, parcourez ce vecteur et ajoutez chaque élément à un ensemble, vous vous retrouvez avec des occurrences uniques. Cependant, je pourrais aussi le faire en ajoutant chaque élémento à un autre vecteur et en vérifiant si l'élément existe déjà. Je suppose que selon la langue utilisée, il peut y avoir une différence de performances. Mais y a-t-il une raison d'utiliser un ensemble autre que celui-là?

Fondamentalement: quels types d'algorithmes nécessitent un ensemble et ne devraient pas être effectués avec un autre type de conteneur?

Vous posez des questions sur les ensembles en particulier, mais je pense que votre question concerne un concept plus large: l'abstraction. Vous avez absolument raison de pouvoir utiliser un vecteur pour ce faire (si vous utilisez Java, utilisez plutôt ArrayList.) Mais pourquoi s'arrêter là? Pourquoi avez-vous besoin du Vector? Vous pouvez tout faire avec des tableaux.

Chaque fois que vous devez ajouter un élément au tableau, vous pouvez simplement boucler sur chaque élément et s'il n'est pas là, vous l'ajoutez à la fin. Mais, en fait, vous devez d'abord vérifier s'il y a de la place dans le tableau. S'il n'y en a pas, vous devrez créer un nouveau tableau plus grand et copier tous les éléments existants de l'ancien tableau vers le nouveau tableau, puis vous pourrez ajouter le nouvel élément. Bien sûr, vous devez également mettre à jour chaque référence à l'ancien tableau pour pointer vers le nouveau. Vous avez tout fait? Génial! Maintenant, qu'essayons-nous d'accomplir à nouveau?

Ou, à la place, vous pouvez utiliser une instance Set et simplement appeler add(). La raison pour laquelle les ensembles existent est qu'ils sont une abstraction utile pour de nombreux problèmes courants. Par exemple, disons que vous souhaitez suivre les éléments et réagir lorsqu'un nouveau est ajouté. Vous appelez add()un ensemble et il revient trueou falseselon que l'ensemble a été modifié. Vous pouvez écrire tout cela à la main en utilisant des primitives, mais pourquoi?

Il peut y avoir un cas où vous avez une liste et que vous souhaitez supprimer les doublons. L'algorithme que vous proposez est à peu près la manière la plus lente de le faire. Il existe plusieurs méthodes plus rapides: les regrouper ou les trier. Vous pouvez également les ajouter à un ensemble qui implémente l'un de ces algorithmes.

Au début de votre carrière / éducation, l'accent est mis sur la construction de ces algorithmes et leur compréhension, et il est important de le faire. Mais ce n'est pas ce que les développeurs professionnels font normalement. Ils utilisent ces approches pour créer des choses beaucoup plus intéressantes et l'utilisation d'implémentations préconstruites et fiables permet d'économiser du temps.

Je suppose que selon la langue utilisée, il peut y avoir une différence de performances. Mais y a-t-il une raison d'utiliser un ensemble autre que celui-là?

Oh oui, (mais ce n'est pas une performance.)

Utilisez un ensemble lorsque vous pouvez en utiliser un car ne pas l'utiliser signifie que vous devez écrire du code supplémentaire. L'utilisation d'un ensemble facilite la lecture de ce que vous faites. Tout ce test de logique d'unicité est caché ailleurs où vous n'avez pas à y penser. C'est dans un endroit qui a déjà été testé et vous pouvez avoir confiance que cela fonctionne.

Écrivez votre propre code pour ce faire et vous devez vous en soucier. Bleh. Qui veut faire ça?

Fondamentalement: quels types d'algorithmes nécessitent un ensemble et ne devraient pas être effectués avec un autre type de conteneur?

Il n'y a pas d'algorithme qui "ne devrait pas être fait avec un autre type de conteneur". Il existe simplement des algorithmes qui peuvent tirer parti des ensembles. C'est bien quand vous n'avez pas à écrire de code supplémentaire.

Il n'y a rien de particulièrement spécial à cet égard. Vous devez toujours utiliser la collection qui correspond le mieux à vos besoins. En java, j'ai trouvé cette image utile pour prendre cette décision. Vous remarquerez qu'il a trois types d'ensembles différents.

Et comme @germi le fait remarquer à juste titre, si vous utilisez la bonne collection pour le travail, votre code devient plus facile à lire pour les autres.

Cependant, je pourrais aussi le faire en ajoutant chaque élémento à un autre vecteur et en vérifiant si l'élément existe déjà.

Si vous faites cela, vous implémentez la sémantique d'un ensemble au-dessus de la structure de données vectorielle. Vous écrivez du code supplémentaire (qui pourrait contenir des erreurs), et le résultat sera extrêmement lent si vous avez beaucoup d'entrées.

Pourquoi voudriez-vous faire cela en utilisant une implémentation d'ensemble existante, testée et efficace?

Les entités logicielles qui représentent des entités du monde réel sont souvent des ensembles logiques. Prenons par exemple une voiture. Les voitures ont des identifiants uniques et un groupe de voitures forme un ensemble. La notion d'ensemble sert de contrainte à la collection de voitures qu'un programme peut connaître et la limitation des valeurs des données est très précieuse.

De plus, les ensembles ont une algèbre très bien définie. Si vous avez un ensemble de voitures appartenant à George et un ensemble appartenant à Alice, alors le syndicat est clairement l'ensemble appartenant à George et Alice même si George et Alice possèdent tous les deux la même voiture. Les algorithmes qui devraient utiliser des ensembles sont donc ceux où la logique des entités impliquées présente des caractéristiques d'ensemble. Cela s'avère assez courant.

La manière dont les ensembles sont mis en œuvre et la garantie de la contrainte d'unicité sont une autre affaire. On espère pouvoir trouver une implémentation appropriée pour la logique d'ensemble qui élimine les doublons étant donné que les ensembles sont si fondamentaux pour la logique, mais même si vous effectuez l'implémentation vous-même, la garantie d'unicité est intrinsèque à l'insertion d'un élément dans un ensemble et vous ne devriez pas avoir à "vérifier si l'élément existe déjà".

Outre les caractéristiques de performance (qui sont très importantes et ne devraient pas être si facilement rejetées), les ensembles sont très importants en tant que collection abstraite.

Pourriez-vous émuler le comportement de Set (en ignorant les performances) avec un tableau? Oui absolument! Chaque fois que vous insérez, vous pouvez vérifier si l'élément est déjà dans le tableau, puis n'ajouter l'élément que s'il n'est pas déjà trouvé. Mais c'est quelque chose que vous devez consciemment être au courant, et n'oubliez pas chaque fois que vous insérez dans votre Array-Psuedo-Set. Oh qu'est-ce que c'est, vous avez inséré une fois directement, sans d'abord vérifier les doublons? Welp, votre tableau a rompu son invariant (que tous les éléments sont uniques, et de manière équivalente, qu'il n'y a pas de doublons).

Alors, que feriez-vous pour contourner cela? Vous devez créer un nouveau type de données, l'appeler (disons, PsuedoSet), qui enveloppe un tableau interne et expose insertpubliquement une opération, ce qui renforcera l'unicité des éléments. Étant donné que le tableau encapsulé est uniquement accessible via cette insertAPI publique , vous garantissez que les doublons ne peuvent jamais se produire. Ajoutez maintenant du hachage pour améliorer les performances des containsvérifications, et tôt ou tard vous vous rendrez compte que vous avez implémenté un full-out Set.

Je répondrais également par une déclaration et une question de suivi:

Lors de mes premiers cours de programmation, on m'a dit que je devais utiliser un tableau chaque fois que je devais faire des choses comme stocker plusieurs éléments ordonnés de quelque chose. Par exemple: pour stocker une collection de noms de collègues. Cependant, je pourrais également le faire en allouant de la mémoire brute et en définissant la valeur de l'adresse mémoire donnée par le pointeur de démarrage + un certain décalage.

Pourriez-vous utiliser un pointeur brut et des décalages fixes pour imiter un tableau? Oui absolument! Chaque fois que vous insérez, vous pouvez vérifier si le décalage ne s'écarte pas de la fin de la mémoire allouée avec laquelle vous travaillez. Mais c'est quelque chose que vous devez consciemment être conscient de, et rappelez-vous chaque fois que vous insérez dans votre Pseudo-Array. Oh qu'est-ce que c'est, vous avez inséré une fois directement, sans d'abord vérifier le décalage? Welp, il y a un défaut de segmentation avec votre nom dessus!

Alors, que feriez-vous pour contourner cela? Vous devez créer un nouveau type de données, l'appeler (disons PsuedoArray), qui encapsule un pointeur et une taille, et expose une insertopération publiquement, ce qui imposera que le décalage ne dépasse pas la taille. Étant donné que les données encapsulées sont uniquement accessibles via cette insertAPI publique , vous garantissez qu'aucun débordement de tampon ne peut se produire. Ajoutez maintenant quelques autres fonctions pratiques (redimensionnement de tableau, suppression d'élément, etc.), et tôt ou tard vous vous rendrez compte que vous avez implémenté un full-out Array.

Il existe toutes sortes d'algorithmes basés sur des ensembles, en particulier lorsque vous devez effectuer des intersections et des unions d'ensembles et que le résultat soit un ensemble.

Les algorithmes basés sur les ensembles sont largement utilisés dans divers algorithmes de recherche de chemin, etc.

Pour une introduction à la théorie des ensembles, consultez ce lien: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Si vous avez besoin d'une sémantique d'ensemble, utilisez un ensemble. Cela va éviter les bugs dus aux doublons parasites parce que vous avez oublié d'élaguer le vecteur / liste à un moment donné, et ça va être plus rapide que vous ne pouvez le faire en élaguant constamment votre vecteur / liste.

En fait, je trouve que les conteneurs d'ensemble standard sont pour la plupart inutiles moi-même et je préfère simplement utiliser des tableaux, mais je le fais d'une manière différente.

Pour calculer les intersections d'ensemble, j'itère le premier tableau et marque les éléments avec un seul bit. Ensuite, j'itère le deuxième tableau et cherche les éléments marqués. Voila, définissez l'intersection en temps linéaire avec beaucoup moins de travail et de mémoire qu'une table de hachage, par exemple les unions et les différences sont tout aussi simples à appliquer en utilisant cette méthode. Cela aide que ma base de code tourne autour de l'indexation des éléments plutôt que de leur duplication (je duplique les index en éléments, pas les données des éléments eux-mêmes) et a rarement besoin de quoi que ce soit à trier, mais je n'ai pas utilisé de structure de données définie depuis des années comme un résultat.

J'ai aussi du code C maléfique à manipuler, même lorsque les éléments n'offrent aucun champ de données à ces fins. Cela implique d'utiliser la mémoire des éléments eux-mêmes en définissant le bit le plus significatif (que je n'utilise jamais) dans le but de marquer les éléments traversés. C'est assez dégoûtant, ne faites pas cela à moins que vous ne travailliez vraiment au niveau du quasi-assemblage, mais je voulais juste mentionner comment cela peut être applicable même dans les cas où les éléments ne fournissent pas de champ spécifique pour la traversée si vous pouvez garantir que certains bits ne seront jamais utilisés. Il peut calculer une intersection définie entre 200 millions d'éléments (environ 2,4 Go de données) en moins d'une seconde sur mon dinky i7. Essayez de faire une intersection d'ensemble entre deux std::setinstances contenant chacune cent millions d'éléments en même temps; ne vient même pas de près.

Cela mis à part ...

Cependant, je pourrais aussi le faire en ajoutant chaque élémento à un autre vecteur et en vérifiant si l'élément existe déjà.

Cette vérification pour voir si un élément existe déjà dans le nouveau vecteur va généralement être une opération temporelle linéaire, ce qui fera que l'intersection de l'ensemble elle-même est une opération quadratique (une quantité de travail explosive plus la taille d'entrée est grande). Je recommande la technique ci-dessus si vous souhaitez simplement utiliser de vieux vecteurs ou tableaux simples et le faire d'une manière qui évolue à merveille.

Fondamentalement: quels types d'algorithmes nécessitent un ensemble et ne devraient pas être effectués avec un autre type de conteneur?

Aucune si vous me demandez mon avis biaisé si vous en parlez au niveau du conteneur (comme dans une structure de données spécifiquement implémentée pour fournir des opérations d'ensemble efficacement), mais il y en a beaucoup qui nécessitent une logique d'ensemble au niveau conceptuel. Par exemple, disons que vous voulez trouver les créatures dans un monde de jeu qui sont capables de voler et de nager, et que vous avez des créatures volantes dans un ensemble (que vous utilisiez ou non un conteneur d'ensemble) et celles qui peuvent nager dans un autre . Dans ce cas, vous voulez une intersection définie. Si vous voulez des créatures qui peuvent voler ou qui sont magiques, alors vous utilisez une union fixe. Bien sûr, vous n'avez pas réellement besoin d'un conteneur d'ensemble pour l'implémenter, et l'implémentation la plus optimale n'a généralement pas besoin ou ne veut pas d'un conteneur spécifiquement conçu pour être un ensemble.

Going Off Tangent

Très bien, j'ai reçu de belles questions de JimmyJames concernant cette approche d'intersection d'ensemble. C'est un peu dévier du sujet, mais bon, je suis intéressé à voir plus de gens utiliser cette approche intrusive de base pour définir l'intersection afin qu'ils ne construisent pas des structures auxiliaires entières comme des arbres binaires équilibrés et des tables de hachage uniquement dans le but de définir des opérations. Comme mentionné, l'exigence fondamentale est que les listes copient les éléments de manière superficielle de sorte qu'ils indexent ou pointent vers un élément partagé qui peut être "marqué" comme traversé par le passage à travers la première liste ou tableau non trié ou quoi que ce soit à ramasser ensuite sur le second passer par la deuxième liste.

Cependant, cela peut être accompli pratiquement même dans un contexte multithreading sans toucher aux éléments à condition que:

1. Les deux agrégats contiennent des indices des éléments.
2. La gamme des indices n'est pas trop large (disons [0, 2 ^ 26), pas des milliards ou plus) et est relativement densément occupée.

Cela nous permet d'utiliser un tableau parallèle (un seul bit par élément) aux fins des opérations d'ensemble. Diagramme:

La synchronisation des threads ne doit être présente que lors de l'acquisition d'un tableau de bits parallèles à partir du pool et de sa libération dans le pool (effectuée implicitement lorsque vous sortez de la portée). Les deux boucles réelles pour effectuer l'opération définie ne nécessitent aucune synchronisation de thread. Nous n'avons même pas besoin d'utiliser un pool de bits parallèle si le thread peut simplement allouer et libérer les bits localement, mais le pool de bits peut être pratique pour généraliser le modèle dans des bases de code qui correspondent à ce type de représentation de données où les éléments centraux sont souvent référencés par index afin que chaque thread n'ait pas à se soucier d'une gestion efficace de la mémoire. Les principaux exemples de ma zone sont les systèmes à composants d'entité et les représentations de mailles indexées. Les deux ont souvent besoin de définir des intersections et ont tendance à se référer à tout ce qui est stocké de manière centralisée (composants et entités dans ECS et sommets, arêtes,

Si les indices ne sont pas densément occupés et dispersés de manière clairsemée, cela est toujours applicable avec une implémentation raisonnable et clairsemée du tableau parallèle de bits / booléen, comme celui qui ne stocke la mémoire que dans des blocs de 512 bits (64 octets par nœud non déroulé représentant 512 indices contigus). ) et ignore l'allocation de blocs contigus complètement vacants. Il y a de fortes chances que vous utilisiez déjà quelque chose comme ça si vos structures de données centrales sont peu occupées par les éléments eux-mêmes.

... idée similaire pour un jeu de bits clairsemé servant de tableau de bits parallèle. Ces structures se prêtent également à l'immuabilité, car il est facile de copier des blocs volumineux superficiels qui n'ont pas besoin d'être copiés en profondeur pour créer une nouvelle copie immuable.

Encore une fois, des intersections définies entre des centaines de millions d'éléments peuvent être effectuées en moins d'une seconde en utilisant cette approche sur une machine très moyenne, et cela dans un seul thread.

Cela peut également être fait en moins de la moitié du temps si le client n'a pas besoin d'une liste d'éléments pour l'intersection résultante, comme s'il voulait seulement appliquer une logique aux éléments trouvés dans les deux listes, à quel point il peut simplement passer un pointeur de fonction ou un foncteur ou un délégué ou quoi que ce soit à rappeler pour traiter des plages d'éléments qui se croisent. Quelque chose à cet effet:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... ou quelque chose à cet effet. La partie la plus chère du pseudocode dans le premier diagramme est intersection.append(index)dans la deuxième boucle, et cela s'applique même pour std::vectorréservé à la taille de la liste plus petite à l'avance.

Et si je copie tout en profondeur?

Eh bien, arrête ça! Si vous devez définir des intersections, cela implique que vous dupliquez des données pour les intersecter. Il y a de fortes chances que même vos plus petits objets ne soient pas plus petits qu'un index 32 bits. Il est très possible de réduire la plage d'adressage de vos éléments à 2 ^ 32 (2 ^ 32 éléments, pas 2 ^ 32 octets) à moins que vous n'ayez réellement besoin de plus de ~ 4,3 milliards d'éléments instanciés, auquel cas une solution totalement différente est nécessaire ( et qui n'utilise certainement pas de conteneurs définis en mémoire).

Matchs clés

Que diriez-vous des cas où nous devons effectuer des opérations de définition où les éléments ne sont pas identiques mais pourraient avoir des clés correspondantes? Dans ce cas, même idée que ci-dessus. Nous avons juste besoin de mapper chaque clé unique à un index. Si la clé est une chaîne, par exemple, les chaînes internes peuvent faire exactement cela. Dans ces cas, une belle structure de données comme un trie ou une table de hachage est requise pour mapper les clés de chaîne aux index 32 bits, mais nous n'avons pas besoin de telles structures pour effectuer les opérations de définition sur les index 32 bits résultants.

De nombreuses solutions algorithmiques et structures de données très bon marché et simples s'ouvrent comme celles-ci lorsque nous pouvons travailler avec des indices d'éléments dans une plage très raisonnable, pas la plage d'adressage complète de la machine, et donc cela en vaut souvent la peine capable d'obtenir un index unique pour chaque clé unique.

J'adore les indices!

J'aime autant les indices que la pizza et la bière. Quand j'avais 20 ans, je me suis vraiment mis au C ++ et j'ai commencé à concevoir toutes sortes de structures de données entièrement conformes aux normes (y compris les astuces pour lever l'ambiguïté d'un ctor de remplissage d'un ctor de plage au moment de la compilation). Rétrospectivement, c'était une grande perte de temps.

Si vous faites tourner votre base de données autour du stockage central des éléments dans des tableaux et de leur indexation plutôt que de les stocker de manière fragmentée et potentiellement sur l'ensemble de la plage adressable de la machine, vous pouvez finir par explorer un monde de possibilités algorithmiques et de structure de données simplement en la conception de conteneurs et d'algorithmes qui tournent autour de simples vieux intou int32_t. Et j'ai trouvé que le résultat final était tellement plus efficace et facile à maintenir où je ne transférais pas constamment des éléments d'une structure de données à une autre à une autre.

Quelques exemples de cas d'utilisation où vous pouvez simplement supposer que toute valeur unique de Ta un index unique et aura des instances résidant dans un tableau central:

Triages radix multithread qui fonctionnent bien avec des entiers non signés pour les indices . J'ai en fait un tri Radix multithread qui prend environ 1 / 10e du temps pour trier une centaine de millions d'éléments en tant que tri parallèle d'Intel, et celui d'Intel est déjà 4 fois plus rapide que std::sortpour de si grandes entrées. Bien sûr, Intel est beaucoup plus flexible car il s'agit d'un tri basé sur la comparaison et peut trier les choses lexicographiquement, il compare donc les pommes aux oranges. Mais ici, je n'ai souvent besoin que d'oranges, comme je pourrais faire un tri radix juste pour obtenir des modèles d'accès à la mémoire compatibles avec le cache ou filtrer les doublons rapidement.

Possibilité de construire des structures liées comme des listes liées, des arbres, des graphiques, des tables de hachage de chaînage séparées, etc. sans allocations de tas par nœud . Nous pouvons simplement allouer les nœuds en vrac, parallèlement aux éléments, et les relier entre eux avec des indices. Les nœuds eux-mêmes deviennent simplement un index 32 bits du nœud suivant et stockés dans un grand tableau, comme ceci:

Convient au traitement parallèle. Souvent, les structures liées ne sont pas aussi conviviales pour le traitement parallèle, car il est à tout le moins gênant d'essayer de réaliser le parallélisme dans l'arborescence ou la traversée de liste liée, par opposition à, disons, simplement faire un parallèle pour une boucle à travers un tableau. Avec la représentation index / tableau central, nous pouvons toujours accéder à ce tableau central et tout traiter en boucles parallèles volumineuses. Nous avons toujours ce tableau central de tous les éléments que nous pouvons traiter de cette façon, même si nous ne voulons en traiter que certains (auquel cas vous pouvez traiter les éléments indexés par une liste triée par radix pour un accès compatible avec le cache via le tableau central).

Peut associer des données à chaque élément à la volée en temps constant . Comme dans le cas du tableau parallèle de bits ci-dessus, nous pouvons associer facilement et à très bon marché des données parallèles à des éléments pour, par exemple, un traitement temporaire. Cela a des cas d'utilisation au-delà des données temporaires. Par exemple, un système de maillage peut vouloir permettre aux utilisateurs d'attacher autant de cartes UV à un maillage qu'ils le souhaitent. Dans un tel cas, nous ne pouvons pas simplement coder en dur le nombre de cartes UV qu'il y aura dans chaque sommet et face en utilisant une approche AoS. Nous devons être en mesure d'associer de telles données à la volée, et les tableaux parallèles y sont pratiques et tellement moins chers que n'importe quel type de conteneur associatif sophistiqué, même des tables de hachage.

Bien sûr, les tableaux parallèles sont désapprouvés en raison de leur nature sujette aux erreurs de garder les tableaux parallèles synchronisés les uns avec les autres. Chaque fois que nous supprimons un élément à l'index 7 du tableau "racine", par exemple, nous devons également faire la même chose pour les "enfants". Cependant, il est assez facile dans la plupart des langues de généraliser ce concept à un conteneur à usage général afin que la logique délicate de garder les tableaux parallèles synchronisés les uns avec les autres ne doive exister qu'en un seul endroit dans toute la base de code, et un tel conteneur de tableaux parallèles peut utilisez l'implémentation de tableau fragmenté ci-dessus pour éviter de gaspiller beaucoup de mémoire pour les espaces vacants contigus dans le tableau à récupérer lors des insertions suivantes.

Plus d'élaboration: Sparse Bitset Tree

D'accord, j'ai reçu une demande pour en élaborer davantage, ce qui je pense était sarcastique, mais je vais le faire de toute façon parce que c'est tellement amusant! Si les gens veulent porter cette idée à de nouveaux niveaux, il est possible d'effectuer des intersections définies sans même boucler linéairement à travers les éléments N + M. Voici ma structure de données ultime que j'utilise depuis des âges et essentiellement des modèles set<int>:

La raison pour laquelle il peut effectuer des intersections d'ensemble sans même inspecter chaque élément dans les deux listes est parce qu'un seul bit d'ensemble à la racine de la hiérarchie peut indiquer que, disons, un million d'éléments contigus sont occupés dans l'ensemble. En inspectant simplement un bit, nous pouvons savoir que N indices dans la plage, [first,first+N)sont dans l'ensemble, où N pourrait être un très grand nombre.

J'utilise en fait cela comme un optimiseur de boucle lors de la traversée d'indices occupés, car disons qu'il y a 8 millions d'indices occupés dans l'ensemble. Eh bien, normalement, nous aurions à accéder à 8 millions d'entiers en mémoire dans ce cas. Avec celui-ci, il peut simplement inspecter quelques bits et proposer des plages d'index d'indices occupés à parcourir. De plus, les plages d'indices qui en découlent sont triées, ce qui permet un accès séquentiel très convivial par opposition à, par exemple, une itération à travers un tableau d'index non trié utilisé pour accéder aux données d'éléments d'origine. Bien sûr, cette technique est pire pour les cas extrêmement clairsemés, le pire des cas étant que chaque indice unique soit un nombre pair (ou que chacun soit impair), auquel cas il n'y a aucune région contiguë. Mais dans mes cas d'utilisation au moins,

Pour vérifier si un ensemble contenant n éléments contient un autre élément, X prend généralement un temps constant. Pour vérifier si un tableau contenant n éléments contient un autre élément, X prend généralement O (n) temps. C'est mauvais, mais si vous voulez supprimer les doublons de n éléments, cela prend du temps O (n) au lieu de O (n ^ 2); 100 000 articles mettront votre ordinateur à genoux.

Et vous demandez plus de raisons? "En dehors du tournage, avez-vous apprécié la soirée, Mme Lincoln?"