Структуры данных в lisp

Question

У меня есть простая проблема: собрать объекты в список и пройти этот список в обратном направлении.Кажется довольно простым, но этот код является частью высоконагруженных вычислений.Весьма естественно использовать conses, потому что для добавления нового элемента и последовательного доступа требуется O (1).Но что мне делать, если мне нужен эффективный список с двумя связями, чтобы легко обходить его в обоих направлениях?Использовать (реверс)?Это займет O (n) памяти и времени, так что на самом деле это займет O (n ^ 2) в моем случае (что действительно плохо).Использовать (последний) или (добавить)?Та же история: O (n).Я не очень понимаю, где можно найти (кроме исходного кода) какую-либо информацию о вычислительной сложности стандартных функций библиотеки.Это зависит от реализации?И что я должен сделать для реализации различных стандартных структур данных?Есть ли инструкции по эффективному использованию conses?

Answer 1

Если вы используете Common Lisp, вы можете вместо этого использовать векторы.Векторы могут иметь указатель заполнения и / или могут быть регулируемыми.Таким образом, вы можете использовать vector-push для добавления элементов в вектор.Указатель заполнения будет расти.Если вектор является регулируемым, то при необходимости он также будет увеличен.Поскольку векторы являются одномерными массивами, вы можете обращаться к элементам с индексом по своему усмотрению.

См. Параметры MAKE-ARRAY для создания такого вектора.

VECTOR-PUSH и VECTOR-PUSH-EXTEND - это функции для добавления элементов.

Answer 2

Если вы выполните (reverse) один раз, а затем просмотрите обратный список в последовательном порядке, итоговое значение должно составить всего O (2n) времени (O (n) для настройки, а затем еще одно O (n) для прохождения) и O (n) памяти.

Двусвязный список не очень сложен. Как вы знаете, список состоит из cons-ячеек, где автомобиль указывает на объект, а cdr указывает на следующую cons-ячейку в списке.

Один из способов создания двусвязного списка состоит в том, чтобы вместо него указывать cdr на другую cons-ячейку, чей cdr указывает на следующую cons-ячейку в списке, а автомобиль указывает на предыдущую cons-ячейку в списке. Затем вы используете cddr, чтобы двигаться вперед, и cdar, чтобы двигаться назад.

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