Древовидная структура данных в Mathematica

Question

Я использовал mathematica в основном в качестве рабочего места для математики и для написания сравнительно небольших специальных программ. Однако я проектирую систему, которую собираюсь запрограммировать в Mathematica. Мне нужно хранить данные в дереве, а также искать и обходить дерево. Хотя я знаю, как реализовать дерево, я предпочитаю стандартный, проверенный код. Я посмотрел, какие пакеты существуют для базовых структур данных, в вики пользователей Mathematica. Я не нашел ни одного, хотя есть небольшой пример в документации Mathematica.

Теперь на мой вопрос (ы):

1. Есть ли где-нибудь пакет с открытым исходным кодом для структур данных?

2. Какой подход вы использовали в отношении структур данных? Постепенно разрабатываете свой собственный пакет утилит?

(Не вопрос, просто замечание. Может быть... отсутствие (много доступных) пакетов с открытым исходным кодом является причиной, по которой Mathematica не имеет импульса, которого она заслуживает. Боюсь, что это проблема курицы / яйца.)

Answer 1

В Mathematica большая часть того, что вы делаете, основана на выражениях. Выражения естественно имеют древовидную структуру. Для обходов в глубину (которые, вероятно, наиболее распространены), вы можете использовать такие функции, как Scan, Map, Cases и т. д. Различие по сравнению с более традиционными языками состоит в том, что не существует простого способа сохранить идентичность отдельного узла в дереве выражений, поскольку в Mathematica нет указателей. Кроме того, многие операции с выражениями, которые являются идиоматическими в Mathematica, копируют все выражение, когда вам нужно только изменить его в нескольких местах, потому что выражения неизменны.

Использование неизменяемых выражений Mathematica в качестве деревьев по-прежнему имеет ряд преимуществ. Одна из них заключается в том, что, поскольку они неизменны, легко понять, что они хранят, просто взглянув на них (состояние и поведение не смешаны). Другое заключается в том, что существуют эффективные и общие функции, такие как Map, MapIndexed или же Scan, что пересечь их. Например, шаблон дизайна посетителя невидим - он просто Map[f,tree,Infinity], встроенный в язык. Кроме того, есть встроенные функции, такие как Cases, Replace, ReplaceAllи т. д., которые позволяют писать очень лаконичный и декларативный код для деструктурирования деревьев, находить фрагменты деревьев с определенным синтаксисом или удовлетворять некоторым условиям и т. д. Поскольку деревья не ограничиваются только построением из списков и построением из разных глав, один может эффективно использовать это, чтобы написать очень краткий код обработки дерева. Наконец, свобода очень легко создавать любую желаемую древовидную структуру значительно упрощает проведение экспериментов и создание прототипов в духе исследовательского и восходящего программирования, что сокращает цикл разработки и в конечном итоге приводит к улучшению дизайна.

Тем не менее, вы, безусловно, можете реализовать структуру данных с изменяемым состоянием (изменяемым). Реальная причина, по которой это еще не было сделано, - это, как я подозреваю, снижение производительности, связанное со сборкой, изменением и обходом такого дерева, поскольку оно будет проходить полный процесс символьной оценки на каждом этапе (см. Этот пост для получения дополнительной информации об этом). Два примера того, как, например, двоичное дерево поиска можно использовать в контексте Mathematica для довольно эффективного кода, см. В моих сообщениях здесь (общие символьные настройки) и здесь (в контексте скомпилированного кода). Для общих способов построения структур данных идиоматически в Mathematica, я рекомендую книги Романа Медера: "Программирование в Mathematica", "Mathematica programmer I&II" и особенно "Информатика в Mathematica". В последнем у него есть подробное обсуждение того, как реализовать двоичное дерево поиска в Mathematica. РЕДАКТИРОВАТЬ Как сказал @Simon, выступление @Daniel Lichtblau также является отличным ресурсом, который показывает, как создавать структуры данных и делать их эффективными.

Что касается общих способов реализации структур данных в Mathematica, которые бы включали в себя некоторое состояние, вот простой пример, извлеченный из моего поста в этом потоке Mathgroup - он реализует "парную" структуру данных.

Unprotect[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
ClearAll[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
Module[{first, second},
  first[_] := {};
  second[_] := {};
  pair /: new[pair[]] := pair[Unique[]];
  pair /: pair[tag_].delete[] := (first[tag] =.; second[tag] =.);
  pair /: pair[tag_].setFirst[value_] := first[tag] = value;
  pair /: pair[tag_].getFirst[] := first[tag];
  pair /: pair[tag_].setSecond[value_] := second[tag] = value;
  pair /: pair[tag_].getSecond[] := second[tag];
  Format[pair[x_Symbol]] := "pair[" <> ToString[Hash[x]] <> "]";
];
Protect[pair, setFirst, getFirst, setSecond, getSecond, new, delete]; 

Вот как вы можете использовать это:

pr = new[pair[]];
pr.setFirst[10];
pr.setSecond[20];
{pr.getFirst[], pr.getSecond[]}

{10, 20}

Создание списка новых парных объектов:

pairs = Table[new[pair[]], {10}]

{"pair[430427975]", "pair[430428059]", "pair[430428060]", "pair[430428057]",
"pair[430428058]", "pair[430428063]", "pair[430428064]", "pair[430428061]", 
"pair[430428062]", "pair[430428051]"}

Установка полей:

Module[{i},
 For[i = 1, i <= 10, i++,
  pairs[[i]].setFirst[10*i];
  pairs[[i]].setSecond[20*i];]]

Проверка полей:

#.getFirst[] & /@ pairs

{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

#.getSecond[] & /@ pairs

{20, 40, 60, 80, 100, 120, 140, 160, 180, 200} 

В упомянутом мной посте есть более подробное обсуждение. Одна большая проблема для "объектов", создаваемых таким образом, заключается в том, что для них не существует автоматической сборки мусора, что может быть одной из основных причин, по которой расширения ООП, реализованные в самом Mathematica верхнего уровня, действительно не взлетели.

Есть несколько расширений ООП для Mathematica, таких как classes.m Послание Романа Мейдера (источник находится в его книге "Mathematica Programmer"), Objectica коммерческий пакет и ряд других. Но до тех пор, пока сама Mathematica не предоставит эффективные механизмы (возможно, основанные на каком-либо механизме указателей или ссылок) для построения изменяемых структур данных (если это когда-либо произойдет), вероятно, будет существенное снижение производительности, связанное с реализациями таких структур данных верхнего уровня. в мма. Кроме того, поскольку mma основана на неизменности как одной из основных идей, сделать изменяемые структуры данных не очень легко соответствуют другим идиомам программирования Mathematica.

РЕДАКТИРОВАТЬ

Вот простая реализация дерева состояний с сохранением структуры в соответствии с примером выше:

Module[{parent, children, value},
  children[_] := {};
  value[_] := Null;
  node /: new[node[]] := node[Unique[]];
  node /: node[tag_].getChildren[] := children[tag];
  node /: node[tag_].addChild[child_node, index_] := 
        children[tag] = Insert[children[tag], child, index];
  node /: node[tag_].removeChild[index_] := 
        children[tag] = Delete[children[tag], index];
  node /: node[tag_].getChild[index_] := children[tag][[index]];
  node /: node[tag_].getValue[] := value[tag];
  node /: node[tag_].setValue[val_] := value[tag] = val;
];

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

In[68]:= root = new[node[]]

Out[68]= node[$7]

In[69]:= root.addChild[new[node[]], 1]

Out[69]= {node[$8]}

In[70]:= root.addChild[new[node[]], 2]

Out[70]= {node[$8], node[$9]}

In[71]:= root.getChild[1].addChild[new[node[]], 1]

Out[71]= {node[$10]}

In[72]:= root.getChild[1].getChild[1].setValue[10]

Out[72]= 10

In[73]:= root.getChild[1].getChild[1].getValue[]

Out[73]= 10

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

Answer 2

Я использовал mathematica в основном в качестве рабочего места для математики и для написания сравнительно небольших специальных программ.

Mathematica действительно превосходна в этом.

Какой подход вы использовали в отношении структур данных? Постепенно разрабатываете свой собственный пакет утилит?

Я избегаю создавать свои собственные структуры данных в Mathematica, потому что он не может эффективно их обрабатывать. В частности, общие структуры данных в Mathematica, как правило, в 10-1000 раз медленнее, чем в других местах, что значительно ограничивает их практическую полезность. Например, Mathematica в 100 раз медленнее, чем F#, при расчете диапазона глубин в красно-черном дереве.

Логическое программирование со списками является одним из примеров, когда Mathematica обычно на несколько порядков медленнее, чем другие скомпилированные языки. Следующая программа Mathematica использует связанные списки для решения проблемы n-queens:

safe[{x0_, y0_}][{x1_, y1_}] := 
 x0 != x1 && y0 != y1 && x0 - y0 != x1 - y1 && x0 + y0 != x1 + y1

filter[_, {}] := {}
filter[p_, {h_, t_}] := If[p[h], {h, filter[p, t]}, filter[p, t]]

search[n_, nqs_, qs_, {}, a_] := If[nqs == n, a + 1, a]
search[n_, nqs_, qs_, {q_, ps_}, a_] := 
 search[n, nqs, qs, ps, 
  search[n, nqs + 1, {q, qs}, filter[safe[q], ps], a]]

ps[n_] := 
 Fold[{#2, #1} &, {}, Flatten[Table[{i, j}, {i, n}, {j, n}], 1]]

solve[n_] := search[n, 0, {}, ps[n], 0]

Вот эквивалент F#:

let safe (x0, y0) (x1, y1) =
  x0<>x1 && y0<>y1 && x0-y0<>x1-y1 && x0+y0<>x1+y1

let rec filter f = function
  | [] -> []
  | x::xs -> if f x then x::filter f xs else filter f xs

let rec search n nqs qs ps a =
  match ps with
  | [] -> if nqs=n then a+1 else a
  | q::ps ->
      search n (nqs+1) (q::qs) (filter (safe q) ps) a
      |> search n nqs qs ps

let ps n =
  [ for i in 1..n do
      for j in 1..n do
        yield i, j ]

let solve n = search n 0 [] (ps n) 0

solve 8

Решение проблемы 8 ферзей занимает 10,5 с с помощью Mathematica и 0,07 с с помощью F#. Таким образом, F# в 150 раз быстрее, чем Mathematica в этом случае.

Вопрос переполнения стека Mathematica "связанные списки" и производительность дают более экстремальный пример. Наивный перевод этого кода Mathematica на F# дает эквивалентную программу, которая работает в 4000-20000 раз быстрее, чем Mathematica:

let rand = System.Random()
let xs = List.init 10000 (fun _ -> rand.Next 100)
Array.init 100 (fun _ ->
  let t = System.Diagnostics.Stopwatch.StartNew()
  ignore(List.length xs)
  t.Elapsed.TotalSeconds)

В частности, Mathematica занимает от 0,156 до 16 с, чтобы выполнить одну итерацию, тогда как F# занимает от 42 до 86 мкс.

Если я действительно хочу остаться в Mathematica, тогда я включаю все, что я делаю, в горстку встроенных структур данных Mathematica, например Dispatch,