En Clojure, quand dois-je utiliser un vecteur plutôt qu'une liste, et inversement ?

Question

J'ai lu que les vecteurs ne sont pas des séquences, mais que les listes le sont. Je ne suis pas sûr de savoir pourquoi on utilise l'un plutôt que l'autre. Il semble que les vecteurs soient les plus utilisés, mais y a-t-il une raison à cela ?

Answer 1

Une fois de plus, il semble que j'ai répondu à ma propre question en m'impatientant et en la posant dans #clojure sur Freenode. Heureusement que répondre à ses propres questions est encouragé sur Stackoverflow.com :D

J'ai eu une brève discussion avec Rich Hickey, dont voici l'essentiel.

[12:21] <Raynes>    Vectors aren't seqs, right?
[12:21] <rhickey>   Raynes: no, but they are sequential
[12:21] <rhickey>   ,(sequential? [1 2 3])
[12:21] <clojurebot>    true
[12:22] <Raynes>    When would you want to use a list over a vector?
[12:22] <rhickey>   when generating code, when generating back-to-front
[12:23] <rhickey>   not too often in Clojure

Answer 2

Si vous avez beaucoup programmé en Java et que vous êtes familier avec le cadre de collection Java, vous pensez à des listes telles que LinkedList et des vecteurs tels que ArrayList . Vous pouvez donc à peu près choisir les conteneurs de la même manière.

Pour plus de clarté : si vous avez l'intention d'ajouter souvent des éléments individuellement à l'avant ou à l'arrière de la séquence, une liste chaînée est bien meilleure qu'un vecteur, car les éléments n'ont pas besoin d'être mélangés à chaque fois. En revanche, si vous souhaitez accéder fréquemment à des éléments spécifiques (qui ne se trouvent pas à l'avant ou à l'arrière de la liste) (accès aléatoire), vous devez utiliser un vecteur.

Par ailleurs, les vecteurs peuvent facilement être transformés en séquences.

user=> (def v (vector 1 2 3))
#'user/v
user=> v
[1 2 3]
user=> (seq v)
(1 2 3)
user=> (rseq v)
(3 2 1)

Answer 3

Les vecteurs ont des temps d'accès aléatoires O(1), mais ils doivent être pré-alloués. Les listes peuvent être étendues dynamiquement, mais l'accès à un élément aléatoire est O(n).

Answer 4

Quand utiliser un vecteur ?

• Performance de l'accès indexé - Vous obtenez un coût ~O(1) pour l'accès indexé contre O(n) pour les listes.
• L'ajout de - avec conj est ~O(1)
• Notation pratique - Je trouve qu'il est plus facile de taper et de lire [1 2 3] que '(1 2 3) pour une liste littérale dans des circonstances où l'une ou l'autre fonctionnerait.

Quand utiliser une liste :

• Lorsque vous voulez y accéder en tant que séquence (puisque les listes supportent directement seq sans avoir à allouer de nouveaux objets)
• Prepending - ajouter au début d'une liste avec des cons ou de préférence des conj est O(1)

Answer 5

Juste une petite note en passant :

"I read that Vectors are not seqs, but Lists are." 

les séquences sont plus génériques que les listes ou les vecteurs (ou les cartes ou les ensembles).
Il est regrettable que la REPL imprime les listes et les séquences de la même manière La fonction (seq ) crée une séquence à partir d'un grand nombre de choses différentes, y compris des listes, et vous pouvez ensuite transmettre cette séquence à une pléthore de fonctions qui font des choses intéressantes avec les séquences.

user> (class (list 1 2 3))
clojure.lang.PersistentList

user> (class (seq (list 1 2 3)))
clojure.lang.PersistentList

user> (class (seq [1 2 3]))
clojure.lang.PersistentVector$ChunkedSeq

Sec dispose d'un raccourci qui renvoie son argument s'il s'agit déjà d'un seq :

user> (let [alist (list 1 2 3)] (identical? alist (seq alist)))
true
user> (identical? (list 1 2 3) (seq (list 1 2 3)))
false

static public ISeq seq(Object coll){
        if(coll instanceof ASeq)
                return (ASeq) coll;
        else if(coll instanceof LazySeq)
                return ((LazySeq) coll).seq();
        else
                return seqFrom(coll);
}

les listes sont des séquences, mais d'autres choses le sont également, et toutes les séquences ne sont pas des listes.