No Clojure, quando devo usar um vetor sobre uma lista e o contrário?

147

Eu li que vetores não são seqs, mas listas são. Não sei ao certo qual é a razão para usar um sobre o outro. Parece que os vetores são mais utilizados, mas existe uma razão para isso?

Rayne
fonte
1
Relacionados stackoverflow.com/questions/6928327/...
Duncan McGregor

Respostas:

112

Mais uma vez, parece que respondi à minha própria pergunta, ficando impaciente e fazendo-a no #clojure no Freenode. É bom responder a suas próprias perguntas no Stackoverflow.com: D

Tive uma rápida discussão com Rich Hickey, e aqui está a essência disso.

[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
fonte
Enquanto você estiver no freenode, venha para o lado sombrio e participe do #stackoverflow! :-P
Chris Jester-Young
Na verdade, eu costumava ficar ocioso lá. Troquei clientes de IRC e nunca pensei em adicionar #stackoverflow à minha lista de ingresso automático.
21909 Rayne
Sou novato no Lisp, mas me perguntei se vetores, mapas e conjuntos quebram de alguma forma a idéia de que todo código é intercambiável com dados? Ou isso é apenas uma daquelas coisas que faz Clojure um Lisp prático? (OR, você pode avaliar um vetor?)
Rob Grant
23
Este é um trecho de bate-papo completamente inútil. "Gerando código" "gerando back-to-front" -> significa precisamente? Estou realmente tendo dificuldades com essa pergunta porque, no meu livro, preguiça + estilo declarativo = desempenho muito melhor, e ainda os vetores são sugeridos em todo o Clojure, o que me deixa totalmente confuso.
Jimmy Hoffa
22
@JimmyHoffa Do jeito que eu entendo: "Gerando código" = "Dentro de uma macro" (porque a maior parte do código é chamada de função, portanto, lista); "gerando de trás para a frente" = "construindo uma sequência anexando".
Omiel
87

Se você já fez muita programação em Java e está familiarizado com a estrutura de coleta Java, pense em listas como LinkedListe vetores como ArrayList. Assim, você pode escolher contêineres da mesma maneira.

Para esclarecimentos adicionais: se você deseja adicionar itens individualmente à frente ou atrás da sequência, uma lista vinculada é muito melhor que um vetor, porque os itens não precisam ser embaralhados a cada vez. No entanto, se você deseja obter elementos específicos (não próximos à frente ou atrás da lista) com frequência (ou seja, acesso aleatório), convém usar o vetor.

A propósito, os vetores podem ser facilmente transformados em seqs.

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
fonte
Vetores não são seqs, mas são seqüenciais. (fonte: Rich-se em #clojure on freenode.) Além disso, eu realmente não conheço Java, mas Rich acabou de responder à minha pergunta.
21411 Rayne
1
Vou editar meu post para dizer que os vetores podem ser transformados em seqs, através da função seq. :-) #
31420 Chris Jester-Young
2
Escolha sua resposta porque ela realmente respondeu à pergunta, e eu realmente não gosto de escolher minhas próprias respostas como corretas. Não parece certo. Obrigado. :)
Rayne
Um deque é melhor que uma lista vinculada no caso de adicionar o primeiro e o último. LLs são terríveis: P
encaixotado
1
@boxed Você não pode implementar um deque em cima de um vetor ou ArrayListsem, efetivamente, ArrayDequese reimplementar .
Chris Jester-Young
43

Os vetores têm tempos de acesso aleatório O (1), mas precisam ser pré-alocados. As listas podem ser estendidas dinamicamente, mas o acesso a um elemento aleatório é O (n).

Svante
fonte
3
Tecnicamente, as listas vinculadas têm tempos de acesso O (1) ... se você estiver acessando apenas o elemento frontal ou traseiro. :-P No entanto, os vetores têm acesso aleatório O (1). :-)
Chris Jester-Young
4
( "Lista Linked", como descrito acima referem-se a listas duplamente ligadas listas Singly ligados tem O (1) o acesso ao elemento frontal única :-P..)
Chris Jester-Young
1
Como alguém que acabou de mergulhar em Clojure, esta é uma resposta MUITO melhor do que as outras duas com mais votos. Os outros dois não me dizem nada de útil.
21814 Keithjgrant
@ ChrisJester-Young A lista vinculada a um único pode suportar acesso O (1) à parte traseira se ela armazenar uma referência ao elemento back, assim .
Gill Bates
30

Quando usar um vetor:

  • Desempenho de acesso indexado - você obtém um custo ~ O (1) para acesso indexado vs. O (n) para listas
  • Anexando - com conj é ~ O (1)
  • Notação conveniente - acho mais fácil digitar e ler [1 2 3] do que '(1 2 3) para obter uma lista literal nas circunstâncias em que qualquer uma delas funcionaria.

Quando usar uma lista:

  • Quando você deseja acessá-lo como uma sequência (uma vez que as listas suportam diretamente a seq sem precisar alocar novos objetos)
  • Anexar - adicionar ao início de uma lista com contras ou, de preferência, conj é O (1)
Mikera
fonte
3
Mesmo ao adicionar / remover nas duas extremidades, uma lista é uma escolha bastante terrível. Um deque é muito melhor (na CPU e principalmente na memória). Tente github.com/pjstadig/deque-clojure
caixa
2
Re: o ~O(1), para aqueles a quem esta explicação custo pode ser útil - stackoverflow.com/questions/200384/constant-amortized-time
Merlyn Morgan-Graham
13

apenas uma observação rápida:

"Eu li que Vetores não são seqs, mas Listas são." 

seqüências são mais genéricas do que listas ou vetores (ou mapas ou conjuntos).
É lamentável que o REPL imprima listas e sequências da mesma forma, porque realmente faz parecer que as listas são sequências, embora sejam diferentes. a função (seq) fará uma sequência de várias coisas diferentes, incluindo listas, e você pode alimentar essa seq com qualquer uma das inúmeras funções que fazem coisas bacanas com as 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 possui um atalho que retorna seu argumento se já é um 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);
}

listas são sequências, embora outras coisas também sejam, e nem todas as sequências são listas.

Arthur Ulfeldt
fonte
Eu não pretendo escolher um pequeno ponto, é apenas uma oportunidade de apontar algo útil. muitos já vai saber que isso :)
Arthur Ulfeldt
2
Você não quer dizer em classvez de class??
qerub
Não tenho certeza se o seu exemplo mudou após as atualizações de clojure (acho que estou no 1.5), mas os dois exemplos retornam clojure.lang.PersistentListpara mim. Estou assumindo que você pretendia escrever classnão class?.
Adrian Mouat
Eu fiz mesmo! Eu vou consertar isso
Arthur Ulfeldt
Ainda um pouco confuso; Como classretorna o mesmo PersistentList para ambas as expressões mencionadas, isso implica que sequências e listas são exatamente a mesma coisa?
johnbakers