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 add
opé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 4
est immuable, je dois créer une nouvelle copie de 4
, mais remplacer son next
champ par un nouveau nœud contenant un 5
. Le problème est maintenant, 3
fait référence à l'ancien 4
; celui sans l'annexe 5
. Maintenant, je dois copier 3
et remplacer son next
champ pour référencer la 4
copie, mais fait maintenant 2
ré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.
la source
CopyOnWritexxx
classes 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)Réponses:
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:
La prépension d'un
1
vous donne:Mais notez que peu importe si quelqu'un d'autre détient toujours une référence à
2
la 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'il1
existe même si vous n'avez qu'une référence à2
. Maintenant, si vous ajoutez un5
sur 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.la source
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
next
pointeur de l'avant-dernier nœud (maintenant), qui dans un paramètre immuable crée un nouveau nœud, puis nous devons définir lenext
pointeur de l'avant-dernier nœud, etc.Je pense que le problème principal ici n'est pas l'immuabilité, ni l'
append
opé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):
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.List
et 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
map
oufold
(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
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.
la source
List
c'é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.java.util.List
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'
cons
opé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
StringBuilder
pour construire une chaîne et, à la fin, obtenez le résultat sous la formeString
(immuable!) En appelanttoString
. Une différence est que aStringBuilder
est 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
DList
classe immuable qui fournit une interface similaire à celle de HaskellData.DList
.la source
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é:
la source
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é.la source
Une approche qui peut parfois être utile consisterait à avoir deux classes d'objets contenant une liste - un objet de liste directe avec une
final
référence au premier nœud dans une liste liée vers l'avant et une non-final
ré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 unefinal
ré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
final
référence et de créer un nouvel objet de liste du même type que l'original, avec unefinal
ré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 unefinal
ré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
volatile
variables 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.la source