Передача переменной с большим объемом данных требует большого количества памяти и времени в Mathematica?

Я кодирую алгоритм построения дерева суффиксов в Mathematica на основе алгоритма Укконена.

Вопрос, который у меня есть, передаст мою всю структуру дерева (которую я сохранил в списке) в функцию для поиска, стоимость моей программы много памяти и времени, так как я должен использовать некоторые из функций несколько раз в алгоритме?

Например, у меня есть функция, которая ищет дочерние элементы определенного node, и я использую функцию Select для поиска по всему дереву.

getChildren[parentID_] := Select[tree, #[[3]] == parentID &];

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

Ответы

Ответ 1

Нет, для передачи выражений не требуется дополнительная память. Как обычно в функциональных языках, объекты Mathematica immutable: они не могут быть изменены, вместо этого создается новый объект при их преобразовании с использованием некоторых функция. Это также означает, что, если вы не преобразуете их, они не копируются, независимо от того, сколько вы передаете их между функциями.


С точки зрения пользователя, выражения Mathematica являются деревьями, но я считаю, что внутри они хранятся как ориентированные ациклические графики, то есть одно и то же подвыражение может храниться только один раз в памяти, независимо от того, сколько раз оно появляется в полном выражении (см., например, страницу документа Share[]).

Вот пример, иллюстрирующий:

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

In[1]:= $HistoryLength = 0;

Проверьте использование памяти:

In[2]:= MemoryInUse[]
Out[2]= 13421756

Сделайте выражение, которое занимает заметный объем памяти:

In[3]:= s = [email protected][1000000];

In[4]:= MemoryInUse[]
Out[4]= 17430260

Теперь повторите это выражение сто раз...

In[5]:= t = ConstantArray[s, 100];

... и обратите внимание, что использование памяти почти не увеличивается:

In[6]:= MemoryInUse[]
Out[6]= 18264676

ByeCount[] вводит в заблуждение, поскольку он не сообщает о фактической физической памяти, но память, которая будет использоваться, если общие подвыражения Разрешено использовать одну и ту же память:

In[7]:= ByteCount[t]
Out[7]= 400018040

Интересно отметить: если вы удалите f[...] из s и сделайте как s, так и t простой численный массив, тогда этого совместного использования памяти не произойдет, и использование памяти переместится на ~ 400 МБ.


Если вы сделаете tree глобальную переменную или аргумент getChildren, это не повлияет на использование памяти.