В Clojure, когда я должен использовать вектор над списком, и наоборот?

147

Я читал, что Векторы не являются последовательностями, но Списки. Я не уверен, в чем причина использования одного над другим. Кажется, что векторы используются чаще всего, но есть ли причина для этого?

Rayne
источник
1
Связанный stackoverflow.com/questions/6928327/…
Дункан МакГрегор

Ответы:

112

Еще раз, кажется, я ответил на свой вопрос, проявив нетерпение и задав его в #clojure на Freenode. На Stackoverflow.com рекомендуется отвечать на ваши вопросы: D

У меня было быстрое обсуждение с Ричем Хики, и вот суть этого.

[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
источник
Пока вы находитесь на freenode, переходите на темную сторону и присоединяйтесь к #stackoverflow! :-P
Крис Шестер-Янг
Я вообще-то там простаивал. Я переключил клиентов IRC и никогда не думал, что добавлю #stackoverflow в свой список автоматического присоединения.
Рейн
Я новичок в Lisp, но мне было интересно, нарушают ли векторы, карты и наборы идею, что весь код взаимозаменяем с данными? Или это только одна из тех вещей, которые делают Clojure практическим Лиспом? (ИЛИ, вы можете оценить вектор?)
Роб Грант
23
Это совершенно бесполезный фрагмент чата. «Генерация кода» «генерация задом наперед» -> означает точно ?? У меня действительно возникают трудности с этим вопросом, потому что в моей книге лень + декларативный стиль = гораздо лучшая производительность, и тем не менее повсюду в Clojure предлагаются векторы, что приводит меня в замешательство.
Джимми Хоффа
22
@JimmyHoffa Как я понимаю: «Генерация кода» = «Внутри макроса» (потому что большая часть кода - это вызовы функций, то есть списки); "генерация задом наперед" = "построение последовательности путем добавления".
Омель
87

Если вы много занимались программированием на Java и знакомы с фреймворком Java-коллекций, подумайте о списках как LinkedListи векторах как ArrayList. Таким образом, вы можете выбрать контейнеры таким же образом.

Для дальнейшего пояснения: если вы намерены добавлять элементы по отдельности в начало или конец последовательности, связанный список намного лучше, чем вектор, потому что элементы не нужно перетасовывать каждый раз. Однако, если вы хотите получить доступ к определенным элементам (не в начале или в конце списка) часто (например, произвольный доступ), вам нужно будет использовать вектор.

Кстати, векторы легко превращаются в последовательности.

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)
Крис Шут-Янг
источник
Векторы не являются последовательностями, но они последовательны. (источник: Рич сам на #clojure на freenode.) Кроме того, я совсем не знаю Java, но Рич только что ответил на мой вопрос.
Рэйн
1
Я отредактирую свой пост, говоря, что векторы можно преобразовать в seqs с помощью функции seq. :-)
Крис Шут-Янг
2
Выберите свой ответ, потому что он действительно ответил на вопрос, и мне действительно не нравится выбирать свои собственные ответы как правильные. Не кажется правильным. Спасибо. :)
Rayne
Дек лучше, чем связанный список в случае добавления первого и последнего. LL довольно ужасны: P
штучной упаковке
1
@boxed Вы не можете реализовать deque поверх вектора или ArrayListбез эффективного переопределения ArrayDequeсебя.
Крис Шут-Янг
43

Векторы имеют O (1) времен произвольного доступа, но они должны быть предварительно выделены. Списки могут быть динамически расширены, но доступ к случайному элементу - O (n).

Сванте
источник
3
Технически, связанные списки имеют O (1) времени доступа ... если вы обращаетесь только к переднему или заднему элементу. :-P Однако, векторы имеют O (1) произвольный доступ. :-)
Крис Шут-Янг
4
(«Связанный список», как описано выше, относится к двусвязным спискам. Односвязные списки имеют O (1) доступ только к переднему элементу. :-P)
Крис Джестер-Янг
1
Поскольку кто-то просто погружается в Clojure, это ПУТЬ лучше, чем два других с большим количеством голосов. Два других не говорят мне ничего полезного.
Keithjgrant
@ ChrisJester-Young Односвязный список может поддерживать O (1) доступ к задней части, если он хранит ссылку на элемент задней части, например .
Гилл Бейтс
30

Когда использовать вектор:

  • Производительность индексированного доступа - Вы получаете ~ O (1) стоимость для индексированного доступа против O (n) для списков
  • Добавление - с ~ O (1)
  • Удобная запись - мне легче и печатать, и читать [1 2 3], чем '(1 2 3) для буквального списка в тех случаях, когда любой из них будет работать.

Когда использовать список:

  • Когда вы хотите получить доступ к нему как к последовательности (поскольку списки напрямую поддерживают seq без необходимости выделения новых объектов)
  • Preeding - добавление в начало списка с минусами или, предпочтительно, конъюнктурой (1)
mikera
источник
3
Даже при добавлении / удалении на обоих концах список является довольно ужасным выбором. Дек намного лучше (в процессоре и особенно в памяти). Попробуйте github.com/pjstadig/deque-clojure
штучной упаковке
2
Re:, ~O(1)для тех, кому это объяснение стоимости может быть полезным - stackoverflow.com/questions/200384/constant-amortized-time
Мерлин Морган-Грэм
13

просто быстрое примечание:

«Я читал, что Векторы - это не последовательность, а списки». 

последовательности являются более общими, чем списки или векторы (или карты или множества).
К сожалению, REPL печатает списки и последовательности одинаково, потому что это действительно делает их похожими на списки, даже если они разные. Функция (seq) создаст последовательность из множества различных вещей, включая списки, и вы можете затем передать этот seq любому из множества функций, которые делают изящные вещи с помощью 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 имеет ярлык, который возвращает свой аргумент, если он уже является 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);
}

списки являются последовательностями, хотя есть и другие вещи, и не все последовательности являются списками.

Артур Ульфельдт
источник
Я не хочу выбирать маленькую точку, это просто возможность указать на что-то полезное. многие уже будут знать это :)
Артур Ульфельдт
2
Разве вы не имеете в виду classвместо class??
Qerub
Не уверен, что ваш пример изменился после обновления clojure (я думаю, что я на 1.5), но оба ваших примера возвращаются clojure.lang.PersistentListдля меня. Я предполагаю, что ты хотел написать classнет class?.
Адриан Муат
Я действительно сделал! Я исправлю это
Артур Ульфельдт
Все еще немного смущен; поскольку classвозвращает один и тот же PersistentList для обоих упомянутых вами выражений, это означает, что последовательности и списки действительно одно и то же?
Джонбейкерс