Structure de données arborescente en Mathematica

Question

J'ai utilisé mathematica principalement comme un banc de travail mathématique et pour écrire des programmes ad hoc relativement petits. Je suis cependant en train de concevoir un système que j'ai l'intention de programmer en Mathematica. J'ai besoin de stocker des données dans un arbre, et de rechercher et de parcourir cet arbre. Bien que je sache comment mettre en œuvre un arbre, je préfère un code standard et testé. J'ai cherché à savoir quelles sortes de paquets existaient pour les structures de données de base sur le wiki des utilisateurs de Mathematica. Je n'en ai trouvé aucun, bien qu'il y ait un petit exemple dans la documentation de Mathematica.

J'en viens maintenant à ma ou mes questions :

1. Existe-t-il un paquet ( open source ) pour les structures de données disponible quelque part ?

2. Quelle approche avez-vous utilisée en ce qui concerne les structures de données ? Développer progressivement votre propre paquet utilitaire ?

( Pas une question, juste une remarque. Peut-être que... le manque de paquets open source (nombreux et disponibles) est la raison pour laquelle Mathematica n'a pas l'élan qu'il mérite. Un problème de poule et d'oeuf, j'en ai peur. )

Answer 1

Dans Mathematica, la plupart de vos actions sont basées sur des expressions. Les expressions ont naturellement une structure arborescente. Pour les traversées en profondeur (qui sont probablement les plus courantes), vous pouvez alors utiliser des fonctions telles que Scan , Map , Cases etc. La différence par rapport aux langages plus traditionnels est qu'il n'existe pas de moyen simple de préserver l'identité d'un nœud individuel dans un arbre d'expression, puisqu'il n'y a pas de pointeurs en Mathematica. En outre, de nombreuses opérations sur les expressions qui sont idiomatiques en Mathematica copieraient l'expression entière alors que vous n'avez besoin de la modifier qu'à quelques endroits, car les expressions sont immuables.

L'utilisation d'expressions Mathematica immuables sous forme d'arbres présente encore plusieurs avantages. L'un d'eux est que, comme elles sont immuables, il est facile de comprendre ce qu'elles stockent en les regardant simplement (l'état et le comportement ne sont pas mélangés). Un autre avantage est qu'il existe des fonctions efficaces et génériques telles que Map , MapIndexed ou Scan qui les traversent. Par exemple, le modèle de conception visiteur est invisible - c'est juste Map[f,tree,Infinity] intégrés dans la langue. Il existe également des fonctions intégrées telles que Cases , Replace , ReplaceAll etc., qui permettent d'écrire un code très concis et déclaratif pour déstructurer les arbres, trouver des morceaux d'arbres avec une certaine syntaxe ou satisfaisant une certaine condition, etc. Puisque les arbres ne sont pas limités à être construits uniquement à partir de listes et à être construits à partir de différentes têtes, on peut effectivement utiliser ceci pour écrire un code de traitement d'arbre très concis. Enfin, la liberté de construire très facilement n'importe quelle structure d'arbre que vous voulez rend beaucoup plus facile la réalisation d'expériences et de prototypes, dans l'esprit de la programmation exploratoire et ascendante ce qui permet de raccourcir le cycle de développement et, en fin de compte, d'obtenir de meilleures conceptions.

Cela dit, vous pouvez certainement mettre en œuvre une structure de données arborescente "étatique" (mutable). La véritable raison pour laquelle cela n'a pas encore été fait est, je pense, le manque de performance associé à la construction, la modification et la traversée d'un tel arbre, puisqu'il subira un processus d'évaluation symbolique complet à chaque étape (cf. ce pour plus de détails à ce sujet). Pour 2 exemples de la façon dont, par exemple, un arbre de recherche binaire peut être utilisé dans le contexte de Mathematica pour un code assez efficace, voir mes posts ici (cadre symbolique générique) et ici (dans le contexte du code compilé). Pour les moyens généraux de construire des structures de données de manière idiomatique dans Mathematica, je recommande les livres de Roman Maeder : "Programming in Mathematica", "Mathematica programmer I&II", et surtout "Computer Science in Mathematica". Dans ce dernier, il explique en détail comment implémenter un arbre de recherche binaire en Mathematica. EDIT Comme @Simon l'a mentionné, la conférence de @Daniel Lichtblau est également une excellente ressource, qui montre comment construire des structures de données et les rendre efficaces.

En ce qui concerne les moyens généraux d'implémenter des structures de données dans Mathematica qui incorporeraient un certain état, voici un exemple simple extrait de mon post dans ce Le fil Mathgroup - il met en œuvre une structure de données "paire".

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]; 

Voici comment vous pourriez l'utiliser :

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

{10, 20}

Création d'une liste de nouveaux objets de paire :

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]"}

Définition des champs :

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

Vérification des champs :

#.getFirst[] & /@ pairs

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

#.getSecond[] & /@ pairs

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

Dans le post que j'ai mentionné, il y a une discussion plus détaillée. Un gros problème pour les "objets" créés de cette manière est qu'il n'y a pas de collecte automatique des déchets pour eux, ce qui peut être l'une des principales raisons pour lesquelles les extensions de la POO mises en œuvre dans Mathematica de haut niveau n'ont pas vraiment décollé.

Il existe plusieurs extensions de la POO pour Mathematica, telles que l'application classes.m par Roman Maeder (la source se trouve dans son livre "Mathematica Programmer"), le paquet Objectica paquet commercial, et plusieurs autres. Mais jusqu'à ce que Mathematica lui-même fournisse des mécanismes efficaces (peut-être basés sur une sorte de pointeur ou de mécanisme de référence) pour construire des structures de données mutables (si cela se produit un jour), il y aura probablement un gros problème de performance associé aux implémentations de haut niveau de telles structures de données dans mma. De plus, comme mma est basé sur l'immuabilité comme l'une des idées principales, il n'est pas très facile de faire en sorte que les structures de données mutables s'adaptent bien aux autres idiomes de la programmation Mathematica.

EDIT

Voici une mise en œuvre d'un arbre à état simple selon les lignes de l'exemple ci-dessus :

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;
];

Quelques exemples d'utilisation :

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

Pour un exemple non trivial d'utilisation de cette structure de données arborescente mutable, voir ce de mon poste. Il confronte également cette méthode à celle qui réutilise plus fortement les structures de données et fonctions natives de Mathematica, et illustre bien les points abordés au début de ce billet.

Answer 2

J'ai utilisé mathematica principalement comme banc de travail mathématique et pour écrire des programmes ad-hoc relativement petits.

Mathematica excelle vraiment dans ce domaine.

Quelle approche avez-vous utilisée en ce qui concerne les structures de données ? Développer progressivement votre propre paquet utilitaire ?

J'évite de créer mes propres structures de données dans Mathematica car il ne peut pas les gérer efficacement. Plus précisément, les structures de données générales ont tendance à être 10 à 1000 fois plus lentes dans Mathematica qu'ailleurs, ce qui limite considérablement leur utilité pratique. Par exemple, Mathematica est 100 fois plus lent que F# pour calculer l'étendue des profondeurs d'un arbre rouge-noir. .

La programmation logique avec des listes est un exemple où Mathematica est typiquement plus lent de plusieurs ordres de grandeur que d'autres langages compilés. Le programme Mathematica suivant utilise des listes liées pour résoudre le problème des n-reines :

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]

Voici l'équivalent du 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

La résolution du problème des 8 reines prend 10,5 secondes avec Mathematica et 0,07 seconde avec F#. F# est donc 150 fois plus rapide que Mathematica dans ce cas.

La question de Stack Overflow Les "listes liées" de Mathematica et les performances donne un exemple plus extrême. La traduction naïve de ce code Mathematica en F# donne un programme équivalent qui s'exécute entre 4 000 et 200 000 fois plus vite que 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)

Plus précisément, Mathematica prend de 0,156s à 16s pour effectuer une seule itération alors que F# prend de 42µs à 86µs.

Si je veux vraiment rester dans Mathematica, j'intègre tout ce que je fais dans les quelques structures de données intégrées de Mathematica, par exemple Dispatch .