wolfram mathematica - variable - Estructura de datos de árbol en Mathematica

mathematica plot title

Question

He utilizado mathematica principalmente como un banco de trabajo de matemáticas y para escribir programas ad-hoc relativamente pequeños. Sin embargo, estoy diseñando un sistema que pretendo programar en Mathematica. Necesito almacenar datos en un árbol, buscar y atravesar el árbol. Aunque sé cómo implementar un árbol, prefiero el código estándar probado. Miré qué tipo de paquetes hay para las estructuras de datos básicos en la wiki de usuarios de Mathematica. No he encontrado ninguno, aunque hay un pequeño ejemplo en la documentación de Mathematica.

Ahora a mi (s) pregunta (s):

1. ¿Hay algún paquete (de código abierto) para las estructuras de datos disponibles en alguna parte?

2. ¿Qué enfoque ha utilizado con respecto a las estructuras de datos? ¿Desarrollando gradualmente su propio paquete de utilidades?

(No es una pregunta, solo un comentario. Tal vez ... la falta de (muchos disponibles) paquetes de código abierto es la razón por la cual Mathematica no tiene el impulso que merece. Un tema de huevo / pollo, me temo).

Answer 1

He utilizado mathematica principalmente como un banco de trabajo de matemáticas y para escribir programas ad-hoc relativamente pequeños.

Mathematica realmente sobresale en esto.

¿Qué enfoque ha utilizado con respecto a las estructuras de datos? ¿Desarrollando gradualmente su propio paquete de utilidades?

Evito crear mis propias estructuras de datos en Mathematica porque no puede manejarlas de manera eficiente. Específicamente, las estructuras de datos generales tienden a ser 10-1,000 veces más lentas en Mathematica que en otros lugares, lo que limita en gran medida su utilidad práctica. Por ejemplo, Mathematica es 100 veces más lenta que F # al calcular el rango de profundidades en un árbol rojo-negro .

La programación lógica con listas es un ejemplo en el que Mathematica suele ser un orden de magnitud más lento que otros lenguajes compilados. El siguiente programa de Mathematica utiliza listas vinculadas para resolver el problema 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]

Aquí está el equivalente 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 resolución del problema de las 8 reinas requiere 10.5 segundos con Mathematica y 0.07 segundos con F #. Entonces F # es 150 veces más rápido que Mathematica en este caso.

La pregunta de Desbordamiento de pila Mathematica "listas vinculadas" y el rendimiento da un ejemplo más extremo. La traducción ingenua de ese código de Mathematica a F # da un programa equivalente que corre entre 4.000 y 200.000 × más rápido que el 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)

Específicamente, Mathematica toma 0.156s a 16s para realizar una única iteración mientras que F # toma 42μs a 86μs.

Si realmente quiero quedarme en Mathematica, me calzador todo lo que estoy haciendo en el puñado de estructuras de datos integradas de Mathematica, por ejemplo, Dispatch .

Answer 2

En Mathematica, la mayoría de lo que haces se basa en expresiones. Las expresiones tienen naturalmente la estructura del árbol. Para recorridos de profundidad primero (que probablemente sean los más comunes), puede usar funciones como Scan , Map , Cases , etc. La diferencia con los lenguajes más tradicionales es que no existe una forma simple de preservar la identidad del nodo individual en una expresión árbol, ya que no hay punteros en Mathematica. Además, muchas operaciones en expresiones que son idiomáticas en Mathematica copiarían la expresión completa cuando solo necesitas modificarla en algunos lugares, porque las expresiones son inmutables.

El uso de expresiones de Mathematica inmutables como árboles todavía tiene varias ventajas. Una es que, como son inmutables, es fácil entender lo que almacenan simplemente observándolos (el estado y el comportamiento no son mixtos). Otra es que existen funciones eficientes y genéricas tales como Map , MapIndexed o Scan , que las atraviesan. Por ejemplo, el patrón de diseño del visitante es invisible ; es simplemente Map[f,tree,Infinity] , integrado en el idioma. Además, hay funciones incorporadas como Cases , Replace , ReplaceAll , etc., que permiten escribir un código muy conciso y declarativo para desestructurar árboles, encontrar árboles con cierta sintaxis o satisfacer alguna condición, etc. Como los árboles no son restringido para que solo se construya a partir de listas y se construya desde diferentes encabezados, uno puede usar esto de manera efectiva para escribir código de procesamiento de árbol muy conciso. Finalmente, la libertad para construir fácilmente cualquier estructura de árbol que desee hace que sea mucho más fácil realizar experimentos y prototipos, en el espíritu de la programación exploratoria y ascendente , lo que acorta el ciclo de desarrollo y, en última instancia, conduce a mejores diseños.

Dicho esto, ciertamente puede implementar una estructura de datos de árbol "con estado" (mutable). La razón real por la que aún no se ha hecho es, sospecho, el golpe de rendimiento asociado con construir, modificar y atravesar tal árbol, ya que se someterá a un proceso de evaluación simbólico completo en cada paso (ver this publicación para más detalles sobre eso ) Para 2 ejemplos de cómo, por ejemplo, un árbol de búsqueda binaria se puede utilizar en el contexto de Mathematica para un código bastante eficiente, vea mis publicaciones here (configuración simbólica genérica) y here (en el contexto del código compilado). Para las formas generales de construir estructuras de datos idiomáticamente en Mathematica, recomiendo libros de Roman Maeder: "Programación en Mathematica", "Programador Mathematica I y II", y especialmente "Informática en Mathematica". En este último, tiene una discusión detallada sobre cómo implementar el árbol de búsqueda binario en Mathematica. EDITAR Como @Simon mencionó, la charla de @Daniel Lichtblau es también un gran recurso, que muestra cómo construir estructuras de datos y hacerlos más eficientes.

En cuanto a las formas generales de implementar estructuras de datos en Mathematica que incorporarían algún estado, aquí hay un ejemplo simple extraído de mi publicación en this hilo de Mathgroup: implementa una estructura de datos "par".

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

Aquí es cómo puedes usarlo:

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

Crear una lista de nuevos objetos de pares:

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

Configurando los campos:

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

Verificando los campos:

#.getFirst[] & /@ pairs
{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
#.getSecond[] & /@ pairs
{20, 40, 60, 80, 100, 120, 140, 160, 180, 200}

En el post que mencioné hay una discusión más detallada. Un gran problema para los "objetos" creados de esta manera es que no existe una recolección automática de basura para ellos, que puede ser una de las razones principales por las que las extensiones OOP implementadas en Mathematica de nivel superior en sí no despegaron realmente.

Hay varias extensiones de OOP para Mathematica, como el paquete classes.m de Roman Maeder (la fuente está en su libro "Mathematica Programmer"), el paquete comercial de Objectica y muchas otras. Pero hasta que Mathematica proporcione mecanismos eficientes (quizás basados ​​en algún tipo de puntero o mecanismo de referencia) para construir estructuras de datos mutables (si esto sucede alguna vez), probablemente habrá un gran impacto de rendimiento asociado con implementaciones de alto nivel de tales estructuras de datos en mma. Además, dado que mma se basa en la inmutabilidad como una de las ideas centrales, no es muy fácil hacer que las estructuras de datos mutables encajen bien con otras expresiones idiomáticas de la programación de Mathematica.

EDITAR

Aquí hay una implementación de árbol con estado escueto a lo largo de las líneas del ejemplo anterior:

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

Algunos ejemplos de uso:

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

Para ver un ejemplo no trivial del uso de esta estructura de datos de árbol mutable, vea this publicación mía. También confronta este método con uno que reutiliza mucho las estructuras y funciones de datos nativas de Mathematica, e ilustra bien los puntos discutidos al comienzo de esta publicación.