Велосипедим связанный список на Wolfram22.01.2024 08:45

Георгий Вицин пытается освободиться за O(1)

Георгий Вицин пытается освободиться за O (1)

Возможно 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 благодаря атрибутом оно все еще остается в виде невычисленного символа. Лучше понять смысл «удерживания» можно на просто примере: 

f1 = f[1 + 1] (* => f[2] *)

SetAttributes[g, HoldFirst]
g1 = g[1 + 1] (* => g[1 + 1] *)

f1[[1]]    (* => 2 *)
g1[[1, 1]] (* => 1 т.е. 1 из 1 + 1 *)
g1[[1, 0]] (* => Plus т.е. "+" из 1 + 1 *)

Как работает HoldFirst

Как работает HoldFirst

Это ассоциация, т.е. по сути HashMap и мы реализуем одну структуру данных с использованием другой. Теперь добавим узлу методы. Извлечение его свойств: 

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 — функция, которая переопределяет отображение некоторого выражения в интерфейсе Wolrfam Mathematica

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

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

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

Визуальное отображение связанного списка в блокноте

Визуальное отображение связанного списка в блокноте

Заключение

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

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

© Habrahabr.ru