Ну тогда все классно.| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > LISP > Скорость взятия элемента по индексу - функция nth |
| Автор: GreenTea22 6.9.2009, 14:55 |
| Прохожу хороший туториал по лиспу: 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 чтобы получить средний элемент. А это значит что как ни крути добиться логарифмической сложности не получится!! Я прав или ошибаюсь? |
| Автор: adejneka 7.9.2009, 05:39 |
| Прав. Зато объединение отсортированных списков с удалением дублей делается за линейное время, а не за квадратичное. |
| Автор: GreenTea22 7.9.2009, 19:41 |
| Странный этот лисп. Такой примитивной вещи как быстрое взятие элемента по индексу нету оО. Может конечно задач где это было бы критично не так много, но все же.. Очень странно |
| Автор: adejneka 8.9.2009, 05:40 |
| Если Вам нужен быстрый доступ по индексу - используйте массив вместо списка. Но тогда вставка элемента в начало будет работать долго. Разные структуры данных существуют не просто так - и не только в Лиспе. |
| Автор: GreenTea22 8.9.2009, 21:06 |
| Спасибо! В том туториале который я прохожу еще ничего небыло про массивы) Я было думал что в лиспе ничего кроме списков нет Ну тогда все классно. |
| Автор: lonli 13.9.2009, 10:06 |
| Весьма советую: http://pcl.catap.ru/doku.php Там всё, что нужно. |
| Автор: GreenTea22 20.9.2009, 20:29 |
| Большое спасибо!! Как раз читаю оригинал (http://gigamonkeys.com/book/). Хорошая книжка. |
| Автор: _sg 25.4.2014, 09:57 |
| http://lisper.ru/pcl/pcl.pdf |