Структура данных Lisp с использованием вектора в пунктирной паре - PullRequest
Новая
       18

Структура данных Lisp с использованием вектора в пунктирной паре

0 голосов
/ 22 июня 2019

Как запоздалое продолжение этого , кто-то может объяснить мне, почему структура данных, используемая в файлах пакетов Emacs ELPA archive-contents, представляет собой пунктирную пару имени (символа) и вектора, которыйсодержит много вещей?

В чем преимущество такого подхода?Это кажется слишком преднамеренным, чтобы быть случайным ударом.На каком прецеденте находится это здание? 

(1
 (ace-window .
         [(0 9 0)
          ((avy (0 2 0)))
          "Quickly switch windows." single
          ((:url . "https://github.com/abo-abo/ace-window")
           (:keywords "window" "location"))])

... представьте себе (1 ...), в котором гораздо больше членов списка;Например, список доступных пакетов MELPA огромен.Поэтому, если я сделаю (cdr (assq 'ace-window THELIST)), у меня есть сопутствующий вектор пунктирной пары, начинающийся с ace-window.Казалось бы, список был разработан для использования предыдущего sexp.Так что да, почему они использовали вектор в этой ситуации?Это хорошая идиоматическая практика?Я слышал, что Clojure рекомендует больше использовать массивы и векторы над списками.Это больше соответствует философии Clojure?Так что, если список больше похож на кортеж, то есть с множеством, неизменяющимися членами, следует ли использовать векторы вместо списков?Или это разновидность загадочной проблемы с кортежами ?

1 Ответ

1 голос
/ 23 июня 2019

То есть, если список больше похож на кортеж, то есть с множеством неизменяемых членов, следует ли использовать векторы вместо списков?

Есть преимущества 1 , да. В частности, доступ к элементу - это O (1) для векторов, но O (n) для списков.

C-h i g (elisp)Sequences Arrays Vectors объясняет:

Тип «sequence» - это объединение двух других типов Lisp: списков и массивы. Другими словами, любой список является последовательностью, а любой массив - последовательность. Общее свойство, которое имеют все последовательности, состоит в том, что каждый упорядоченная коллекция элементов.

«Массив» - это объект фиксированной длины со слотом для каждого из его элементы. Все элементы доступны в постоянном времени. Четверка типы массивов: строки, векторы, таблицы символов и bool-векторы.

Список - это последовательность элементов, но это не единственный примитив объект; это сделано из клеток cons, одна ячейка за элемент. В поисках N элемент требует просмотра через N cons клеток, поэтому элементы дальше от начало списка займет больше времени для доступа. Но это возможно добавить элементы в список или удалить элементы.

<Ч />

1 , в зависимости от конкретного варианта использования, преимущества могут или не могут быть ощутимы на практике.

...