Структуры данных в lisp - программирование

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

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

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