Сложность Схема векторов

Question

6.3.6 Vectors сечения в стандартных состояниях Схемы R5RS следующее о векторах:

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

Это описание векторов немного размыто.

Я хотел бы знать, что это на самом деле означает, с точки зрения vector-ref и list-ref операций и их сложности. Обе процедуры возвращают k-ый элемент вектора и списка. Является ли операция вектора O (1) и является ли операция списка O (n)? Как векторы отличаются от списков? Где я могу найти дополнительную информацию об этом?

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

Answer 1

Очень конкретные детали vector-ref и list-ref зависит от реализации, что означает: каждый интерпретатор Scheme может реализовать спецификацию, как он считает нужным, так что ответ на ваш вопрос не может быть обобщена для всех переводчиков, соответствующих R5RS, его зависит от от фактического интерпретатора, который вы используете.

Но да, в любой достойной реализации есть безопасная ставка, чтобы предположить, что операция vector-ref равна O (1) и что операция list-ref, вероятно, O (n). Зачем? потому что вектор под капотом должен быть реализован с использованием структуры данных, родной для языка реализации, что позволяет O (1) получить доступ к элементу с учетом его индекса (скажем, примитивного массива), поэтому делает реализацию vector-ref простой. В то время как списки в Lisp создаются путем связывания ячеек cons, и поиск элемента в любом заданном индексе влечет за собой перемещение всех элементов перед ним в списке - следовательно, сложность O (n).

В качестве побочного примечания - да, использование векторов было бы более быстрой альтернативой, чем использование списков ассоциаций пар ключ/значение, если ключи являются целыми числами, а количество индексируемых элементов известно заранее (вектор схемы не может расти по размеру после его создания). В общем случае (ключи, отличные от целых чисел, размер переменной) проверьте, поддерживает ли ваш интерпретатор хэш-таблицы или использует внешнюю библиотеку, которая их предоставляет (скажем, SRFI 69).

Answer 2

A изготовлен из cons сотовых телефонов. От R⁵RS list section:

Объекты в автомобильных полях последовательных пар списка являются элементами списка. Например, список из двух элементов - это пара, чей автомобиль является первым элементом и чья cdr является парой, чей автомобиль является вторым элементом и чья cdr - пустой список. Длина списка - это количество элементов, которое совпадает с количеством пар.

Например, список (a b c) эквивалентна следующей серии пар: (a . (b . (c .())))

А может быть представлена ​​в памяти с помощью следующих «узлов»:

[p] --> [p] --> [p] --> null 
|  |  | 
|==> a |==> b |==> c 

с каждым узлом [] содержащий указатель p на значение (это car) и другой указатель на следующий элемент (это cdr).

Это позволяет увеличить список до неограниченной длины, но для начала поиска в начале списка необходимо выполнить операцию ref и переместить k элементов, чтобы найти запрошенный. Как вы сказали, это O (n).

---

В противоположность этому, вектор в основном массив значений, которые могут быть внутренне представлены как массив указателей. Например, вектор #(a b c) может быть представлен в виде:

[p p p] 
| | | 
| | |==> c 
| | 
| |==> b 
| 
|==> a 

Если массив [] содержит серию из трех указателей, и каждый указатель присваивается значение в векторе. Таким образом, вы можете ссылаться на третий элемент вектора v, используя обозначение v[3]. Поскольку вам не нужно проходить предыдущие элементы, vector-ref является операцией O (1).

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

---

Есть много ресурсов в Интернете - эта статья на Scheme Data Structures переходит в более подробно и приведены некоторые примеры, хотя это гораздо больше сосредоточены на списках.

---

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