Что циклические списки хороши для (в Lisp или Схеме)?
Я отмечаю, что Схема и Lisp (я предполагаю) поддерживают циклические списки, и я использовал циклические списки в C/C++ для 'упрощения' вставки и удаления элементов, но для чего они хороши?
Схема гарантирует, что они могут быть созданы и обработаны, но для какой?
Существует ли 'уничтожающая' структура данных, которая должна быть круговой или круговой хвостом?
4 ответа
Сказать, что он поддерживает "круговые списки" - это слишком. В Лиспе можно строить все виды круговых структур данных. Как и во многих других языках программирования. В этом отношении в Лиспе нет ничего особенного. Возьмите свою типичную книгу "Алгоритмы и структура данных" и реализуйте любую круговую структуру данных: графы, кольца, .... Что предлагают некоторые Лиспы, так это то, что можно печатать и читать круговые структуры данных. Это поддерживается тем, что в типичных областях программирования на Лиспе круговые структуры данных встречаются часто: синтаксические анализаторы, реляционные выражения, сети слов, планы ...
Довольно часто структуры данных содержат циклы. Настоящие "круговые списки" используются не так часто. Например, вспомните планировщик задач, который выполняет задачу и через некоторое время переключается на следующую. Список задач может быть круговым, так что после "последней" задачи планировщик берет "первую" задачу. На самом деле нет никаких "последних" и "первых" - это просто круговой список задач, и планировщик выполняет их без конца. Вы также можете иметь список окон в оконной системе, и с помощью некоторой ключевой команды вы будете переключаться на следующее окно. Список окон может быть круговым.
Списки полезны, когда вам нужна дешевая следующая операция, а размер структуры данных заранее неизвестен. Вы всегда можете добавить еще один узел в список или удалить узел из списка. Обычные реализации списков делают получение следующего узла и добавление/удаление элемента дешевыми. Получение следующего элемента из массива также относительно просто (увеличить индекс, при последнем индексе перейти к первому индексу), но добавление/удаление элементов обычно требует более дорогих операций сдвига.
Кроме того, поскольку строить круговые структуры данных легко, можно просто делать это во время интерактивного программирования. Если вы затем печатаете круговую структуру данных с помощью встроенных процедур, было бы хорошо, если бы принтер мог справиться с этим, поскольку в противном случае он может печатать круговой список вечно...
Например, структура данных двусвязного списка является "круговой" с точки зрения схемы / LISP, т.е. если вы попытаетесь распечатайте cons-структуру, вы получите обратные ссылки, то есть "циклы". Так что на самом деле речь идет не о структурах данных, которые выглядят как «кольца», любая структура данных, в которой есть какие-то обратные указатели, является «круговой» с точки зрения схемы / LISP.
«Обычный» список LISP является односвязным, что означает, что деструктивная мутация для удаления элемента изнутри списка является операцией O (n); для двусвязных списков это O (1). Это «убийственная особенность» двусвязных списков, которые в контексте Scheme / LISP являются «круговыми».
Вы когда-нибудь играли в «Монополию»?
Не играя в игры со счетчиками, модулем и т.п., как бы вы изобразили доску «Монополия» в компьютерной реализации игры? Круговой список - это естественно.
Добавление и удаление элементов в начало списка обходится недорого. Чтобы добавить или удалить элемент из конца списка, вы должны пройти по всему списку.
С круговым списком у вас может быть что-то вроде очереди фиксированной длины.
Создайте круговой список длиной 5:
> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))
Давайте добавим число в список:
> (set-car! q 6)
Теперь давайте сделаем это последним элементом списка:
> (set! q (cdr q))
Показать список:
> (take q 5)
(2 3 4 5 6)
Итак, вы можете рассматривайте это как очередь, в которой элементы входят в конец списка и удаляются из заголовка.
Давайте добавим 7 к списку:
> (set-car! q 7)
> (set! q (cdr q))
> (take q 5)
(3 4 5 6 7)
Etc ...
В любом случае, это один из способов использования круговых списков.
Я использую эту технику в демонстрации OpenGL , которую я перенес из примера из книги Processing .
Эд