В качестве контейнера данных, каковы основные различия между вектором и списком

Ответ 1

[1 2 3] - vector, тогда как '(1 2 3) - list, Существуют разные характеристики производительности этих двух структур данных.

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

Списки легко изменяются на голове и/или хвосте (в зависимости от реализации), но обеспечивают линейный доступ к элементам: (nth (list 1 2 3 4 5) 3) требует последовательного сканирования списка.

Для получения дополнительной информации о компрометации производительности вы можете использовать вектор "вектор против производительности списка" или что-то подобное.

[ПОСЛЕДУЮЩИЕ UP]

Хорошо, давайте рассмотрим более подробно. Прежде всего, векторы и списки - это понятия, не относящиеся к Clojure. Наряду с картами, очередями и т.д. Они представляют собой абстрактные типы коллекций данных. Алгоритмы, работающие с данными, определяются в терминах этих абстракций. Векторы и списки определены по поведению, которое я кратко описал выше (т.е. Что-то является вектором, если он имеет размер, вы можете получить доступ к своим элементам и индексу в постоянное время и т.д.).

Clojure, как и любой другой язык, хочет выполнить эти ожидания при предоставлении структур данных, которые называются таким образом. Если вы посмотрите на базовую реализацию nth в vector, вы увидите вызов метода arrayFor, который имеет сложность O ( log ₃₂ N) и поиск в массиве Java, который является O (1).

Почему мы можем сказать, что (v 34) есть фактически O (1)? Поскольку максимальное значение log ₃₂ для Java int составляет около 7. Это означает, что случайный доступ к вектору является фактическим постоянным временем.

Таким образом, основное отличие между vectors и lists - это характеристики производительности. Кроме того, как указывает Джереми Хейлер, в Clojure существуют логические различия в поведении, т.е. В отношении выращивания коллекции с conj.

Ответ 2

Существуют два основных различия между списками и векторами.

• Списки логически растут в голове, тогда как векторы логически растут на хвосте. Это можно увидеть при использовании функции conj. Он будет выращивать коллекцию в соответствии с типом коллекции, данной ей. Хотя вы можете выращивать коллекции с обеих сторон, это делается так, чтобы сделать это.

• Чтобы получить n-й элемент в списке, список должен быть перемещен из головы. С другой стороны, векторы не пересекаются и возвращают n-й элемент в O (1). (Это действительно O (log32n), но это связано с тем, как коллекции реализуются как постоянные коллекции.)

Ответ 3

время оценки вектора не O (1) it log32N

Векторы (IPersistentVector) Вектор - это набор значений, индексированных смежными целыми числами. Векторы поддерживают доступ к элементам по индексу в перехватах log32N. count - O (1). conj помещает элемент в конец вектора. Векторы также поддерживают rseq, который возвращает элементы в обратном порядке. Векторы реализуют IFn, для invoke() одного аргумента, который, как они предполагают, являются индексом и выглядят сами по себе, как если бы на n-м, то есть векторы являются функциями их индексов.

Ответ 4

• Вектор содержит все элементы данных в смежных областях памяти, что делает передача всего вектора легко и вставка или удаление элементов по сравнению со списками.

• Список элементов хранения - это непересекающиеся области памяти, что делает передачу весь список дорог, но вставка и удаление отдельных предметов относительно дешево.

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

• Векторы также предлагают индексированный доступ к элементам элемента. В списках нет. Классическим предшественником вектора является массив.
• Современные реализации векторов часто направлены на предоставление аналогичных но базовая структура данных может быть фактически список или хэш, и эти векторы обычно поддерживают динамический повторно проклейки.