382 palavras

Listas VS Vetores em Clojure

, em Clojure, Listas, Vetores

Lista VS Vetores

Embora Listas e Vetores sejam muito semelhantes, sendo estruturas sequências ordenadas, por debaixo do capô elas são bem diferentes. Então porquê o Clojure mantêm implementações/estruturas similares?

rastro da via láctea Tirei essa foto do meu celular em Viçosa no Ceará durante minhas férias em Agosto de 2022.

Vetores

Não são só os colchetes que diferenciam os vetores das listas. Por baixo, um Vetor é uma árvore persistente em que cada nó guarda até 32 itens. Isso permite acessar qualquer posição pelo índice em tempo quase constante e adicionar itens no fim sem copiar o vetor inteiro.

Vetor do Clojure como árvore: um nó raiz aponta para nós-folha, e cada folha guarda até 32 itens, do 0 ao 31 na primeira e a partir do 32 na segunda raiz 01…31 3233…
Vetor: uma árvore rasa em que cada nó guarda até 32 itens. Achar um item pelo índice leva poucos passos.
(def vector-numbers [1 2 3 4])

(conj vector-numbers 5)
;; => [1 2 3 4 5]

Listas

Listas, além de serem representadas através de parentes, por outro lado, são implementadas como listas ligadas em um sentido só: cada item aponta para o próximo. Por isso o conj adiciona no começo, que é o lugar mais barato.

Lista ligada do Clojure: os itens 1, 2, 3 e 4 apontam cada um para o próximo, e o último aponta para vazio. O conj cria um nó 5 no começo, que aponta para a lista que já existia 5 (conj lista 5) cria um nó novo no começo 1 2 3 4ø
Lista: cada item aponta para o próximo. Adicionar no começo não mexe no resto.
(def list-numbers '(1 2 3 4))

(conj list-numbers 5)
;; => (5 1 2 3 4)

Conclusão

As duas abordagens apresentam pontos fortes bem diferentes. Em estruturas consideravelmente grandes, ir até uma determinada posição dentro de um Vetor pode ser considerado uma tarefa bastante rápida, isso pelo fato que o Clojure, internamente, usa um algoritmo para saber a localização. Já a Lista, irá precisar percorrer todos os elementos até chegar a determinada posição. Embora pareça que os vetores têm uma certa “vantagem”, as listas são bastante úteis, especialmente nas situações em que você deseja criar uma sequência anexando novos itens como demonstrado no exemplo anterior.

Referências

  • Getting Clojure - Book