В Лиспе и других функциональных языках, почему длина не O(1)
Примитивы списка в Лиспе имеют длину оператора, определяемую следующим образом:
(define (length lst)
(if (null? lst) 0 (+ 1 (length (cdr lst)))))
Почему разработчики некоторых Lisp не могут сделать длину примитивом, вычисленным за постоянное время?
Спасибо
4 ответа
Причина в "традиционной" реализации списков в Лиспе. В других местах списки иногда реализуются аналогично массиву. Итак, когда вы создаете список, это отдельная, автономная вещь.
An array-like list: [ 1 2 3 4 5 6 ]
Если вы хотите прикрепить элемент - например, "0" - к началу этого списка (и при условии, что реализация списка упрощена), все элементы в списке будут сдвинуты вверх (вправо). Затем "0" будет установлен в новом месте.
Step 0. [ 1 2 3 4 5 6 ]
Step 1. [ 1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)
Это не то, как (традиционные) списки Lisp вообще. Каждый элемент списка представляет собой отдельный элемент, который указывает на следующий элемент. Части списка называются "conses". (Это называется связанным списком.)
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
А? Ну, каждый из этих пунктов является клеткой против. И в каждой ячейке cons есть два значения: car и cdr. (Когда ячейки cons используются со списками, лучше называть "car" и "cdr" как "first" и "rest". "First" содержит любые данные, которые вы хотите сохранить в списке, такие как числа или даже ссылки на другие списки. "Rest" содержит остальную часть списка. Вы также можете поместить все, что хотите, в часть "rest", но здесь мы проигнорируем.) "Nil" - это "пустой список", который в основном означает "список закончился!"
Итак, что, если мы хотим снова поставить "0" на передний план?
[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
Увидеть? Мы только что создали новую ячейку cons, которая указывала на начало старого списка. Вы услышите, как люди называют это "употреблением" значения на фронте. Но вы заметите, что остальная часть списка остается нетронутой.
Хорошо, но почему кто-то хочет этого? Вы можете поделиться списками. Представьте, что вы хотели два в основном одинаковых списка. Только теперь вы хотели, чтобы один список начинался с "7", а другой - с "4"? Ну, с использованием массива, у нас должно быть два списка.
[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]
Что если вы заменили "5" на "13" и поделились этим изменением?
[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]
У вас есть два совершенно разных списка. Если вы хотите поделиться изменениями, вам придется внести изменения в оба списка.
Что происходит с традиционными списками Lisp? Сначала наклеиваем "7" и "4" вперед:
[7]
\
----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
/
[4]
Ага. Мы только что сделали два утверждения, которые оба указывают на старый список. Остальная часть списка является общей. И, если мы заменим "5" на "13":
[7]
\
----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
/
[4]
Оба списка получают изменения, потому что остальные являются общими.
Смысл всего этого в том, что, в отличие от того, что ожидают многие, традиционные списки Лиспа - это не одно. Это куча маленьких вещей (понятий), которые указывают друг на друга, образуя цепочку, которая является списком. Если вы хотите получить длину цепи, вы должны следовать всем маленьким ссылкам, пока не дойдете до конца, ноль. Таким образом, длина O(n).
Списки Lisp могут быть сделаны O(1), если они сделаны как массивы. Я уверен, что некоторые непонятные Лиспы делают это и вообще избавляются от связанных списков. Но conses, кажется, является одной из вещей, которая пробивается в основном на каждом популярном диалекте Lisp. Если вам нужна длина O(1) и поиск, большинство из них также предоставляют массивы или векторы.
Прикольный список веселья:
-----------------<------------------------<----------
| |
--> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->
Этот связанный список в конечном итоге указывает на себя. Если вы используете свою функцию длины, она зациклится навсегда, ищет конец, но никогда не найдет его.
Большинство диалектов Lisp не имеют списков в качестве примитивного типа данных. Например, в Common Lisp списки состоят из cons-ячеек и пустого списка (он же NIL). Минус ячейка - это структура данных с двумя полями: CAR и CDR. С помощью cons-ячеек и NIL можно предоставить множество структур данных: односвязные списки, списки ассоциаций, круговые списки, деревья,...
Lisp мог бы реализовать списки по-другому (без всяких смыслов), но обычно это не так.
Кстати, Common Lisp имеет настраиваемые массивы с указателем заполнения. Указатель заполнения обеспечивает длину в O(1).
Это O(n) для простого связанного списка, но есть и другие доступные структуры данных. Например, Clojure реализует List и Vector с количеством O(1).
Потому что люди не спрашивают длину списка достаточно часто, чтобы оправдать стоимость места. И если вы делаете, вы делаете это неправильно.