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