Я отмечаю, что схемы и Lisp (я думаю) поддерживают круговые списки, и я использовал круговые списки в C/C++ для «упрощения» вставки и удаления элементов, но для чего они хороши?Что такое круговые списки (для Lisp или Scheme)?
Схема гарантирует, что они могут быть построены и обработаны, но для чего?
Есть ли структура данных 'killer', которая должна быть круговой или круговой?
Говорить, что он поддерживает «циркулярные списки», немного. Вы можете создавать все виды циклических структур данных в Lisp. Как во многих языках программирования. В этом отношении нет особого интереса к Lisp. Возьмите свою типичную книгу «Алгоритмы и данные» и внедрите любую круговую структуру данных: графики, кольца ... Что предлагает некоторые Lisp, так это то, что можно печатать и читать круговые структуры данных. Поддержка этого заключается в том, что в типичных областях программирования Lisp круговые структуры данных являются общими: парсерами, реляционными выражениями, сетями слов, планами, ...
Общепринято, что структуры данных содержат циклы. Реальные «круговые списки» часто используются не так. Например, подумайте о планировщике задач, который запускает задачу и через некоторое время переключается на следующую. Список задач может быть круглым, так что после «последней» задачи планировщик берет «первую» задачу. На самом деле нет «последнего» и «первого» - это всего лишь круговой список задач, и планировщик запускает их без конца. Вы также можете иметь список окон в оконной системе, а с помощью некоторой ключевой команды вы переключитесь на следующее окно. Список окон может быть круглым.
Списки полезны, когда вам нужна дешевая следующая операция, и размер структуры данных неизвестен заранее. Вы всегда можете добавить еще один узел в список или удалить узел из списка. Обычные реализации списков делают получение следующего узла и добавление/удаление товара дешевым. Получение следующего элемента из массива также относительно просто (увеличение индекса, при последнем индексе перейдите к первому индексу), но добавление/удаление элементов обычно требует более дорогостоящих операций сдвига.
Также, поскольку легко создавать круговые структуры данных, можно просто сделать это во время интерактивного программирования. Если вы затем распечатаете круговую структуру данных со встроенными подпрограммами, было бы неплохо, если бы принтер мог ее обработать, так как в противном случае она может печатать круглый список навсегда ...
Под «поддержкой» я имел в виду конкретный синтаксис для описания круговых списков для чтения и записи (как вы говорите). например. '(# 0 = (1 2) (x y. # 0 #))'; также предикат «list?» в схеме указывает, что круговой список не является списком - или это конкретная реализация? – philcolbourn
Хорошо, я вижу, что планировщик задач является круговым списком. Хороший пример. В LISP или Scheme, как бы вы вставляли или удаляли задачу? – philcolbourn
@philcolbourn Конкретный синтаксис, который вы упоминаете, работает в Lisp для всех типов структур данных с циклами. Не только круговые списки. Вы можете использовать операции деструктивного списка, чтобы добавить объект в круглый список. Это типичное упражнение по программированию в курсах Lisp и/или программирования ... –
Например, структура данных с двойным соединенным списком является «круговой» в точке зрения Схемы/LISP, то есть если вы пытаетесь распечатать структуру cons-структуры, вы получаете обратные ссылки, то есть «циклы». Таким образом, дело не в том, что структуры данных выглядят как «кольца», любая структура данных, где у вас есть какие-то backpointers, является «круговой» с точки зрения схемы/LISP.
«Обычный» список LISP является односвязным, что означает, что разрушающая мутация для удаления элемента из списка является операцией O (n); для двойных связанных списков это O (1). Это «функция убийцы» двойных связанных списков, которые являются «круговыми» в контексте Scheme/LISP.
Вы говорите, что «нормальные» списки LISP связаны друг с другом - я это понимаю. Но вы также говорите, что круговые списки в LISP/Scheme связаны вдвойне? – philcolbourn
Я думаю, что он говорил, «если у вас есть двойной список, он круговой». В языке lisp/scheme круговой список означает только, что по меньшей мере одна ссылка далее вниз по списку, по меньшей мере, на одну ячейку ближе к началу. – Vatine
Да, он говорит, что дублированные списки отвечают требованиям «быть кругом». – Cam
Вы когда-нибудь играли в монополию?
Не играя в игры с прилавками и модулем и т. Д., Как бы вы представляли Monopoly board в компьютерной реализации игры? Круговой список является естественным.
'как бы вы представляли Monopoly board в компьютерной реализации игры?' ... Как массив, так что мне не пришлось бы перебирать каждый квадрат на доске каждый ход. – Cam
Чтобы быть честным, вы бы просто указали на текущий квадрат, так что вам не придется этого делать. –
С обычным списком вам нужно будет написать логику, чтобы указать позицию в массиве, чтобы перейти от конца к началу. С круговым списком вы просто используете ту же логику, независимо от того, что: переместите позиции X из текущего. Циркулярный список действительно был бы естественным. – Dave
Добавление и удаление элементов в начало списка дешево. К добавьте или удалите элемент из конца списка, вы должны пройти весь список.
С круглым списком вы можете иметь некоторую очередь фиксированной длины.
Настройка круговой список длины 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 demo, которую я портировал из примера в Processing book.
Ed
Не было бы проще использовать массив для этого? – philcolbourn
Одно использование круговых списков, чтобы «повторить» значение при использовании версии SrfI-1 карта. Например, чтобы добавить val к каждому элементу lst, мы могли бы написать:
(map + (circular-list val) lst)
Например:
(map + (circular-list 10) (list 0 1 2 3 4 5))
возвращается:
(10 11 12 13 14 15)
Конечно, вы могли бы сделать это, заменяя + на (lambda (x) (+ x val)), но иногда вышеуказанная идиома может быть более удобной. Обратите внимание, что это работает только с версией карты srfi-1, которая может принимать списки разных размеров.
Теперь я узнал, что для модели окружения Схемы требуются (слишком сильные?) Круговые списки: процедура, назначенная в среде «указывает» на ее окружение - круговой список. – philcolbourn