Dans quelles circonstances les listes chaînées sont-elles utiles?

110

La plupart du temps, je vois des gens essayer d'utiliser des listes chaînées, cela me semble être un mauvais (ou très mauvais) choix. Il serait peut-être utile d'explorer les circonstances dans lesquelles une liste chaînée est ou n'est pas un bon choix de structure de données.

Idéalement, les réponses expliqueraient les critères à utiliser pour sélectionner une structure de données et quelles structures de données sont susceptibles de fonctionner le mieux dans des circonstances spécifiques.

Edit: Je dois dire que je suis assez impressionné non seulement par le nombre, mais par la qualité des réponses. Je ne peux en accepter qu'un, mais il y en a deux ou trois de plus que j'aurais à dire qui auraient valu la peine d'être acceptés si quelque chose d'un peu mieux n'avait pas été là. Seul un couple (surtout celui que j'ai fini par accepter) a signalé des situations où une liste chaînée offrait un réel avantage. Je pense que Steve Jessop mérite une sorte de mention honorable pour avoir fourni non pas une, mais trois réponses différentes, que j'ai toutes trouvées assez impressionnantes. Bien sûr, même s'il n'a été publié que sous forme de commentaire, pas de réponse, je pense que l'article de blog de Neil vaut également la peine d'être lu - non seulement informatif, mais aussi très divertissant.

Jerry Coffin
la source
34
La réponse à votre deuxième paragraphe prend environ un semestre.
Seva Alekseyev
2
Pour mon avis, voir punchlet.wordpress.com/2009/12/27/letter-the-fourth . Et comme cela semble être une enquête, cela devrait probablement être CW.
1
@Neil, bien, même si je doute que CS Lewis l'approuverait.
Tom
@Neil: Je suppose qu'une sorte d'enquête. C'est surtout une tentative pour voir si quelqu'un peut trouver une réponse qui a une base que je pourrais au moins acheter comme étant raisonnable. @Seva: oui, en la relisant, j'ai rendu la dernière phrase un peu plus générale que je ne l'avais prévu à l'origine.
Jerry Coffin
2
@Yar People (y compris moi, je suis désolé de le dire) avait l'habitude d'implémenter des listes chaînées sans pointeurs dans des langages comme FORTRAN IV (qui n'avait aucune notion de pointeurs), tout comme ils le faisaient avec les arbres. Vous avez utilisé des tableaux au lieu de la "vraie" mémoire.

Réponses:

40

Ils peuvent être utiles pour les structures de données simultanées. (Il existe maintenant un exemple d'utilisation du monde réel non simultané ci-dessous - qui ne serait pas là si @Neil n'avait pas mentionné FORTRAN. ;-)

Par exemple, ConcurrentDictionary<TKey, TValue>dans .NET 4.0 RC, utilisez des listes liées pour chaîner les éléments hachés dans le même compartiment.

La structure de données sous-jacente pour ConcurrentStack<T>est également une liste chaînée.

ConcurrentStack<T>est l'une des structures de données qui servent de base au nouveau Thread Pool (avec les "files d'attente" locales implémentées sous forme de piles, essentiellement). (L'autre structure de support principale étant ConcurrentQueue<T>.)

Le nouveau pool de threads fournit à son tour la base de la planification du travail de la nouvelle bibliothèque parallèle de tâches .

Ils peuvent donc certainement être utiles - une liste chaînée sert actuellement de l'une des principales structures de soutien d'au moins une grande nouvelle technologie.

(Une liste à un seul lien fait un choix convaincant sans verrouillage - mais pas sans attente - dans ces cas, car les opérations principales peuvent être effectuées avec un seul CAS (+ tentatives). Dans un environnement GC-d moderne - tel que Java et .NET - le problème ABA peut facilement être évité. Enveloppez simplement les éléments que vous ajoutez dans des nœuds fraîchement créés et ne réutilisez pas ces nœuds - laissez le GC faire son travail. La page sur le problème ABA fournit également l'implémentation d'un verrou- Free stack - qui fonctionne réellement en .Net (& Java) avec un nœud (GC-ed) contenant les éléments.)

Edit : @Neil: en fait, ce que vous avez mentionné à propos de FORTRAN m'a rappelé que le même type de listes liées peut être trouvé dans la structure de données probablement la plus utilisée et la plus abusée de .NET: le générique .NET ordinaire Dictionary<TKey, TValue>.

Pas une, mais de nombreuses listes liées sont stockées dans un tableau.

  • Cela évite de faire de nombreuses petites (dé) allocations sur les insertions / suppressions.
  • Le chargement initial de la table de hachage est assez rapide, car le tableau est rempli séquentiellement (joue très bien avec le cache du processeur).
  • Sans oublier qu'une table de hachage de chaînage est chère en termes de mémoire - et cette "astuce" réduit de moitié les "tailles de pointeurs" sur x64.

Essentiellement, de nombreuses listes liées sont stockées dans un tableau. (un pour chaque compartiment utilisé.) Une liste gratuite de nœuds réutilisables est "entrelacée" entre eux (s'il y a eu des suppressions). Un tableau est alloué au début / à la reprise et les nœuds de chaînes y sont conservés. Il existe également un pointeur libre - un index dans le tableau - qui suit les suppressions. ;-) Alors - croyez-le ou non - la technique FORTRAN est toujours d'actualité. (... et nulle part ailleurs, que dans l'une des structures de données .NET les plus couramment utilisées ;-).

Andras Vass
la source
2
Au cas où vous auriez manqué, voici le commentaire de Neil: "Les gens (y compris moi, je suis désolé de le dire) avaient l'habitude d'implémenter des listes chaînées sans pointeurs dans des langages comme FORTRAN IV (qui n'avait aucune notion de pointeurs), tout comme ils le faisaient avec les arbres Vous avez utilisé des tableaux au lieu de la "vraie" mémoire. "
Andras Vass
Je devrais ajouter que l'approche «listes liées dans un tableau» en cas de Dictionarysauvegarde beaucoup plus dans .NET: sinon, chaque nœud nécessiterait un objet séparé sur le tas - et chaque objet alloué sur le tas aurait une surcharge. ( en.csharp-online.net/Common_Type_System%E2%80%94Object_Layout )
Andras Vass
Il est également bon de savoir que la valeur par défaut de C ++ std::listn'est pas sûre dans un contexte multithread sans verrous.
Mooing Duck
50

Les listes liées sont très utiles lorsque vous devez faire beaucoup d'insertions et de suppressions, mais pas trop de recherche, sur une liste de longueur arbitraire (inconnue à la compilation).

Le fractionnement et la jonction de listes (liées de manière bidirectionnelle) sont très efficaces.

Vous pouvez également combiner des listes liées - par exemple, les structures arborescentes peuvent être implémentées sous forme de listes liées "verticales" (relations parent / enfant) reliant ensemble des listes liées horizontales (frères et sœurs).

L'utilisation d'une liste basée sur un tableau à ces fins présente de graves limitations:

  • L'ajout d'un nouvel élément signifie que le tableau doit être réalloué (ou vous devez allouer plus d'espace que nécessaire pour permettre une croissance future et réduire le nombre de réaffectations)
  • La suppression d'articles laisse de l'espace perdu ou nécessite une réallocation
  • insérer des éléments n'importe où sauf la fin implique (éventuellement de réallouer et) de copier beaucoup de données d'une position vers le haut
Jason Williams
la source
5
La question se résume donc à: quand devez - vous faire beaucoup d'insertions et de suppressions au milieu d'une séquence, mais pas beaucoup de recherches dans la liste par ordinal? Traverser une liste liée est généralement aussi cher ou plus cher que la copie d'un tableau, donc tout ce que vous dites sur la suppression et l'insertion d'éléments dans des tableaux est tout aussi mauvais pour l'accès aléatoire dans les listes. Le cache LRU est un exemple auquel je peux penser, vous devez beaucoup supprimer au milieu, mais vous n'avez jamais besoin de parcourir la liste.
Steve Jessop
2
L'ajout à une liste implique une allocation de mémoire pour chaque élément que vous ajoutez. Cela peut impliquer un appel système qui sera très coûteux. L'ajout à un tableau ne nécessite un tel appel que si le tableau doit être développé. En fait, dans la plupart des langages (exactement pour ces raisons), le tableau est la structure de données préférée et les listes sont à peine utilisées.
1
Supposons lequel? Cette allocation est étonnamment rapide est évidente - nécessite généralement d'ajouter la taille de l'objet à un pointeur. Cette surcharge totale pour GC est faible? La dernière fois que j'ai essayé de le mesurer sur une vraie application, le point clé était que Java faisait tout le travail alors que le processeur était de toute façon inactif, donc naturellement cela n'affectait pas beaucoup les performances visibles. Dans un benchmark CPU chargé, il était facile de perturber Java et d'obtenir un temps d'allocation très mauvais. C'était il y a de nombreuses années, cependant, et le ramassage des ordures générationnel a considérablement réduit le coût total de GC depuis.
Steve Jessop
1
@Steve: Vous vous trompez sur le fait que l'allocation est "la même" entre les listes et les tableaux. Chaque fois que vous avez besoin d'allouer de la mémoire pour une liste, vous allouez simplement un petit bloc - O (1). Pour un tableau, vous devez allouer un nouveau bloc suffisamment grand pour toute la liste, puis copier la liste entière - O (n). Pour insérer dans un emplacement connu dans une liste, vous mettez à jour un nombre fixe de pointeurs - O (1), mais pour insérer dans un tableau et copier tous les éléments ultérieurs d'une position vers le haut pour faire de la place pour l'insertion - O (n). Il existe de nombreux cas où les tableaux sont donc beaucoup moins efficaces que les LL.
Jason Williams
1
@Jerry: Je comprends. Mon point est qu'une grande partie du coût de la réallocation du tableau n'alloue pas de mémoire , c'est la nécessité de copier tout le contenu du tableau dans la nouvelle mémoire. Pour insérer dans l'élément 0 d'un tableau, vous devez copier tout le contenu du tableau d'une position dans la mémoire. Je ne dis pas que les tableaux sont mauvais; juste qu'il y a des situations où l'accès aléatoire n'est pas nécessaire, et où l'insertion / suppression / reconnexion en temps réel des LL est préférable.
Jason Williams
20

Les listes liées sont très flexibles: avec la modification d'un pointeur, vous pouvez effectuer un changement massif, où la même opération serait très inefficace dans une liste de tableaux.

Chris Lercher
la source
Serait-il possible de motiver pourquoi utiliser une liste et non un ensemble ou une carte?
patrik
14

Les tableaux sont les structures de données auxquelles les listes liées sont généralement comparées.

Normalement, les listes liées sont utiles lorsque vous devez apporter beaucoup de modifications à la liste elle-même alors que les tableaux fonctionnent mieux que les listes sur l'accès direct aux éléments.

Voici une liste des opérations qui peuvent être effectuées sur les listes et les tableaux, par rapport au coût d'opération relatif (n = longueur de la liste / tableau):

  • Ajout d'un élément:
    • sur les listes, il vous suffit d'allouer de la mémoire pour le nouvel élément et de rediriger les pointeurs. O (1)
    • sur les tableaux, vous devez déplacer le tableau. Sur)
  • Supprimer un élément
    • sur les listes, vous ne faites que rediriger les pointeurs. O (1).
    • sur les tableaux, vous passez O (n) temps à déplacer le tableau si l'élément à supprimer n'est pas le premier ou le dernier élément du tableau; sinon vous pouvez simplement déplacer le pointeur vers le début du tableau ou diminuer la longueur du tableau
  • Obtenir un élément dans une position connue:
    • sur les listes, vous devez parcourir la liste du premier élément à l'élément dans la position spécifique. Pire cas: O (n)
    • sur les tableaux, vous pouvez accéder immédiatement à l'élément. O (1)

Il s'agit d'une comparaison de très bas niveau de ces deux structures de données populaires et de base et vous pouvez voir que les listes fonctionnent mieux dans les situations où vous devez apporter beaucoup de modifications à la liste elle-même (suppression ou ajout d'éléments). En revanche, les tableaux fonctionnent mieux que les listes lorsque vous devez accéder directement aux éléments du tableau.

Du point de vue de l'allocation de mémoire, les listes sont meilleures car il n'est pas nécessaire d'avoir tous les éléments les uns à côté des autres. D'un autre côté, il y a le (petit) surcoût de stockage des pointeurs vers l'élément suivant (ou même vers l'élément précédent).

Il est important que les développeurs connaissent ces différences pour choisir entre des listes et des tableaux dans leurs implémentations.

Notez qu'il s'agit d'une comparaison de listes et de tableaux. Il existe de bonnes solutions aux problèmes signalés ici (par exemple: SkipLists, Dynamic Arrays, etc ...). Dans cette réponse, j'ai pris en compte la structure de données de base que tout programmeur devrait connaître.

Andrea Zilio
la source
C'est un peu vrai pour une bonne implémentation des listes et une implémentation horrible des tableaux. La plupart des implémentations de tableaux sont beaucoup plus sophistiquées que ce que vous leur attribuez. Et je ne pense pas que vous compreniez à quel point l'allocation de mémoire dynamique peut être coûteuse.
Cette réponse n'est pas censée couvrir le programme d'un cours de Data Structures University. Il s'agit d'une comparaison écrite en tenant compte des listes et des tableaux liés, qui sont mis en œuvre de la manière dont vous, moi et la plupart des gens le savons. Les tableaux à expansion géométrique, les listes de sauts, etc. sont des solutions que je connais, que j'utilise et que j'étudie, mais qui nécessiteraient une explication plus approfondie et qui ne correspondrait pas à une réponse stackoverflow.
Andrea Zilio
1
"Du point de vue de l'allocation de mémoire, les listes sont meilleures car il n'est pas nécessaire d'avoir tous les éléments les uns à côté des autres." Au contraire, les conteneurs contigus sont préférables car ils maintiennent les éléments les uns à côté des autres. Sur les ordinateurs modernes, la localité des données est reine. Tout ce saut en mémoire tue les performances de votre cache, et conduit à des programmes qui insèrent un élément à un emplacement (effectivement) aléatoire, fonctionnant plus rapidement avec un tableau dynamique tel qu'un C ++ std::vectorqu'avec une liste liée telle qu'un C ++ std::list, simplement parce que traversant le la liste est si chère.
David Stone
@DavidStone Peut-être que je n'étais pas assez clair, mais avec cette phrase, je faisais référence au fait que vous n'avez pas besoin d'un espace contigu pour stocker vos éléments. Plus précisément, si vous souhaitez stocker quelque chose qui n'est pas trop petit et que vous avez une mémoire disponible limitée, vous n'aurez peut-être pas assez d'espace libre contigu pour stocker vos données, mais vous pouvez probablement ajuster vos données en utilisant une liste à la place (même si vous aurez la surcharge de pointeurs ... à la fois en raison de l'espace qu'ils occupent et des problèmes de performances que vous avez mentionnés). Je devrais probablement mettre à jour ma réponse pour la rendre plus claire.
Andrea Zilio
4

La liste à liaison unique est un bon choix pour la liste gratuite dans un allocateur de cellules ou un pool d'objets:

  1. Vous n'avez besoin que d'une pile, donc une liste à un seul lien suffit.
  2. Tout est déjà divisé en nœuds. Il n'y a pas de surcharge d'allocation pour un nœud de liste intrusif, à condition que les cellules soient suffisamment grandes pour contenir un pointeur.
  3. Un vecteur ou deque imposerait une surcharge d'un pointeur par bloc. Ceci est important étant donné que lorsque vous créez le tas pour la première fois, toutes les cellules sont gratuites, donc c'est un coût initial. Dans le pire des cas, il double le besoin de mémoire par cellule.
Steve Jessop
la source
Eh bien, d'accord. Mais combien de programmeurs créent réellement de telles choses? La plupart sont simplement en train de ré-implémenter ce que std :: list etc. vous donne. Et en fait, «intrusif» a normalement une signification légèrement différente de celle que vous lui avez donnée - que chaque élément de liste possible contient un pointeur séparé des données.
1
Combien? Plus de 0, moins d'un million ;-) La question de Jerry était-elle "donner de bons usages des listes", ou "donner de bons usages des listes que chaque programmeur utilise quotidiennement", ou quelque chose entre les deux? Je ne connais pas d'autre nom que «intrusif» pour un nœud de liste qui est contenu dans l'objet qui est un élément de liste - que ce soit dans le cadre d'une union (en termes C) ou non. Le point 3 ne s'applique que dans les langages qui vous permettent de le faire - C, C ++, bon assembleur. Java mauvais.
Steve Jessop
4

La liste doublement chaînée est un bon choix pour définir l'ordre d'un hashmap qui définit également un ordre sur les éléments (LinkedHashMap en Java), surtout lorsqu'il est ordonné par le dernier accès:

  1. Plus de surcharge mémoire qu'un vecteur ou deque associé (2 pointeurs au lieu de 1), mais de meilleures performances d'insertion / suppression.
  2. Pas de surcharge d'allocation, car vous avez de toute façon besoin d'un nœud pour une entrée de hachage.
  3. La localité de référence n'est pas un problème supplémentaire par rapport à un vecteur ou à un deque de pointeurs, car vous devrez tirer chaque objet en mémoire de toute façon.

Bien sûr, vous pouvez vous demander si un cache LRU est une bonne idée en premier lieu, par rapport à quelque chose de plus sophistiqué et réglable, mais si vous allez en avoir un, c'est une implémentation assez décente. Vous ne voulez pas effectuer une suppression du milieu et un ajout à la fin sur un vecteur ou deque à chaque accès en lecture, mais déplacer un nœud vers la queue est généralement bien.

Steve Jessop
la source
4

Les listes liées sont l'un des choix naturels lorsque vous ne pouvez pas contrôler où vos données sont stockées, mais que vous devez toujours passer d'un objet à l'autre.

Par exemple, lors de l'implémentation du suivi de la mémoire en C ++ (remplacement nouveau / suppression), vous avez besoin soit d'une structure de données de contrôle qui garde la trace des pointeurs qui ont été libérés, que vous devez entièrement implémenter vous-même. L'alternative consiste à surallouer et à ajouter une liste liée au début de chaque bloc de données.

Parce que vous savez toujours immédiatement où vous vous trouvez dans la liste lorsque la suppression est appelée, vous pouvez facilement abandonner la mémoire dans O (1). L'ajout d'un nouveau morceau qui vient d'être malaxé est également en O (1). Parcourir la liste est très rarement nécessaire dans ce cas, donc le coût O (n) n'est pas un problème ici (marcher une structure est de toute façon O (n)).

LiKao
la source
3

Ils sont utiles lorsque vous avez besoin d'une poussée, d'un pop et d'une rotation à grande vitesse, sans vous soucier de l'indexation O (n).

Ignacio Vazquez-Abrams
la source
Avez-vous déjà pris la peine de chronométrer les listes chaînées C ++ par rapport à (disons) un deque?
@Neil: Je ne peux pas dire que j'ai.
Ignacio Vazquez-Abrams
@Neil: si C ++ a délibérément saboté sa classe de liste chaînée afin de la rendre plus lente que tout autre conteneur (ce qui n'est pas loin de la vérité), qu'est-ce que cela a à voir avec une question indépendante du langage? Une liste liée intrusive est toujours une liste liée.
Steve Jessop
@Steve C ++ est un langage. Je ne vois pas comment cela peut avoir une volonté. Si vous suggérez que les membres du Comité C ++ ont saboté d'une manière ou d'une autre les listes chaînées (ce qui doit logiquement être lent pour de nombreuses opérations), alors nommez les coupables!
3
Ce n'est pas vraiment du sabotage - les nœuds de liste externes ont leurs avantages, mais les performances n'en font pas partie. Cependant, tout le monde était sûrement conscient au moment de faire le compromis entre la même chose dont vous êtes conscient, à savoir qu'il est assez difficile de trouver une bonne utilisation std::list. Une liste intrusive ne correspond tout simplement pas à la philosophie C ++ d'exigences minimales sur les éléments de conteneur.
Steve Jessop
3

Les listes à liaison unique sont l'implémentation évidente du type de données commun «liste» dans les langages de programmation fonctionnelle:

  1. L'ajout à la tête est rapide, et (append (list x) (L))et(append (list y) (L)) permet de partager presque toutes leurs données. Pas besoin de copier sur écriture dans une langue sans écriture. Les programmeurs fonctionnels savent comment en profiter.
  2. L'ajout à la queue est malheureusement lent, mais il en serait de même pour toute autre implémentation.

Par comparaison, un vecteur ou deque serait généralement lent à ajouter à l'une ou l'autre extrémité, nécessitant (au moins dans mon exemple de deux appendices distincts) qu'une copie soit prise de la liste entière (vecteur), ou du bloc d'index et du bloc de données étant ajouté à (deque). En fait, il y a peut-être quelque chose à dire là-bas à propos de grandes listes qui doivent être ajoutées à la fin pour une raison quelconque, je ne suis pas suffisamment informé sur la programmation fonctionnelle pour juger.

Steve Jessop
la source
3

Un exemple de bonne utilisation pour une liste chaînée est lorsque les éléments de la liste sont très volumineux. suffisamment grand pour qu'un ou deux seulement puissent tenir dans le cache du processeur en même temps. À ce stade, l'avantage des conteneurs de blocs contigus tels que les vecteurs ou les tableaux d'itération est plus ou moins annulé, et un avantage de performance peut être possible si de nombreuses insertions et suppressions se produisent en temps réel.

métamorphose
la source
2

D'après mon expérience, la mise en œuvre de matrices clairsemées et de tas de fibonacci. Les listes liées vous permettent de mieux contrôler la structure globale de ces structures de données. Bien que je ne sois pas sûr que les matrices clairsemées soient mieux implémentées à l'aide de listes liées - il existe probablement un meilleur moyen, mais cela a vraiment aidé à apprendre les tenants et les aboutissants des matrices clairsemées à l'aide de listes liées dans CS de premier cycle :)

zakishaheen
la source
1

Il y a deux opérations complémentaires qui sont trivialement O (1) sur les listes et très difficiles à implémenter en O (1) dans d'autres structures de données - supprimer et insérer un élément à partir d'une position arbitraire, en supposant que vous devez maintenir l'ordre des éléments.

Les cartes de hachage peuvent évidemment faire l'insertion et la suppression dans O (1), mais vous ne pouvez pas parcourir les éléments dans l'ordre.

Compte tenu du fait ci-dessus, la carte de hachage peut être combinée avec une liste liée pour créer un cache LRU astucieux: une carte qui stocke un nombre fixe de paires clé-valeur et supprime la clé la moins récemment accédée pour faire de la place pour de nouvelles.

Les entrées de la mappe de hachage doivent avoir des pointeurs vers les nœuds de la liste liée. Lors de l'accès à la carte de hachage, le nœud de la liste liée est dissocié de sa position actuelle et déplacé vers la tête de la liste (O (1), oui pour les listes liées!). Lorsqu'il est nécessaire de supprimer l'élément le moins récemment utilisé, celui de la queue de la liste doit être supprimé (encore une fois O (1) en supposant que vous gardez le pointeur vers le nœud de queue) avec l'entrée de la carte de hachage associée (donc les backlinks de la liste de la carte de hachage sont nécessaires.)

Rafał Dowgird
la source
1

Considérez qu'une liste chaînée peut être très utile dans une implémentation de style Domain Driven Design d'un système qui comprend des parties qui s'imbriquent avec la répétition.

Un exemple qui me vient à l'esprit pourrait être si vous deviez modéliser une chaîne suspendue. Si vous vouliez savoir quelle était la tension sur un lien particulier, votre interface pourrait inclure un getter pour le poids "apparent". La mise en œuvre de ce qui inclurait un lien demandant son prochain lien pour son poids apparent, puis ajoutant son propre poids au résultat. De cette façon, toute la longueur jusqu'en bas serait évaluée avec un seul appel du client de la chaîne.

Étant un partisan d'un code qui se lit comme un langage naturel, j'aime comment cela permettrait au programmeur de demander à un maillon de chaîne combien de poids il porte. Il garde également le souci de calculer ces enfants de propriétés dans les limites de l'implémentation du lien, supprimant ainsi le besoin d'un service de calcul de poids de chaîne ".

780Farva
la source
1

L'un des cas les plus utiles que je trouve pour les listes liées travaillant dans des domaines critiques pour les performances tels que le traitement de maillage et d'image, les moteurs physiques et le lancer de rayons est lorsque l'utilisation de listes liées améliore réellement la localité de référence et réduit les allocations de tas et parfois même réduit l'utilisation de la mémoire par rapport à les alternatives simples.

Maintenant, cela peut sembler être un oxymore complet que les listes liées pourraient faire tout cela car elles sont connues pour faire souvent le contraire, mais elles ont une propriété unique en ce que chaque nœud de liste a une taille et des exigences d'alignement fixes que nous pouvons exploiter pour permettre ils doivent être stockés de manière contiguë et supprimés en temps constant d'une manière que les choses de taille variable ne peuvent pas.

En conséquence, prenons un cas où nous voulons faire l'équivalent analogique de stocker une séquence de longueur variable qui contient un million de sous-séquences de longueur variable imbriquées. Un exemple concret est un maillage indexé stockant un million de polygones (certains triangles, certains quads, certains pentagones, certains hexagones, etc.) et parfois des polygones sont supprimés de n'importe où dans le maillage et parfois des polygones sont reconstruits pour insérer un sommet dans un polygone existant ou supprimer un. Dans ce cas, si nous stockons un million de minuscules std::vectors, nous nous retrouvons face à une allocation de tas pour chaque vecteur unique ainsi qu'à une utilisation de la mémoire potentiellement explosive. Un million de minuscules SmallVectorspeuvent ne pas souffrir autant de ce problème dans les cas courants, mais leur tampon préalloué qui n'est pas alloué séparément en tas peut toujours provoquer une utilisation explosive de la mémoire.

Le problème ici est qu'un million d' std::vectorinstances essaieraient de stocker un million de choses de longueur variable. Les objets de longueur variable ont tendance à vouloir une allocation de tas car ils ne peuvent pas très efficacement être stockés de manière contiguë et supprimés en temps constant (au moins de manière simple sans allocateur très complexe) s'ils ne stockent pas leur contenu ailleurs sur le tas.

Si, à la place, nous faisons ceci:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... alors nous avons considérablement réduit le nombre d'allocations de tas et d'erreurs de cache. Au lieu d'exiger une allocation de tas et des échecs de cache potentiellement obligatoires pour chaque polygone auquel nous accédons, nous n'exigeons désormais cette allocation de tas que lorsque l'un des deux vecteurs stockés dans le maillage entier dépasse leur capacité (un coût amorti). Et bien que la foulée pour passer d'un sommet à l'autre puisse toujours causer sa part de ratés dans le cache, c'est encore souvent moins que si chaque polygone stockait un tableau dynamique séparé car les nœuds sont stockés de manière contiguë et il y a une probabilité qu'un sommet voisin puisse accessible avant l'expulsion (d'autant plus que de nombreux polygones ajouteront leurs sommets en même temps, ce qui rend la part du lion des sommets de polygones parfaitement contigus).

Voici un autre exemple:

entrez la description de l'image ici

... où les cellules de la grille sont utilisées pour accélérer la collision particule-particule pour, par exemple, 16 millions de particules se déplaçant à chaque image. Dans cet exemple de grille de particules, en utilisant des listes liées, nous pouvons déplacer une particule d'une cellule de la grille à une autre en changeant simplement 3 indices. L'effacement d'un vecteur et le repoussement vers un autre peuvent être considérablement plus coûteux et introduire plus d'allocations de tas. Les listes chaînées réduisent également la mémoire d'une cellule à 32 bits. Un vecteur, selon l'implémentation, peut préallouer son tableau dynamique au point où il peut prendre 32 octets pour un vecteur vide. Si nous avons environ un million de cellules de grille, c'est toute une différence.

... et c'est là que je trouve les listes chaînées les plus utiles de nos jours, et je trouve spécifiquement la variété «liste chaînée indexée» utile puisque les indices 32 bits divisent par deux les besoins en mémoire des liens sur les machines 64 bits et ils impliquent que le les nœuds sont stockés de manière contiguë dans un tableau.

Souvent, je les combine également avec des listes gratuites indexées pour permettre des suppressions et des insertions à temps constant n'importe où:

entrez la description de l'image ici

Dans ce cas, l' nextindex pointe vers le prochain index libre si le nœud a été supprimé ou vers le prochain index utilisé si le nœud n'a pas été supprimé.

Et c'est le cas d'utilisation numéro un que je trouve pour les listes liées de nos jours. Lorsque nous voulons stocker, par exemple, un million de sous-séquences de longueur variable faisant en moyenne, par exemple, 4 éléments chacun (mais parfois avec des éléments supprimés et ajoutés à l'une de ces sous-séquences), la liste chaînée nous permet de stocker 4 millions nœuds de liste chaînée contigus au lieu de 1 million de conteneurs qui sont chacun alloués individuellement par tas: un vecteur géant, c'est-à-dire pas un million de petits.

DrunkCoder
la source
0

J'ai utilisé des listes liées (même des listes doublement liées) dans le passé dans une application C / C ++. C'était avant .NET et même stl.

Je n'utiliserais probablement pas de liste chaînée maintenant dans un langage .NET car tout le code de traversée dont vous avez besoin vous est fourni via les méthodes d'extension Linq.

ChrisF
la source