Блог

Я хочу реализовать простой двойной связанный список в SBCL со следующей ключевой структурой

 (defstruct element
  (value 0 :type fixnum)
  (next nil :type element)
  (prev nil :type element))
 

Проблема в том, что невозможно создать экземпляр первого элемента, потому что ни следующий, ни предыдущий не могут быть равны нулю. Их тип-элемент, и поэтому они должны быть экземпляром.

Проблему в принципе легко исправить, если я удалю свойство type. Но дело в том, что эта часть программы должна быть очень быстрой, поэтому я хочу дать оптимизатору возможность извлечь из нее максимум пользы.

Есть ли какой-либо другой способ указать тип участника И сделать их равными нулю? Или лучше: есть ли способ создать начальный экземпляр со ссылкой next и prev на сам экземпляр?

Можно также настроить иерархию:

 (defstruct element)

(defstruct (null-element (:include element)))

(defstruct (link-element (:include element))
  (value 0                   :type fixnum)
  (next  (make-null-element) :type element)
  (prev  (make-null-element) :type element))
 

Используя его:

 * (compile-file "linked-list.lisp")
; compiling file "/Users/joswig/Desktop/linked-list.lisp"
;   (written 08 APR 2021 12:58:56 PM):
; processing (DEFSTRUCT ELEMENT)
; processing (DEFSTRUCT (NULL-ELEMENT #))
; processing (DEFSTRUCT (LINK-ELEMENT #) ...)

; wrote /Users/joswig/Desktop/linked-list.fasl
; compilation finished in 0:00:00.032
#P"/Users/joswig/Desktop/linked-list.fasl"
NIL
NIL
* (load *)
T
* (make-link-element)
#S(LINK-ELEMENT :VALUE 0
                :NEXT #S(NULL-ELEMENT)
                :PREV #S(NULL-ELEMENT))
 

 (defstruct element
  (value 0 :type fixnum)
  (next nil :type (or element null))
  (prev nil :type (or element null)))
 

Нет ничего плохого в том, чтобы NIL представлял нулевые элементы, но в случае, если вы действительно хотите применить этот тип, вы можете сделать это следующим образом.

ALLOCATE-INSTANCE Универсальная функция (но не INITIALIZE-INSTANCE явно) указана для работы с экземплярами STRUCTURE-CLASS .

Прямое объявление нулевого элемента функции

Эта функция возвращает нулевое значение для типа element . С SBCL это не является строго необходимым, если вы компилируете все определения сразу (т. Е. с compile-file помощью ).

 (declaim (ftype function null-element))
 

Определить структуру

Форма инициализации для значений является вызовом null-element , чтобы значение удовлетворяло типу при формировании новой структуры. Для этой структуры не определен конструктор, чтобы усложнить ее создание вручную (и избежать проблем с именованием).

 (defstruct (element (:constructor nil))
  (value 0 :type fixnum)
  (next (null-element) :type element)
  (prev (null-element) :type element))
 

Создание экземпляра элемента

Здесь код выделяет структуру, но не инициализирует ее. Это позволяет избежать проблемы, которая может возникнуть у вас с sbcl, когда он автоматически проверяет тип своих слотов. Здесь содержимое слотов не определено после выделения, но затем им присваиваются значения соответствующего типа (сам элемент).

 (defun make-element (value)
  (let ((element (allocate-instance (find-class 'element))))
    (prog1 element
      (setf (element-value element) value
            (element-next  element) element
            (element-prev  element) element))))
 

Используя класс, я бы позвонил initialize-instance вместо этого, но я не думаю, что это будет работать во всех реализациях. Использование setf для прямой установки слотов работает.

Здесь я соглашаюсь с вашим вопросом и хочу, чтобы элемент имел ссылки на себя.

Или лучше: есть ли способ создать начальный экземпляр со ссылкой next и prev на сам экземпляр?

Вы также можете оставить поля (null-element) , но это только вопрос выбора дизайна.

Одноэлементное значение нулевого элемента

Вызов (null-element) возвращает значение sentinel, представляющее нулевой элемент. Здесь я выделяю один экземпляр element во время загрузки и возвращаю один и тот же экземпляр при каждом вызове. Фактическое значение, хранящееся в узле, не имеет значения. Как указывает Райнер Йошвиг, нулевой элемент может быть экземпляром структуры, в которой такого значения нет.

 (defun null-element ()
  (load-time-value (make-element 0)))

(defun null-element-p (element)
  (eq element (null-element)))
 

Я хочу дать оптимизатору шанс извлечь из этого максимум пользы.

Если вы хотите, чтобы код двусвязного списка был как можно быстрее, не nil используйте указатели на завершение.

Используйте узел sentinel для завершения связанного списка, эффективно делая его циклическим.

Таким образом, это означает, что пустой список-это узел, который указывает на себя:

 (defun make-dl-list()
  (let ((do (make-element)))
     (setf (element-next sentinel) dl
           (element-prev sentinel) dl)
      dl))
 

Во главе списка стоит (element-next list) . Если это значение является самим списком, то список пуст:

  (defun dl-list-empty (dl)
   (eq (element-next dl) dl))
 

Вставка спереди:

  (defun dl-insert-front (list node)
   (let ((head (element-next list)))
     (setf (elem-next node) head
           (elem-prev node) list
           (elem-prev head) node
           (elem-next list) node)))
 

Удаление узла: указатель на список не требуется!

  (defun dl-delete-node (node)
   (let ((next (elem-next node))
         (prev (elem-prev node))
     (setf (elem-next prev) next
           (elem-prev next) prev)))
 

Обратите внимание, что ни одна из этих операций не выполняет никаких тестов; это всего лишь базовые блоки указателей на обновление кода.