Прохожу хороший туториал по лиспу: http://www.cs.sfu.ca/CC/310/pwfong/Lisp/3/tutorial3.html
И есть там такая задача 
Exercise: A set can be implemented as a sorted list, which is a list storing distinct members in ascending order. Implement the sorted list abstraction.  Ок, значит надо реализовать сет используя абстракцию отсортированного списка. Зачем? Вроде бы очевидно - для того чтобы к примеру находить элементы с логарифмической сложностью. Т.е. если мне нужно реализовать функцию добавления нового элемента то нужно будет найти индекс, куда его вставить. Используя тот факт что список отсортирован для нахождения этого индекса можно использовать метод половинного деления. 

Но вот что меня смутило.

Я новичек в лиспе. Насколько я сейчас понимаю в лиспе список является связным. То-есть операция взятия элемента по индексу функцией nth имеет сложность не O(1) а O(N).  На каждой итерации метода половинного деления надо один раз вызвать метод nth чтобы получить средний элемент. А это значит что как ни крути добиться логарифмической сложности не получится!! Я прав или ошибаюсь?

Прав. Зато объединение отсортированных списков с удалением дублей делается за линейное время, а не за квадратичное.

Странный этот лисп. Такой примитивной вещи как быстрое взятие элемента по индексу нету оО. Может конечно задач где это было бы критично не так много, но все же.. Очень странно

Если Вам нужен быстрый доступ по индексу - используйте массив вместо списка. Но тогда вставка элемента в начало будет работать долго. Разные структуры данных существуют не просто так - и не только в Лиспе.

Спасибо! В том туториале который я прохожу еще ничего небыло про массивы) Я было думал что в лиспе ничего кроме списков нет  Ну тогда все классно.

Весьма советую: Практический Common Lisp
Там всё, что нужно.

Большое спасибо!! Как раз читаю оригинал (http://gigamonkeys.com/book/). Хорошая книжка.

Это сообщение отредактировал(а) GreenTea22 - 20.9.2009, 20:29

Перевод на русский язык, PDF-версия