Реализация динамического списка на WL / Habr

Пользователь просит ядро выделить больше памяти под динамический список

Это тематическое продолжение моей предыдущей статьи, которая описывала реализацию связанного списка на Wolfram Language. На этот раз мы будем делать динамический список. Где-то его называют просто список либо динамический массив. В C# эта структура представлена типом List<T>, а в Java наиболее похожим классом является ArrayList, хотя насколько я помню называют его динамический массив.

Цель этой статьи - демонстрация возможностей и трюков языка Wolfram. А так же это руководство по созданию своих структур данных. Кроме того, возможно, эта статья будет полезна тем, что только начинает изучать программирование и в частности структуры данных.

Ниже реализация динамического массива/списка на Wolfram Language.

Немного о динамическом списке

Как известно, эта структура данных очень похожа на обычный массив, с тем отличием, что у массива размер фиксированный, а у динамического списка он может меняться. Собственно вот и все. Все остальные его особенности - это уже вопрос эффективности. Какими свойствами обладает динамический массив:

Добавление в начало и конец за O(1)
Удаление из начала и конца за O(1)
Получение произвольного элемента по индексу за O(1)
Вставка в середину за O(n) в среднем
Поиск элемента по значению за O(n)

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

Список

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

Сначала небольшая подготовка:

ClearAll["`*"]; 

$HistoryLength = 0;

Пустой список создается вот так:

list1 = {};

Для заполнения списка данными мы создадим свою функцию. В дальнейшем она нам понадобится для динамического списка:

SetAttributes[append, HoldFirst]; 

append[list_, item_] := 
list = Append[list, item];

Заполняем его и вычисляем время, которое занимает добавление каждого элемента:

appendTime = 
Table[{i, AbsoluteTiming[append[list1, i]][[1]]}, {i, 1, 5000}];

К сожалению функции удаления нет, поэтому сделаем ее сами:

SetAttributes[remove, HoldFirst]; 

remove[list_Symbol] := 
list = Delete[list, -1];

А теперь посчитаем время этой операции в зависимости от размера списка. Очищаем, заполняем по новой два раза и удаляем элементы по одному разу на каждую итерацию.

list1 = {}; 

removeTime = Table[
	{
		i, 
		append[list1, i]; 
		append[list1, i]; 
		AbsoluteTiming[remove[list1]][[1]]
	}, 
	{i, 1, 5000}
];

Получение элемента по индексу выполняется при помощи функции part. Будем получать случайный элемент на каждой итерации и параллельно увеличивать размер массива:

part[list_, i_] := 
list[[i]]; 

list1 = {}; 

partTime = 
Table[
	{
		i, 
		append[list1, i]; 
		With[{j = RandomInteger[{1, i}]},  
			AbsoluteTiming[part[list1, j]][[1]]
		]
	}, 
	{i, 1, 5000}
];

Вставка в случайное место - примерно так же как и с удалением и случайным индексом:

SetAttributes[insert, HoldFirst]; 

insert[list_, item_, i_] := 
list = Insert[list, item, i]; 

list1 = {1}; 

insertTime = 
Table[
	{
		i, 
		With[{j = RandomInteger[{1, i}]},  
			AbsoluteTiming[insert[list1, i, j]][[1]]
		]
	}, 
	{i, 1, 5000}
];

И последнее - поиск. Будем как в предыдущем пункте вставлять индекс в случайное место, а затем искать его при помощи функции position:

position[list_, item_] := 
Position[list, item]; 

list1 = {1}; 

positionTime = 
Table[
	{
		i, 
		With[{j = RandomInteger[{1, i}]},  
			insert[list1, i, j]; 
			AbsoluteTiming[position[list1, i]][[1]]
		]
	}, 
	{i, 1, 5000}
];

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

ListPlot[{appendTime, removeTime, insertTime}, 
	PlotLegends -> {"append", "remove", "insert"}, 
	ImageSize -> Large, 
	PlotTheme -> "Detailed"
]

Зависимость времени добавления, удаления и вставки от размера списка

ListPlot[{positionTime}, 
	PlotLegends -> {"position"}, 
	ImageSize -> Large, 
	PlotTheme -> "Detailed"
]

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

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

Хоть тут все хорошо! Доступ по индексу за константное время. На фоне других графиков этот будет сливаться с осью X, поэтому он тоже отдельно

Что мы имеем? Встроенный список все перечисленные выше операции выполняет за O(n) и только получение по индексу за O(1).

Собственная реализация

А теперь приступим к реализации динамического массива! Нам нужно сделать так, чтобы 3 перечисленные операций из начала статьи (кроме вставки и поиска) имели временную сложность порядка O(1). Как это сделать? Алгоритм очень прост:

Размер массива всегда больше, чем число его элементов
Добавление происходит записью в уже существующую позицию, а это быстро
Если только происходит запись на последнюю позицию + 1, то массив увеличивается в два раза
Когда число элементов меньше чем фактический размер в два раза - то массив уменьшается

Приступим к его реализации. Сначала подготовка - создадим свой символ, зададим ему атрибут HoldFirst (он поможет хранить ссылку) и определим функцию для создания динамического списка:

ClearAll[DynamicList]; 

SetAttributes[DynamicList, HoldFirst]

createDynamicList[] := 
With[{ref = Unique["DYNAMICLIST`$"]}, 
	ref = <|
		"Data" -> {0}, 
		"Length" -> 0,     (*число элементов*)
		"Capacity" -> 1    (*доступный размер*)
	|>; 
	DynamicList[ref]
];

Определим на нем те 5 методов, которые мы использовали для проверки временной сложности операций с List. Я сознательно не буду реализовывать prepend для добавления в начало и pop для удаления из начала, так как они аналогичный append и remove только с другого конца.

В первую очередь реализуем добавление элемента в список. Сначала я уберу атрибут, так как сейчас он нам не понадобится и создам определение, которое связывается с самим типом DynamicList:

ClearAttributes[append, HoldFirst]

DynamicList /: append[DynamicList[ref_Symbol], item_] := 
With[{len = ref["Length"], capacity = ref["Capacity"]}, 
	If[len === capacity, 
		ref["Data"] = Join[ref["Data"], ConstantArray[0, len]]; 
		ref["Capacity"] = capacity * 2; 
	]; 
	ref["Length"] = len + 1; 
	ref[["Data", len + 1]] = item
];

Это очень простой и эффективный способ создать массив нефиксированной длинный. Дело в том, что при увеличении списка каждый раз в два раза частота вызова этой операции будет все меньше и меньше, т.е. снижаться логарифмически. Хоть и один вызов создания списка - это "тяжелая" операция, но для больших списков она вызывается настолько редко, что не влияет на производительность в среднем.

Таким же образом создадим метод удаления элемента из конца:

ClearAttributes[remove, HoldFirst]; 

DynamicList /: remove[DynamicList[ref_Symbol]] := 
With[{
	len = ref["Length"], 
	capacity = ref["Capacity"], 
	item = ref[["Data", ref["Length"]]]
}, 
	If[len === capacity / 2, 
		ref["Data"] = ref[["Data", ;; len / 2]]; 
		ref["Capacity"] = capacity / 2; 
	]; 
	ref["Length"] = len - 1; 
	ref[["Data", len]] = 0; 
	item
];

Операция вставки будет чуть сложнее:

ClearAttributes[insert, HoldFirst]; 

DynamicList /: insert[DynamicList[ref_Symbol], item_, i_Integer] := 
With[{len = ref["Length"], capacity = ref["Capacity"]}, 
	If[len === capacity, 
		ref["Data"] = Join[ref["Data"], ConstantArray[0, len]]; 
		ref["Capacity"] = capacity * 2;  
	]; 
	ref["Length"] = len + 1; 
	ref[["Data"]] = Join[ref[["Data", 1 ;; i - 1]], {item}, ref[["Data", i ;; -2]]]; 
	item
];

И простые определения для поиска и части:

DynamicList /: position[DynamicList[ref_Symbol], item_] := 
Position[ref[["Data", 1 ;; ref["Length"]]], item];

DynamicList /: part[DynamicList[ref_Symbol], i_Integer] := 
If[Abs[i] <= ref["Length"], 
    ref[["Data", i]], 
    Message[General::partw, i, DynamicList[ref]]
];

Последнее - несколько вспомогательных функций:

DynamicList /: Normal[DynamicList[ref_Symbol]] := 
ref[["Data", 1 ;; ref["Length"]]]; 

DynamicList /: DeleteObject[DynamicList[ref_Symbol]] := 
ClearAll[ref];

Плашка и примеры

Я по традиции приведу код, который будет отображать динамический список в виде SummaryBox. Никакой функциональности эта штука за собой не кроет:

$dynamicListIcon = Import["https://wolfr.am/1jEFx2BBO"];

DynamicList /: MakeBoxes[object: DynamicList[ref_Symbol], 
	form: (StandardForm | TraditionalForm)] := 
Module[{above, below}, 
	above = {
		{BoxForm`SummaryItem[{"Ref: ", Defer[ref]}], SpanFromLeft}, 
		{BoxForm`SummaryItem[{"Length: ", ref["Length"]}], SpanFromLeft}, 
		{BoxForm`SummaryItem[{"Capacity: ", ref["Capacity"]}], SpanFromLeft}
	}; 
	below = {}; 
	
	BoxForm`ArrangeSummaryBox[
		DynamicList, 
		object, 
		$dynamicListIcon, 
		above, 
		below, 
		form, 
		"Interpretable" -> Automatic
	]
];

И несколько примеров. Создаем динамический список:

dynamicList1 = createDynamicList[]

Добавляем элементы:

append[dynamicList1, #]& /@ Range[10]

Удаляем несколько:

Do[remove[dynamicList1], {3}]

Все элементы в виде списка:

Normal[dynamicList1]

Удаление динамического списка:

DeleteObject[dynamicList1]

Проверяем что теперь по ссылке пусто:

dynamicList1[[1]]

Как это выглядит в интерфейсе блокнота

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

Ну и результаты тестов. Так как мы переопределили все те же самые функции на динамическим списке, то код для измерения времени выполнения операций останется без изменения. Нужно только list1 заменить на dynamicList1:

DeleteObject[dynamicList1]; 

dynamicList1 = createDynamicList[]; 

appendTime = 
Table[{i, AbsoluteTiming[append[dynamicList1, i]][[1]]}, {i, 1, 5000}]; 

DeleteObject[dynamicList1]; 

dynamicList1 = createDynamicList[]; 

removeTime = Table[
	{
		i, 
		append[dynamicList1, i]; 
		append[dynamicList1, i]; 
		AbsoluteTiming[remove[dynamicList1]][[1]]
	}, 
	{i, 1, 5000}
];

И график:

ListPlot[{appendTime, removeTime}, 
	PlotLegends -> {"append", "remove"}, 
	ImageSize -> Large, 
	PlotTheme -> "Detailed"
]

С увеличением числа элементов время будет все ближе к константе. Ступеньки совпадают со степенями двойки: 2^10 ~ 1000, 2^11 ~ 2000, 2^12 ~ 4000

А вот сложность вставки, поиска и получения по индексу не должны были измениться. Проверим:

DeleteObject[dynamicList1]; 

dynamicList1 = createDynamicList[]; 

insertTime = 
Table[
	{
		i, 
		With[{j = RandomInteger[{1, i}]},  
			AbsoluteTiming[insert[dynamicList1, i, j]][[1]]
		]
	}, 
	{i, 1, 5000}
];

И график:

ListPlot[{insertTime}, 
	PlotLegends -> {"insert"}, 
	ImageSize -> Large, 
	PlotTheme -> "Detailed"
]

О чудо! Даже вставка стала эффективнее, так как теперь она растет ступенчато!

Благодаря тому, что вставка пересоздает список фиксированной длинны, то при одном и той же величине "Capacity" время остается константой, но все же оно растет ступенчато.

Ну и поиск, который был самым медленным:

DeleteObject[dynamicList1]; 

dynamicList1 = createDynamicList[]; 

positionTime = 
Table[
	{
		i, 
		With[{j = RandomInteger[{1, i}]},  
			insert[dynamicList1, i, j]; 
			AbsoluteTiming[position[dynamicList1, i]][[1]]
		]
	}, 
	{i, 1, 5000}
];

График:

ListPlot[{positionTime}, 
	PlotLegends -> {"position"}, 
	ImageSize -> Large, 
	PlotTheme -> "Detailed"
]

Тут без изменений

Ремарка касательно Position. Дело в том, что эта функция ищет все позиции элемента в списке, а значит гарантированно проходится от начала и до конца за линейное время.

Заключение

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

Блокнот с кодом из статьи вы можете скачать из репозитория на GitHub.