Pourquoi les ajoutant à une liste de mauvais?

Question

J'ai récemment commencé l'apprentissage de la scala, et je suis venu à travers l' :: (contre) la fonction qui ajoute à une liste.
Dans le livre "Programming in Scala", il précise qu'il n'y est pas d'ajouter une fonction car l'ajout à une liste de rendement o(n) alors que les préfixant a un rendement de o(1)

Quelque chose me frappe comme tort à propos de cette déclaration.

N'est-ce pas la performance dépend de la mise en œuvre? N'est-il pas possible de simplement mettre en œuvre la liste à la fois en avant et en arrière des liens et de stocker le premier et le dernier élément dans le conteneur?

La deuxième question je pense que c'est ce que je suis censé faire quand j'ai une liste, dire le 1,2,3 et je veux ajouter 4 à la fin de celui-ci?

Answer 1

L'essentiel est qu' x :: somelist ne pas muter somelist, mais au lieu de crée une nouvelle liste, qui contient x, suivie par tous les éléments de somelist. Cela peut être fait en O(1) temps parce que vous avez seulement besoin de définir somelist comme le successeur de x dans le nouvellement créé, unique liste liée.

Si le double des listes liées ont été utilisés au lieu de cela, x devra également être défini comme le prédécesseur de somelist de la tête, ce qui permettrait de modifier somelist. Donc, si nous voulons être en mesure de le faire : dans O(1) sans modifier la liste d'origine, nous ne pouvons utiliser les listes chaînées.

Concernant la seconde question: Vous pouvez utiliser ::: pour concaténer un seul élément de la liste à la fin de votre liste. C'est un O(n) opérations.

List(1,2,3) ::: List(4)

Answer 2

D'autres réponses ont donné de bonnes explications pour ce phénomène. Si vous ajoutez de nombreux éléments d'une liste dans un sous-programme, ou si vous créez une liste en ajoutant des éléments, une fonctionnelle idiome est de construire la liste dans l'ordre inverse, par contre avec les articles sur le devant de la liste, puis d'inverser à la fin. Cela vous donne O(n) la performance au lieu de O(n2).

Answer 3

Depuis que la question a été juste mis à jour, il est intéressant de noter que les choses ont changé ici.

Aujourd'hui Scala, vous pouvez simplement utiliser xs :+ x ajouter un élément à la fin de tout séquentielle de la collection. (Il est également x +: xs à ajouter. Le mnémonique pour beaucoup de Scala 2.8+ les opérations de collecte, c'est que le colpasse à côté de la collecte.)

Ce sera en O(n) avec la valeur par défaut lié la mise en œuvre de l' List ou Seq, mais si vous utilisez Vector ou IndexedSeq, ce sera effectivement constante de temps. Scala Vector est probablement Scala est le plus utile sous forme de liste de la collection à la différence de Java Vector qui est la plupart du temps inutile de nos jours.

Si vous travaillez dans Scala 2.8 ou plus, les collections de l'introduction est un absolu doit lire.

Answer 4

Les préfixant est plus rapide car elle ne nécessite que deux opérations:

1. Créer la nouvelle liste de nœud
2. Ont que le nouveau point de nœud à la liste existante

Ajoutant nécessite plus d'opérations parce que vous avez à parcourir à la fin de la liste puisque vous n'avez qu'un pointeur vers la tête.

Je n'ai jamais programmé en Scala avant, mais tu pourrais essayer une Liste de Tampon

Answer 5

La plupart des langages fonctionnels en évidence une figure liée individuellement structure de données de liste, car c'est une pratique immuable type de collection. Quand vous dites "la liste" dans un langage fonctionnel, c'est typiquement ce que tu veux dire (une liste liée individuellement, généralement immuable). Pour ce type, append est O(n) alors que le contre est O(1).