Возможно 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.
Всем спасибо за внимание!
