В Clojure, когда я должен использовать вектор над списком, и наоборот?
147
Я читал, что Векторы не являются последовательностями, но Списки. Я не уверен, в чем причина использования одного над другим. Кажется, что векторы используются чаще всего, но есть ли причина для этого?
Еще раз, кажется, я ответил на свой вопрос, проявив нетерпение и задав его в #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
Пока вы находитесь на freenode, переходите на темную сторону и присоединяйтесь к #stackoverflow! :-P
Крис Шестер-Янг
Я вообще-то там простаивал. Я переключил клиентов IRC и никогда не думал, что добавлю #stackoverflow в свой список автоматического присоединения.
Рейн
Я новичок в Lisp, но мне было интересно, нарушают ли векторы, карты и наборы идею, что весь код взаимозаменяем с данными? Или это только одна из тех вещей, которые делают Clojure практическим Лиспом? (ИЛИ, вы можете оценить вектор?)
Роб Грант
23
Это совершенно бесполезный фрагмент чата. «Генерация кода» «генерация задом наперед» -> означает точно ?? У меня действительно возникают трудности с этим вопросом, потому что в моей книге лень + декларативный стиль = гораздо лучшая производительность, и тем не менее повсюду в Clojure предлагаются векторы, что приводит меня в замешательство.
Джимми Хоффа
22
@JimmyHoffa Как я понимаю: «Генерация кода» = «Внутри макроса» (потому что большая часть кода - это вызовы функций, то есть списки); "генерация задом наперед" = "построение последовательности путем добавления".
Омель
87
Если вы много занимались программированием на Java и знакомы с фреймворком Java-коллекций, подумайте о списках как LinkedListи векторах как ArrayList. Таким образом, вы можете выбрать контейнеры таким же образом.
Для дальнейшего пояснения: если вы намерены добавлять элементы по отдельности в начало или конец последовательности, связанный список намного лучше, чем вектор, потому что элементы не нужно перетасовывать каждый раз. Однако, если вы хотите получить доступ к определенным элементам (не в начале или в конце списка) часто (например, произвольный доступ), вам нужно будет использовать вектор.
Кстати, векторы легко превращаются в последовательности.
Векторы не являются последовательностями, но они последовательны. (источник: Рич сам на #clojure на freenode.) Кроме того, я совсем не знаю Java, но Рич только что ответил на мой вопрос.
Рэйн
1
Я отредактирую свой пост, говоря, что векторы можно преобразовать в seqs с помощью функции seq. :-)
Крис Шут-Янг
2
Выберите свой ответ, потому что он действительно ответил на вопрос, и мне действительно не нравится выбирать свои собственные ответы как правильные. Не кажется правильным. Спасибо. :)
Rayne
Дек лучше, чем связанный список в случае добавления первого и последнего. LL довольно ужасны: P
штучной упаковке
1
@boxed Вы не можете реализовать deque поверх вектора или ArrayListбез эффективного переопределения ArrayDequeсебя.
Крис Шут-Янг
43
Векторы имеют O (1) времен произвольного доступа, но они должны быть предварительно выделены. Списки могут быть динамически расширены, но доступ к случайному элементу - O (n).
Технически, связанные списки имеют 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)
Даже при добавлении / удалении на обоих концах список является довольно ужасным выбором. Дек намного лучше (в процессоре и особенно в памяти). Попробуйте github.com/pjstadig/deque-clojure
«Я читал, что Векторы - это не последовательность, а списки».
последовательности являются более общими, чем списки или векторы (или карты или множества).
К сожалению, REPL печатает списки и последовательности одинаково, потому что это действительно делает их похожими на списки, даже если они разные. Функция (seq) создаст последовательность из множества различных вещей, включая списки, и вы можете затем передать этот seq любому из множества функций, которые делают изящные вещи с помощью seqs.
Я не хочу выбирать маленькую точку, это просто возможность указать на что-то полезное. многие уже будут знать это :)
Артур Ульфельдт
2
Разве вы не имеете в виду classвместо class??
Qerub
Не уверен, что ваш пример изменился после обновления clojure (я думаю, что я на 1.5), но оба ваших примера возвращаются clojure.lang.PersistentListдля меня. Я предполагаю, что ты хотел написать classнет class?.
Адриан Муат
Я действительно сделал! Я исправлю это
Артур Ульфельдт
Все еще немного смущен; поскольку classвозвращает один и тот же PersistentList для обоих упомянутых вами выражений, это означает, что последовательности и списки действительно одно и то же?
Ответы:
Еще раз, кажется, я ответил на свой вопрос, проявив нетерпение и задав его в #clojure на Freenode. На Stackoverflow.com рекомендуется отвечать на ваши вопросы: D
У меня было быстрое обсуждение с Ричем Хики, и вот суть этого.
источник
Если вы много занимались программированием на Java и знакомы с фреймворком Java-коллекций, подумайте о списках как
LinkedList
и векторах какArrayList
. Таким образом, вы можете выбрать контейнеры таким же образом.Для дальнейшего пояснения: если вы намерены добавлять элементы по отдельности в начало или конец последовательности, связанный список намного лучше, чем вектор, потому что элементы не нужно перетасовывать каждый раз. Однако, если вы хотите получить доступ к определенным элементам (не в начале или в конце списка) часто (например, произвольный доступ), вам нужно будет использовать вектор.
Кстати, векторы легко превращаются в последовательности.
источник
ArrayList
без эффективного переопределенияArrayDeque
себя.Векторы имеют O (1) времен произвольного доступа, но они должны быть предварительно выделены. Списки могут быть динамически расширены, но доступ к случайному элементу - O (n).
источник
Когда использовать вектор:
Когда использовать список:
источник
~O(1)
для тех, кому это объяснение стоимости может быть полезным - stackoverflow.com/questions/200384/constant-amortized-timeпросто быстрое примечание:
последовательности являются более общими, чем списки или векторы (или карты или множества).
К сожалению, REPL печатает списки и последовательности одинаково, потому что это действительно делает их похожими на списки, даже если они разные. Функция (seq) создаст последовательность из множества различных вещей, включая списки, и вы можете затем передать этот seq любому из множества функций, которые делают изящные вещи с помощью seqs.
Sec имеет ярлык, который возвращает свой аргумент, если он уже является seq:
списки являются последовательностями, хотя есть и другие вещи, и не все последовательности являются списками.
источник
class
вместоclass?
?clojure.lang.PersistentList
для меня. Я предполагаю, что ты хотел написатьclass
нетclass?
.class
возвращает один и тот же PersistentList для обоих упомянутых вами выражений, это означает, что последовательности и списки действительно одно и то же?