Велосипедим связанный список на Wolfram

Возможно 11 подписчиков моего блога обратили внимание на тот факт, что все мои статьи касаются языка Wolfram, а несколько последних статей вышли довольно громоздкими. Одна из последних статей была помечена Хабром как требующая в среднем 32 минуты на прочтение. Я посчитал, что это может отпугнуть пользователей (все 11 человек и не факт, что все они до сих пор читают Хабр) и решил попробовать писать более короткие статьи. Плюс я сам перестану теряться в большом количестве текста.

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

Ниже реализация структуры данных LinkedList на Wolfram Language.

О связанном списке

Не думаю, что это требует длинных объяснений, но если совсем коротко, то такая структура данных ценна тем, что:

• Добавление в конец/начало за O(1)

• Удаление из начала за O(1)

• Поиск или получение по индексу за O(n) — это не очень ценно

• Вставка в середину за O(1), но поиск-то долгий

• Получение всех элементов за O(n) — как у большинства структур

Эта структура данных используется для реализации стека и очереди, так как она оптимизированно добавляет элементы в начало и конец. В Wolfram Language начиная с версии 12.1 есть такие структуры данных как связанный список и двунаправленный связанный список, а также стек, очередь, кольцевой буфер и некоторые другие. Но нас не интересует встроенная реализация, так как здесь клуб вело-любителей. Но если что, вот так создаются связанные списки в WL:

linkedList = CreateDataStructure["LinkedList"]; Do[linkedList["Append", i], {i, 1000}] linkedList["Visualization"]

doublyLinkedList = CreateDataStructure["DoublyLinkedList"]; Do[doublyLinkedList["Append", i], {i, 1000}] doublyLinkedList["Visualization"]

Узел списка

Что ж, приступим! В первую очередь реализуем не сам список целиком, а только один узел этого списка. Сначала легкая подготовка:

$HistoryLength = 0;  ClearAll[LinkedListNode];  SetAttributes[LinkedListNode, HoldFirst]; 

HoldFirst — позволит держать первый аргумент невыполненным. В WL — это один из способов хранения «ссылки» на выражение, вместо самого выражения, т.е. значения. Теперь создаем «конструктор» для узла списка (на самом деле это просто функция):

LinkedListNode[ref_Symbol, value_, next_] :=  With[{uuid = CreateUUID["LINKEDLISTNODE-"]},  If[Not[AssociationQ[ref]], ref = <|"Nodes" -> <||>|>];  ref["Nodes", uuid] = <| "Value" -> value,  "Next" -> next |>;  LinkedListNode[ref, uuid] ]; 

• ref — та самая «ссылка», в которой хранятся данные списка и узла. Если эта ссылка не является ассоциацией, то ей задается новое значение.

• uuid — уникальный номер узла

• value — значение

• next — следующий узел

Вот пример узла:

ClearAll[ref];  node1 = LinkedListNode[ref, 1, Null] (*LinkedListNode[ref, "LINKEDLISTNODE-ad484b44-803b-436f-966a-b359ac961235"]*)

Вот какое значение будет хранить ссылка-символ, после вызова конструктора:

ref (*<|   "Nodes" -> <|     "LINKEDLISTNODE-ad484b44-803b-436f-966a-b359ac961235" -> <|       "Value" -> 1, "Next" -> Null     |>   |> |>*)

Обратите внимание, что символ ref имеет значение, но внутри выражения с заголовком LinkedListNode благодаря атрибуту оно все еще остается в виде невычисленного символа. Лучше понять смысл «удерживания» можно на простом примере:

x = 1;   f[x]  SetAttributes[g, HoldFirst]  g[x]

Теперь добавим узлу методы. Извлечение его свойств:

LinkedListNode[ref_Symbol, uuid_String][key_] :=  ref["Nodes", uuid, key]

Уникального номера:

LinkedListNode[ref_Symbol, uuid_String]["UUID"] :=  uuid; 

И изменение значений свойств:

LinkedListNode /: Set[LinkedListNode[ref_Symbol, uuid_String][key_], value_] :=  ref["Nodes", uuid, key] = value; 

Выше мы по сути переопределяем «оператор присваивания», т.е. «=». Сделано это при помощи так называемого UpSet (obj /: func[obj] := expr[obj]), когда определение связывается не с функцией, а с самим объектом, на котором вызывается функция. Еще добавим метод связывания двух узлов:

LinkedListNode /: link[node_LinkedListNode, next_LinkedListNode] := ( If[node["Next"] =!= Null, next["Next"] = node["Next"]];  node["Next"] = next ); 

Сделаем так, что этот метод может объединить целый список узлов:

link[list_List] := Fold[link, First[list], Rest[list]]; 

Как это работает:

node2 = LinkedListNode[ref, 2, Null];  node3 = LinkedListNode[ref, 3, Null];  link[{node1, node2, node3}] (* => node3 *)  (* node1 -> node2 -> node3 *)

Пока что реализованных методов достаточно. Перейдем к реализации самого списка.

Реализация списка

Как обычно подготовка:

ClearAll[LinkedList];  SetAttributes[LinkedList, HoldFirst]; 

И конструктор списка. Особенность этой функции в том, что она проверяет «ссылку» и если она неподходящая, то меняет ее значение, а если подходящая то возвращает выражение как есть:

LinkedList[ref: _Symbol?(Not@*AssociationQ): Automatic] :=  Which[ ref === Automatic,  With[{$ref = Unique["LINKEDLIST`$"]}, LinkedList[$ref]],  True,  Clear[ref];  ref = <|"Nodes" -> <||>, "Size" -> 0, "Head" -> Null, "Tail" -> Null|>;  LinkedList[ref] ]; 

ref: _Symbol?(Not@*AssociationQ): Automatic слева направо делает следующее:

• ref: _Symbol — значит аргумент должен иметь тип Symbol (т.е. ссылка)

• ?(Not@*AssociationQ) — проверяет аргумент применяя функцию справа от знака вопроса

• Not@*AssociationQ — композиция двух функций

• : Automatic — после второго двоеточия значение по умолчанию. Интересно, что оно может не проходить проверку слева

Теперь метод добавления в конец. Мы создадим функцию append. Она будет брать хвост списка и если его значение это Null, то добавлять и хвост и голову. Но если хвост уже указывает на существующий узел, то к этому узлу привязывается новый узел, а хвост указывает на новый узел. Все тоже самое, но с другой стороны сделаем для prepend:

LinkedList /: append[LinkedList[ref_Symbol], item_] :=  With[{node = LinkedListNode[ref, item, Null]},  ref["Size"] = ref["Size"] + 1;  If[ref["Tail"] === Null,  ref["Head"] = node;  ref["Tail"] = node; ,  (*Else*) link[ref["Tail"], node];  ref["Tail"] = node;  ];  ]; 

LinkedList /: prepend[LinkedList[ref_Symbol], item_] :=  With[{node = LinkedListNode[ref, item, Null]},  ref["Size"] = ref["Size"] + 1;  If[ref["Head"] === Null,  ref["Head"] = node;  ref["Tail"] = node; ,  (*Else*) link[node, ref["Head"]];  ref["Head"] = node;  ];  ]; 

Для обычных списков в WL есть функции First и Last, которые получают первый и последний элемент. Но мы для списка определим отдельные «свойства», которые получают голову и хвост:

LinkedList[ref_Symbol]["Head"] :=  If[ref["Size"] > 0, ref["Head"]["Value"]]; 

LinkedList[ref_Symbol]["Tail"] :=  If[ref["Size"] > 0, ref["Tail"]["Value"]]; 

Так же переопределим функцию, которая получает элемент по индексу (тот самый метод, который занимает O(n)):

LinkedList /: Part[LinkedList[ref_Symbol], i_Integer] /; Abs[i] <= ref["Size"]:=  Block[{$node},  Which[i === 0, LinkedList,  i === 1, ref["Head"],  i === -1, ref["Tail"],  i > 0,  $node = ref["Head"];  Do[$node = $node["Next"], {j, 2, i}];  $node,  i < 0,  $node = ref["Head"];  Do[$node = $node["Next"], {j, -ref["Size"] + 1, i, 1}];  $node ]["Value"] ]; 

И удаление головы с возвращением узла. Здесь я создам функцию pop :

LinkedList /: pop[LinkedList[ref_Symbol]] :=  With[{head = ref["Head"]},  ref["Head"] = head["Next"];  head["Next"] = Null;  head["Value"] ]; 

И последнее, что нам потребуется — функция, которая возвращает все элементы связанного списка в виде обычного списка. Обычно для этих целей используют встроенную функцию Normal:

LinkedList /: Normal[LinkedList[ref_Symbol]] :=  Block[{node = ref["Head"], value},      Table[         value = node["Value"];          node = node["Next"];          value,          {i, 1, ref["Size"]}     ] ]; 

Примеры

Минимальная реализация связанного списка готова. Создать его можно вот так:

linkedList = LinkedList[]

Затем его можно заполнить:

Do[append[linkedList, i], {i, 10}] Do[prepend[linkedList, i], {i, 10}]

Удалить часть из начала:

Table[pop[linkedList], {5}] (* {10, 9, 8, 7, 6} *)

Посмотреть содержимое:

Normal[linkedList] (* {5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} *)

Производительность

Моя реализация не самая оптимальная, плюс WL — это интерпретируемый язык и каждую команду он отправляет в ядро по отдельности. На самом деле можно намного лучше, но это будет более громоздко и малоинформативно. Но в конце концов нам важна не сама скорость выполнения операций, а их временная сложность. Что ж, докажем, что добавление в начало и конец не зависят от размера списка:

linkedList = LinkedList[];  appendTime = Table[{i, AbsoluteTiming[append[linkedList, i]][[1]]}, {i, 1, 10000}]; 

linkedList = LinkedList[];  prependTime = Table[{i, AbsoluteTiming[prepend[linkedList, i]][[1]]}, {i, 1, 10000}]; 

linkedList = LinkedList[];  popTime = Table[{i,  append[linkedList, i];  prepend[linkedList, i];  AbsoluteTiming[pop[linkedList]][[1]] }, {i, 1, 10000}]; 

И построим график зависимости времени операции от размера списка:

ListPlot[{appendTime, prependTime, popTime},  ImageSize -> Large,  PlotTheme -> "Detailed",  PlotLegends -> {"append", "prepend", "pop"} ]

Ну и докажем, что время получения по индексу и извлечения всех элементов линейно растет с ростом числа элементов:

linkedList = LinkedList[];  partTime = Table[{i,  append[linkedList, i];  index = RandomInteger[{1, First[linkedList]["Size"]}]; AbsoluteTiming[linkedList[[index]]][[1]] }, {i, 1, 2000}]; 

linkedList = LinkedList[];  normalTime = Table[{i,  append[linkedList, i];  AbsoluteTiming[Normal[linkedList]][[1]] }, {i, 1, 2000}]; 

И построим график:

ListPlot[{partTime, normalTime},  ImageSize -> Large,  PlotTheme -> "Detailed",  PlotLegends -> {"part", "Normal"} ]

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

Красивая плашка

И последняя совершенно необязательная часть. Сделаем так, чтобы в интерфейсе Mathematica наша структура данных красиво отображалась. Т.е. не в виде LinkedList[ref], а так, как отображаются другие сложные объекты. Например разреженный массив:

SparseArray[{{1, 1} -> 2, {100, 100} -> 101, {5, 66} -> 1243}]

Чтобы сделать нечто похожее — надо использовать внутреннюю функцию для SummaryBox :

$linkedListIcon = ImageResize[Import["https://wolfr.am/1jBx5PyAQ"], 1920 / 5];    LinkedList /: MakeBoxes[linkedList: LinkedList[ref_Symbol?AssociationQ],  form: (StandardForm | TraditionalForm)] :=  Module[{above, below},  above = { {BoxForm`SummaryItem[{"Ref: ", Defer[ref]}], SpanFromLeft},  {BoxForm`SummaryItem[{"Size: ", ref["Size"]}], SpanFromLeft},  {BoxForm`SummaryItem[{"Head: ", linkedList["Head"]}], SpanFromLeft},  {BoxForm`SummaryItem[{"Tail: ", linkedList["Tail"]}], SpanFromLeft} };  below = {};   (*Return*) BoxForm`ArrangeSummaryBox[ LinkedList,  linkedList,  $linkedListIcon,  above,  below,  form,  "Interpretable" -> Automatic ] ];

• MakeBoxes — функция, которая переопределяет отображение некоторого выражения в интерфейсе Wolfram Mathematica

• (StandardForm | TraditionalForm) — два альтернативных формата на которых сработает это отображение. Есть еще например FullForm — он не переопределен и покажет список «как есть»

• BoxForm`ArrangeSummaryBox и BoxForm`SummaryItem — те самые внутренние функция для создания «плашек»

• $linkedListIcon — иконка, которую я скачал прямо из интернета по короткой ссылке

Заключение

В этой статье я постарался показать каким образом можно самостоятельно реализовать некую структуру данных на Wolrfam Language. Я особенно хочу отметить то, как я использовал удерживающий атрибут HoldFirst, а так же конструкцию With для того чтобы в функции с HoldFirst передавать не ссылку а значение. Надеюсь вам статья показалась интересной! В следующий раз мы реализуем еще какую-нибудь структуру данных с использованием особенностей WL.

Всем спасибо за внимание!