Rendimiento en Mathematica

¿Puede hacer algo como la declaración de rendimiento de Python en Mathematica, para crear generadores? Ver p. here para el concepto.Rendimiento en Mathematica

actualización He aquí un ejemplo de lo que quiero decir, para iterar sobre todas las permutaciones, usando solamente O (n) Espacio: (algoritmo como en el libro Algoritmos de Sedgewick):

gen[f_, n_] := Module[{id = -1, val = Table[Null, {n}], visit}, 
    visit[k_] := Module[{t}, 
    id++; If[k != 0, val[[k]] = id]; 
    If[id == n, f[val]]; 
    Do[If[val[[t]] == Null, visit[t]], {t, 1, n}]; 
    id--; val[[k]] = Null;]; 
    visit[0]; 
    ]

Entonces llamarlo se como:

gen[Print,3], la impresión de los 6 permutaciones de longitud 3.

Fuente

2009-07-22 nes1983

FWIW, la forma de hacer iteradores/generadores de Python es bastante inusual. Siempre que tenga algún tipo de abstracción sobre el estado (cierres, clases), puede implementarlos en cualquier lengua. – jrockway

Ah, lindo. Tal vez agregue eso como una respuesta a su propia pregunta (se considera bastante kosher hacer eso). ¿O todavía hay una pregunta sin respuesta aquí? – dreeves

Bueno, necesita pasar explícitamente sus funciones, mientras que el rendimiento de Python se lo imagina y lo hace encajar en el marco. Entonces, no es completamente perfecto. Pero lo suficientemente bueno, de hecho, lo uso ahora. – nes1983

Como he indicado anteriormente, el uso de Compile dará un código más rápido. Usando un algoritmo de fxtbook, el siguiente código genera una partición siguiente en orden lexicográfico:

PermutationIterator[f_, n_Integer?Positive, nextFunc_] := 
Module[{this = Range[n]}, 
    While[this =!= {-1}, f[this]; this = nextFunc[n, this]];]

El código siguiente se supone que ejecutan la versión 8:

ClearAll[cfNextPartition]; 
cfNextPartition[target : "MVM" | "C"] := 
    cfNextPartition[target] = 
    Compile[{{n, _Integer}, {this, _Integer, 1}}, 
    Module[{i = n, j = n, ni, next = this, r, s}, 
    While[Part[next, --i] > Part[next, i + 1], 
     If[i == 1, i = 0; Break[]]]; 
    If[i == 0, {-1}, ni = Part[next, i]; 
     While[ni > Part[next, j], --j]; 
     next[[i]] = Part[next, j]; next[[j]] = ni; 
     r = n; s = i + 1; 
     While[r > s, ni = Part[next, r]; next[[r]] = Part[next, s]; 
     next[[s]] = ni; --r; ++s]; 
     next 
     ]], RuntimeOptions -> "Speed", CompilationTarget -> target 
    ];

Entonces

In[75]:= Reap[PermutationIterator[Sow, 4, cfNextPartition["C"]]][[2, 
    1]] === Permutations[Range[4]] 

Out[75]= True

Este es claramente mejor en rendimiento que la función original gen.

In[83]:= gen[dummy, 9] // Timing 

Out[83]= {26.067, Null} 

In[84]:= PermutationIterator[dummy, 9, cfNextPartition["C"]] // Timing 

Out[84]= {1.03, Null}

El uso de la máquina virtual de Mathematica no es mucho más lento:

In[85]:= PermutationIterator[dummy, 9, 
    cfNextPartition["MVM"]] // Timing 

Out[85]= {1.154, Null}

Por supuesto, esto no es en absoluto la aplicación del código C, sin embargo, proporciona una considerable aceleración sobre el código de nivel superior pura.

Fuente

2011-04-18 16:03:30 Sasha

Puede obtener la velocidad C usando el truco que estaba exponiendo en esta publicación: http://stackoverflow.com/questions/5246330/delete-repeating- list-elements-preservar-orden-de-apariencia/5251034 # 5251034. Si crea un generador para una función compilada 'PermutationIterator', haga lo siguiente:' PermutationIteratorGen [f_, nextFunc_]: = Compile [{{n, _Integer}}, Módulo [{this = Range [n]}, While [this =! = {-1}, f [this]; this = nextFunc [n, this]];], RuntimeOptions -> "Speed", CompilationTarget -> "C", CompilationOptions -> {"InlineCompiledFunctions" -> True, "InlineExternalDefinitions" -> True}] ', continúa ... –

Continuando ... Luego, suponiendo que su función * dummy * puede ser 'Compiled', obtiene otro orden de magnitud speedup:' fn = PermutationIteratorGen [# &, cfNextPartition ["C"]]; fn [9] // Tiempo '. El truco anterior permite efectivamente que las variables de la función compilada adjunta vivan en el código compilado y sean modificadas por la función compilada del llamador, porque al final hacemos la alineación y obtenemos solo una gran función compilada, pero para nosotros se ve más modular . Pero usar 'Sow' u otra función no compilable degradará en gran medida el rendimiento, por lo que casi no hay diferencia entre C y MVM. –

@Leonid Sí, este es un buen punto, y el iterador también se puede escribir a medida para realizar algunas operaciones predeterminadas, omitiendo pasar la función por completo. Lo que quise decir con no C-speed es que está lejos de 130 millones de permutaciones generadas por cita de segundo lugar en el libro de texto. 'fn [11]' toma 9.86 segundos en mi máquina, lo que equivale a 4 millones de permutaciones por segundo. Una mirada a 'CompilePrint [fn]' es instructiva e indicará por qué sucedió eso. – Sasha

probablemente quiere decir la cuestión de ser más general, pero el ejemplo de iteración en permutatio ns como se indica en la página que enlaza a pasa a ser integrado en Mathematica:

Scan[Print, Permutations[{1, 2, 3}]]

El Print no puede ser reemplazado por cualquier función.

Fuente

2009-07-24 19:34:06 dreeves

Bueno, lo que quiero decir con un generador es más parecido al siguiente, que funciona en O (n) memoria, donde necesitas O (n!). gen [f_, n_]: = Módulo [{id = -1, val = Tabla [Nulo, {n}], visita}, visita [k_]: = Módulo [{t}, id ++; Si [k!= 0, val [[k]] = id]; If [id == n, f [val]]; Do [Si [val [[t]] == Null, visite [t]], {t, 1, n}]; id--; val [[k]] = Nulo;]; visita [0]; ] Lo ejecuta así: gen [Imprimir, 3] – nes1983

Respuesta

Cuestiones relacionadas