Existe-t-il un moyen pratique pour qu'une structure de nœuds liés soit immuable?

26

J'ai décidé d'écrire une liste à liaison unique et j'avais le plan pour rendre la structure de nœud liée interne immuable.

Je suis tombé sur un hic cependant. Disons que j'ai les nœuds liés suivants (des addopérations précédentes ):

1 -> 2 -> 3 -> 4

et dire que je veux ajouter un 5.

Pour ce faire, étant donné que le nœud 4est immuable, je dois créer une nouvelle copie de 4, mais remplacer son nextchamp par un nouveau nœud contenant un 5. Le problème est maintenant, 3fait référence à l'ancien 4; celui sans l'annexe 5. Maintenant, je dois copier 3et remplacer son nextchamp pour référencer la 4copie, mais fait maintenant 2référence à l'ancien 3...

Ou en d'autres termes, pour faire un ajout, la liste entière semble avoir besoin d'être copiée.

Mes questions:

  • Ma pensée est-elle correcte? Existe-t-il un moyen de faire un ajout sans copier toute la structure?

  • Apparemment, "Java efficace" contient la recommandation:

    Les classes doivent être immuables à moins qu'il n'y ait une très bonne raison de les rendre mutables ...

    Est-ce un bon cas de mutabilité?

Je ne pense pas que ce soit un double de la réponse suggérée car je ne parle pas de la liste elle-même; cela doit évidemment être modifiable pour se conformer à l'interface (sans faire quelque chose comme garder la nouvelle liste en interne et la récupérer via un getter. Je veux savoir si les éléments internes de la liste doivent être immuables.

Carcigenicate
la source
Je dirais que oui - les rares collections immuables en Java sont soit celles avec des méthodes de mutation surchargées de lancer, soit les CopyOnWritexxxclasses incroyablement coûteuses utilisées pour le multi-threading. Personne ne s'attend vraiment à ce que les collections soient immuables (bien que cela crée des bizarreries)
Ordous
9
(Commentez la citation.) Cela, une grande citation, est souvent très mal compris. L'immutabilité doit être appliquée à ValueObject en raison de ses avantages , mais si vous développez en Java, il n'est pas pratique d'utiliser l'immuabilité dans les endroits où la mutabilité est anticipée. La plupart du temps, une classe a certains aspects qui devraient être immuables et certains aspects qui doivent être modifiables en fonction des exigences.
rwong
2
liés (éventuellement un doublon): l' objet de collection est-il préférable d'être immuable? "Sans frais généraux de performances, cette collection (classe LinkedList) peut-elle être introduite en tant que collection immuable?"
moucher
Pourquoi voudriez-vous faire une liste chaînée immuable? Le plus grand avantage d'une liste chaînée est la mutabilité, ne seriez-vous pas mieux avec un tableau?
Pieter B
3
Pourriez-vous s'il vous plaît m'aider à comprendre vos besoins? Vous voulez avoir une liste immuable, que vous souhaitez muter? N'est-ce pas une contradiction? Que voulez-vous dire par "les internes" de la liste? Voulez-vous dire que les nœuds précédemment ajoutés ne devraient pas être modifiables ultérieurement, mais autoriser uniquement l'ajout au dernier nœud de la liste?
null

Réponses:

46

Avec des listes en langages fonctionnels, vous travaillez presque toujours avec une tête et une queue, le premier élément et le reste de la liste. La prépension est beaucoup plus courante car, comme vous l'avez supposé, l'ajout nécessite la copie de la liste entière (ou d'autres structures de données paresseuses qui ne ressemblent pas précisément à une liste liée).

Dans les langages impératifs, l'ajout est beaucoup plus courant, car il a tendance à sembler plus naturel sémantiquement, et vous ne vous souciez pas d'invalider les références aux versions précédentes de la liste.

Comme exemple de pourquoi le préfixe ne nécessite pas de copier la liste entière, considérez que vous avez:

2 -> 3 -> 4

La prépension d'un 1vous donne:

1 -> 2 -> 3 -> 4

Mais notez que peu importe si quelqu'un d'autre détient toujours une référence à 2la tête de sa liste, car la liste est immuable et les liens ne vont que dans un sens. Il n'y a aucun moyen de dire qu'il 1existe même si vous n'avez qu'une référence à 2. Maintenant, si vous ajoutez un 5sur l' une ou l'autre liste, vous devrez faire une copie de la liste entière, car sinon elle apparaîtrait également sur l'autre liste.

Karl Bielefeldt
la source
Ahh, bon point sur pourquoi le préfixe ne nécessite pas de copie; Je n'y ai pas pensé.
Carcigenicate
17

Vous avez raison, l'ajout nécessite de copier toute la liste si vous ne souhaitez pas muter les nœuds en place. Car nous devons définir le nextpointeur de l'avant-dernier nœud (maintenant), qui dans un paramètre immuable crée un nouveau nœud, puis nous devons définir le nextpointeur de l'avant-dernier nœud, etc.

Je pense que le problème principal ici n'est pas l'immuabilité, ni l' appendopération mal avisée. Les deux sont parfaitement bien dans leurs domaines respectifs. Les mélanger est mauvais: l'interface naturelle (efficace) pour une liste immuable met l'accent sur la manipulation en tête de liste, mais pour les listes modifiables, il est souvent plus naturel de construire la liste en ajoutant successivement les éléments du premier au dernier.

Par conséquent, je vous suggère de vous décider: voulez-vous une interface éphémère ou persistante? La plupart des opérations produisent-elles une nouvelle liste et laissent une version non modifiée accessible (persistante), ou écrivez-vous du code comme ceci (éphémère):

list.append(x);
list.prepend(y);

Les deux choix sont bons, mais l'implémentation devrait refléter l'interface: une structure de données persistante bénéficie de nœuds immuables, tandis qu'un éphémère a besoin d'une mutabilité interne pour concrétiser les promesses de performances qu'il fait implicitement. java.util.Listet d'autres interfaces sont éphémères: les implémenter sur une liste immuable est inapproprié et en fait un risque de performance. Les bons algorithmes sur les structures de données mutables sont souvent très différents des bons algorithmes sur les structures de données immuables, donc habiller une structure de données immuable comme une structure mutable (ou vice versa) invite les mauvais algorithmes.

Bien qu'une liste persistante présente certains inconvénients (pas d'ajout efficace), cela ne doit pas être un problème grave lors de la programmation fonctionnelle: de nombreux algorithmes peuvent être formulés efficacement en modifiant l'état d'esprit et en utilisant des fonctions d'ordre supérieur telles que mapou fold(pour n'en nommer que deux relativement primitives). ), ou en ajoutant plusieurs fois. De plus, personne ne vous oblige à n'utiliser que cette structure de données: lorsque d'autres (éphémères ou persistantes mais plus sophistiquées) sont plus appropriées, utilisez-les. Je dois également noter que les listes persistantes présentent certains avantages pour d'autres charges de travail: elles partagent leurs queues, ce qui peut économiser de la mémoire.


la source
4

Si vous avez une liste liée individuellement, vous travaillerez avec le recto si elle est plus importante qu'avec le verso.

Les langages fonctionnels comme prolog et haskel fournissent des moyens faciles d'obtenir l'élément frontal et le reste du tableau. L'ajout à l'arrière est une opération O (n) avec copie de chaque nœud.

monstre à cliquet
la source
1
J'ai utilisé Haskell. Afaik, il contourne également une partie du problème en utilisant la paresse. Je fais des ajouts parce que je pensais que Listc'était ce à quoi s'attendait l' interface (je peux me tromper cependant). Je ne pense pas que ce morceau réponde vraiment à la question non plus. La liste entière devrait encore être copiée; cela rendrait simplement l'accès au dernier élément ajouté plus rapidement puisqu'un parcours complet ne serait pas requis.
Carcigenicate
La création d'une classe selon une interface qui ne correspond pas à la structure / algorithme de données sous-jacente est une invitation à la douleur et à l'inefficacité.
ratchet freak
Les JavaDocs utilisent explicitement le mot "ajouter". Vous dites qu'il vaut mieux ignorer cela pour la mise en œuvre?
Carcigenicate
2
@Carcigenicate non, je dis que c'est une erreur d'essayer d'ajuster une liste liée individuellement avec des nœuds immuables dans le moule dejava.util.List
ratchet freak
1
Avec la paresse, il n'y aurait plus de liste chaînée; il n'y a pas de liste, donc pas de mutation (annexe). Au lieu de cela, il existe du code qui génère l'élément suivant sur demande. Mais il ne peut pas être utilisé partout où une liste est utilisée. À savoir, si vous écrivez une méthode en Java qui s'attend à muter une liste transmise en argument, cette liste doit être mutable en premier lieu. L'approche générateur nécessite une restructuration complète (réorganisation) du code pour le faire fonctionner - et pour permettre de supprimer physiquement la liste.
rwong
4

Comme d'autres l'ont souligné, vous avez raison de dire qu'une liste immuable liée individuellement nécessite de copier la liste entière lors de l'exécution d'une opération d'ajout.

Souvent, vous pouvez utiliser la solution de contournement pour implémenter votre algorithme en termes d' consopérations (pré-ajout), puis inverser une fois la liste finale. Cela doit toujours copier la liste une fois, mais la surcharge de complexité est linéaire dans la longueur de la liste, alors qu'en utilisant à plusieurs reprises append, vous pouvez facilement obtenir une complexité quadratique.

Les listes de différences (voir par exemple ici ) sont une alternative intéressante. Une liste de différences enveloppe une liste et fournit une opération d'ajout en temps constant. Vous travaillez essentiellement avec l'encapsuleur aussi longtemps que vous devez ajouter, puis reconvertissez en liste lorsque vous avez terminé. Ceci est en quelque sorte similaire à ce que vous faites lorsque vous utilisez a StringBuilderpour construire une chaîne et, à la fin, obtenez le résultat sous la forme String(immuable!) En appelant toString. Une différence est que a StringBuilderest mutable, mais une liste de différences est immuable. De plus, lorsque vous reconvertissez une liste de différences en liste, vous devez toujours construire la nouvelle liste entière, mais, encore une fois, vous n'avez besoin de le faire qu'une seule fois.

Il devrait être assez facile d'implémenter une DListclasse immuable qui fournit une interface similaire à celle de Haskell Data.DList.

Giorgio
la source
4

Vous devez regarder cette superbe vidéo de 2015 React conf par le créateur d' Immutable.js Lee Byron. Il vous donnera des pointeurs et des structures pour comprendre comment mettre en œuvre une liste immuable efficace qui ne duplique pas le contenu. Les idées de base sont les suivantes: - tant que deux listes utilisent des nœuds identiques (même valeur, même nœud suivant), le même nœud est utilisé - lorsque les listes commencent à différer, une structure est créée au nœud de divergence, qui contient des pointeurs vers le nœud particulier suivant de chaque liste

Cette image d'un didacticiel React peut être plus claire que mon anglais cassé:entrez la description de l'image ici

feydaykyn
la source
2

Ce n'est pas strictement Java, mais je vous suggère de lire cet article sur une structure de données persistante indexée immuable, mais performante écrite en Scala:

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala

Comme il s'agit d'une structure de données Scala, elle peut également être utilisée à partir de Java (avec un peu plus de verbosité). Il est basé sur une structure de données disponible dans Clojure, et je suis sûr qu'il existe également une bibliothèque Java plus "native".

En outre, une note sur la construction de structures de données immuables: ce que vous voulez généralement, c'est une sorte de "Builder", qui vous permet de "muter" votre structure de données "en construction" en y ajoutant des éléments (dans un seul thread); une fois que vous avez terminé l'ajout, vous appelez une méthode sur l'objet "under-construction" telle que .build()or .result(), qui "construit" l'objet, vous donnant une structure de données immuable que vous pouvez ensuite partager en toute sécurité.

Sandro Gržičić
la source
1
Il y a une question sur les ports Java de PersistentVector à stackoverflow.com/questions/15997996/…
James_pic
1

Une approche qui peut parfois être utile consisterait à avoir deux classes d'objets contenant une liste - un objet de liste directe avec une finalréférence au premier nœud dans une liste liée vers l'avant et une non- finalréférence initialement nulle qui (lorsqu'elle n'est pas -null) identifie un objet de liste inversée contenant les mêmes éléments dans l'ordre opposé, et un objet de liste inversée avec une finalréférence au dernier élément d'une liste à liens inversés et une référence non finale initialement nulle qui (quand non -null) identifie un objet de liste avant contenant les mêmes éléments dans l'ordre opposé.

Pour ajouter un élément à une liste directe ou ajouter un élément à une liste inverse, il suffirait de créer un nouveau nœud lié au nœud identifié par la finalréférence et de créer un nouvel objet de liste du même type que l'original, avec une finalréférence à ce nouveau nœud.

Ajouter un élément à une liste directe ou ajouter une liste inversée nécessiterait d'avoir une liste du type opposé; la première fois que l'on fait avec une liste particulière, il doit créer un nouvel objet du type opposé et stocker une référence; la répétition de l'action devrait réutiliser la liste.

Notez que l'état externe d'un objet liste sera considéré comme le même si sa référence à une liste de type opposé est nulle ou identifie une liste d'ordre opposé. Il ne serait pas nécessaire de créer des variables final, même lors de l'utilisation de code multithread, car chaque objet de liste aurait une finalréférence à une copie complète de son contenu.

Si le code sur un thread crée et met en cache une copie inversée d'une liste et que le champ dans lequel cette copie est mise en cache n'est pas volatile, il est possible que le code sur un autre thread ne voit pas la liste en cache, mais le seul effet négatif à partir de là, l'autre thread aurait besoin de faire un travail supplémentaire pour construire une autre copie inversée de la liste. Étant donné qu'une telle action nuirait au pire à l'efficacité, mais n'affecterait pas l'exactitude, et parce que les volatilevariables créent leurs propres pertes d'efficacité, il est souvent préférable que la variable soit non volatile et accepte la possibilité d'opérations redondantes occasionnelles.

supercat
la source