W Clojure, kiedy powinienem używać wektora nad listą i na odwrót?


Odpowiedzi:


112

Po raz kolejny wydaje mi się, że odpowiedziałem na swoje pytanie, zniecierpliwiony i zadając je na #clojure na Freenode. Zachęcamy do odpowiadania na własne pytania na Stackoverflow.com: D

Odbyłem szybką dyskusję z Rich Hickey i oto jej sedno.

[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

Będąc na freenode, przejdź na ciemną stronę i dołącz do #stackoverflow! :-P
Chris Jester-Young

Właściwie tam siedziałem. Zmieniłem klientów IRC i nigdy nie pomyślałem o dodaniu #stackoverflow do mojej listy autojoin.
Rayne

Jestem początkującym Lispem, ale zastanawiałem się, czy wektory, mapy i zestawy w jakiś sposób łamią ideę, że cały kod jest wymienny z danymi? A może to tylko jedna z tych rzeczy, które sprawiają, że Clojure jest praktycznym Lispem? (LUB, czy możesz ocenić wektor?)
Rob Grant,

23
To jest całkowicie nieprzydatny fragment czatu. „Generowanie kodu” „generowanie od tyłu do przodu” -> oznacza dokładnie ?? Naprawdę mam trudności z tym pytaniem, ponieważ w mojej książce lenistwo + deklaratywny styl = znacznie lepsza wydajność, a mimo to wektory są sugerowane wszędzie w Clojure, co całkowicie mnie zdezorientowało.
Jimmy Hoffa,

22
@JimmyHoffa Tak, jak to rozumiem: "Generowanie kodu" = "Wewnątrz makra" (ponieważ większość kodu to wywołania funkcji, a więc listy); "generowanie od początku do końca" = "budowanie sekwencji przez poprzedzanie".
omiel

87

Jeśli dużo zajmowałeś się programowaniem w Javie i znasz strukturę kolekcji Java, pomyśl o listach, takich jak LinkedListi wektorach, takich jak ArrayList. Możesz więc wybrać pojemniki w ten sam sposób.

Dla dalszego wyjaśnienia: jeśli zamierzasz dodawać elementy pojedynczo na początku lub na końcu sekwencji, lista połączona jest znacznie lepsza niż wektor, ponieważ elementy nie muszą być tasowane za każdym razem. Jeśli jednak chcesz często uzyskiwać dostęp do określonych elementów (nie blisko początku ani z tyłu listy) (tj. Dostęp losowy), będziesz chciał użyć wektora.

Nawiasem mówiąc, wektory można łatwo przekształcić w sekwencje.

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)

Wektory nie są sekwencjami, ale są sekwencyjne. (źródło: Rich sam na #clojure na freenode.) Poza tym w ogóle nie znam Javy, ale Rich właśnie odpowiedział na moje pytanie.
Rayne

1
Zmienię swój post, aby powiedzieć, że wektory można przekształcić w sekwencje za pomocą funkcji seq. :-)
Chris Jester-Young

2
Wybierz swoją odpowiedź, ponieważ rzeczywiście odpowiedziała na pytanie, a ja naprawdę nie lubię wybierać moich własnych odpowiedzi jako poprawnych. Nie wydaje się w porządku. Dzięki. :)
Rayne,

Deque jest lepszy niż lista połączona w przypadku dodawania pierwszego i ostatniego. LL są dość okropne: P
boxed

1
@boxed Nie możesz zaimplementować deque na wektorze lub ArrayListbez efektywnego ponownego zaimplementowania ArrayDequesiebie.
Chris Jester-Young

43

Wektory mają O (1) czasów dostępu swobodnego, ale muszą być wstępnie przydzielone. Listy można rozszerzać dynamicznie, ale dostęp do elementu losowego jest O (n).


3
Technicznie rzecz biorąc, listy połączone mają czasy dostępu O (1) ... jeśli uzyskujesz dostęp tylko do elementu przedniego lub tylnego. :-P Jednak wektory mają dostęp losowy O (1). :-)
Chris Jester-Young

4
(„Lista połączona”, jak opisano powyżej, odnosi się do list podwójnie połączonych. Listy połączone pojedynczo mają dostęp O (1) tylko do elementu przedniego. :-P)
Chris Jester-Young

1
Ponieważ ktoś właśnie zagłębia się w Clojure, jest to O WIELE lepsza odpowiedź niż dwóch pozostałych z większą liczbą głosów. Pozostali dwaj nie mówią mi nic przydatnego.
keithjgrant

@ ChrisJester-Young Lista pojedynczo połączona może obsługiwać dostęp O (1) do tyłu, jeśli przechowuje odniesienie do tylnego elementu, w ten sposób .
Gill Bates

30

Kiedy używać wektora:

  • Wydajność dostępu indeksowanego - uzyskasz ~ O (1) koszt dostępu indeksowanego w porównaniu z O (n) dla list
  • Dołączanie - z połączeniem ~ O (1)
  • Wygodna notacja - łatwiej mi zarówno pisać, jak i czytać [1 2 3] niż „(1 2 3) dla dosłownej listy w okolicznościach, w których jedno i drugie by się sprawdzało.

Kiedy używać listy:

  • Gdy chcesz uzyskać do niego dostęp jako sekwencję (ponieważ listy bezpośrednio obsługują sekwencję bez konieczności przydzielania nowych obiektów)
  • Prepending - dodanie na początek listy z wadami lub najlepiej spójnikiem O (1)

3
Nawet po dodaniu / usunięciu listy na obu końcach lista jest dość okropnym wyborem. Deque jest znacznie lepszy (w procesorze, a zwłaszcza w pamięci). Wypróbuj github.com/pjstadig/deque-clojure
pudełku

2
Re: the ~O(1), dla tych, dla których to wyjaśnienie kosztów może być pomocne - stackoverflow.com/questions/200384/constant-amortized-time
Merlyn Morgan-Graham

13

tylko krótka uwaga dodatkowa:

„Czytałem, że wektory nie są sekwencjami, ale listy są”. 

sekwencje są bardziej ogólne niż listy lub wektory (lub mapy lub zbiory).
Szkoda, że REPL drukuje listy i sekwencje w ten sam sposób, ponieważ naprawdę sprawia, że ​​wygląda na to, że listy są sekwencjami, mimo że są różne. funkcja (seq) utworzy sekwencję z wielu różnych rzeczy, w tym list, a następnie możesz przekazać tę sekwencję do dowolnej z wielu funkcji, które wykonują sprytne rzeczy z sekwencjami.

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 ma skrót, który zwraca swój argument, jeśli jest już sekwencją:

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);
}

listy są sekwencjami, chociaż inne rzeczy też są i nie wszystkie sekwencje są listami.


Nie chcę czepiać się małej kwestii, to tylko okazja, aby wskazać coś przydatnego. wielu już to wie :)
Arthur Ulfeldt

2
Nie masz na myśli classzamiast class??
qerub

Nie jestem pewien, czy twój przykład zmienił się po aktualizacji clojure (myślę, że jestem na 1.5), ale oba twoje przykłady wrócą clojure.lang.PersistentListdo mnie. Zakładam, że miałeś zamiar classnie pisać class?.
Adrian Mouat,

Rzeczywiście! Naprawię to
Arthur Ulfeldt,

Wciąż trochę zdezorientowany; ponieważ classzwraca tę samą PersistentList dla obu wymienionych przez Ciebie wyrażeń, oznacza to, że sekwencje i listy są rzeczywiście tym samym?
johnbakers
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.