Dans Clojure, quand dois-je utiliser un vecteur sur une liste et inversement?

147

J'ai lu que les vecteurs ne sont pas des seqs, mais que les listes le sont. Je ne sais pas quelle est la justification de l'utilisation de l'un sur l'autre. Il semble que les vecteurs soient les plus utilisés, mais y a-t-il une raison à cela?

Rayne
la source
1
Related stackoverflow.com/questions/6928327/…
Duncan McGregor

Réponses:

112

Encore une fois, il semble que j'ai répondu à ma propre question en m'impatientant et en la posant dans #clojure sur Freenode. Nous vous encourageons à répondre à vos propres questions sur Stackoverflow.com: D

J'ai eu une brève discussion avec Rich Hickey, et en 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
Rayne
la source
Pendant que vous êtes sur freenode, venez du côté obscur et rejoignez #stackoverflow! :-P
Chris Jester-Young
J'avais l'habitude de rester inactif là-bas. J'ai changé de client IRC et je n'ai jamais pensé ajouter #stackoverflow à ma liste d'autojoin.
Rayne
Je suis un débutant en Lisp, mais je me suis demandé si les vecteurs, les cartes et les ensembles rompaient en quelque sorte l'idée que tout le code est interchangeable avec les données? Ou est-ce juste une de ces choses qui fait de Clojure un Lisp pratique? (OU, pouvez-vous évaluer un vecteur?)
Rob Grant
23
Cet extrait de chat est totalement inutile. "Générer du code" "générer de l'arrière vers l'avant" -> signifie précisément ?? J'ai vraiment du mal avec cette question car dans mon livre paresse + style déclaratif = bien meilleure performance, et pourtant des vecteurs sont suggérés partout dans Clojure ce qui me laisse totalement confus.
Jimmy Hoffa
22
@JimmyHoffa La façon dont je le comprends: "Generating Code" = "Inside a Macro" (car la plupart du code sont des appels de fonction, donc des listes); "generate back to front" = "construction d'une séquence en ajoutant".
omiel
87

Si vous avez beaucoup fait de la programmation Java et que vous êtes familier avec le framework de collecte Java, pensez à des listes comme LinkedListet à des vecteurs comme ArrayList. Vous pouvez donc à peu près choisir les conteneurs de la même manière.

Pour plus de précision: si vous avez l'intention d'ajouter beaucoup d'éléments individuellement au début 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. Cependant, si vous souhaitez accéder fréquemment à des éléments spécifiques (pas près de l'avant ou de l'arrière de la liste) (c.-à-d. Accès aléatoire), vous voudrez utiliser vector.

À propos, 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)
Chris Jester-Young
la source
Les vecteurs ne sont pas des séquences, mais ils sont séquentiels. (source: Rich lui-même sur #clojure sur freenode.) De plus, je ne connais pas vraiment Java du tout, mais Rich vient de répondre à ma question.
Rayne
1
Je vais éditer mon message pour dire, les vecteurs peuvent être transformés en seq, via la fonction seq. :-)
Chris Jester-Young
2
Choisissez votre réponse parce qu'elle a effectivement répondu à la question, et je n'aime vraiment pas choisir mes propres réponses comme correctes. Ça ne semble pas juste. Merci. :)
Rayne
Un deque vaut mieux qu'une liste chaînée dans le cas de l'ajout du premier et du dernier. Les LL sont assez terribles: P
boxed
1
@boxed Vous ne pouvez pas implémenter un deque sur un vecteur ou ArrayListsans, effectivement, ArrayDequevous réimplémenter .
Chris Jester-Young
43

Les vecteurs ont des temps d'accès aléatoire 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).

Svante
la source
3
Techniquement, les listes chaînées ont des temps d'accès O (1) ... si vous accédez uniquement à l'élément avant ou arrière. :-P Cependant, les vecteurs ont un accès aléatoire O (1). :-)
Chris Jester-Young
4
("Liste liée" comme décrit ci-dessus se réfère à des listes à double lien. Les listes à lien unique ont un accès O (1) à l'élément avant uniquement. :-P)
Chris Jester-Young
1
En tant que plongeur dans Clojure, c'est une réponse bien meilleure que les deux autres avec plus de votes. Les deux autres ne me disent rien d'utile.
keithjgrant
La liste @ ChrisJester-Young Single-linked peut prendre en charge l'accès O (1) à l'arrière si elle stocke une référence à l'élément arrière, comme ça .
Gill Bates
30

Quand utiliser un vecteur:

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

Quand utiliser une liste:

  • Lorsque vous souhaitez y accéder sous forme de séquence (puisque les listes prennent directement en charge seq sans avoir à allouer de nouveaux objets)
  • Prepending - ajouter au début d'une liste avec contre ou de préférence conj est O (1)
Mikera
la source
3
Même en ajoutant / supprimant aux deux extrémités une liste est un choix assez terrible. Un deque est bien meilleur (en CPU et surtout en mémoire). Essayez github.com/pjstadig/deque-clojure
boîte
2
Re: the ~O(1), pour ceux à qui cette explication des coûts pourrait être utile - stackoverflow.com/questions/200384/constant-amortized-time
Merlyn Morgan-Graham
13

juste un petit mot:

"J'ai lu que les vecteurs ne sont pas des séquences, mais les listes le sont." 

les séquences sont plus génériques que les listes ou les vecteurs (ou les cartes ou les ensembles).
Il est malheureux que le REPL imprime les listes et les séquences de la même manière, car cela donne vraiment l'impression que les listes sont des séquences même si elles sont différentes. la fonction (seq) créera une séquence à partir d'un grand nombre de choses différentes, y compris des listes, et vous pourrez ensuite alimenter cette seq à l'une des pléthore de fonctions qui font des choses intéressantes avec des seqs.

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 a un raccourci qui retourne 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, bien que d'autres choses le soient également, et toutes les séquences ne sont pas des listes.

Arthur Ulfeldt
la source
Je ne veux pas choisir un petit point, c'est juste une occasion de souligner quelque chose d'utile. beaucoup le savent déjà :)
Arthur Ulfeldt
2
Tu ne veux pas dire classau lieu de class??
qerub
Je ne sais pas si votre exemple a changé suite aux mises à jour de clojure (je pense que je suis sur 1.5), mais vos deux exemples clojure.lang.PersistentListme reviennent . Je suppose que vous vouliez écrire classpas class?.
Adrian Mouat
Je l'ai fait! Je vais réparer ça
Arthur Ulfeldt
Encore un peu confus; puisque classrenvoie la même PersistentList pour les deux expressions que vous avez mentionnées, cela implique que les séquences et les listes sont en effet exactement la même chose?
johnbakers