lisp - vertical - graficar vectores en mathematica

Diferencia de rendimiento entre funciones y coincidencia de patrones en Mathematica

Question

Entonces Mathematica es diferente de otros dialectos de lisp porque difumina las líneas entre las funciones y las macros. En Mathematica, si un usuario quisiera escribir una función matemática, es probable que usen la coincidencia de patrones como f[x_]:= x*x lugar de f=Function[{x},x*x] aunque ambos devolverán el mismo resultado cuando se les llame con f[x] . Mi entendimiento es que el primer enfoque es algo equivalente a una macro clara y en mi experiencia se ve favorecida por la sintaxis más concisa.

Entonces, tengo dos preguntas, ¿hay una diferencia de rendimiento entre la ejecución de funciones y el enfoque de patrón / macro? Aunque una parte de mí no se sorprendería si las funciones se transformaran realmente en alguna versión de macros para permitir que se implementen funciones como Listable .

La razón por la que me preocupo por esta pregunta se debe a la reciente serie de preguntas (1) (2) sobre cómo tratar de detectar errores de Mathematica en grandes programas. Si la mayoría de los cálculos se definieron en términos de Funciones, me parece que hacer un seguimiento del orden de evaluación y dónde se originó el error sería más fácil que tratar de detectar el error después de que la entrada haya sido reescrita por la aplicación sucesiva de macros /patrones.

Answer 1

Mi entendimiento es que el primer enfoque es algo equivalente a una macro clara y en mi experiencia se ve favorecida por la sintaxis más concisa.

Realmente no. Mathematica es un término reescritor, al igual que las macros de Lisp.

Entonces, tengo dos preguntas, ¿hay una diferencia de rendimiento entre la ejecución de funciones y el enfoque de patrón / macro?

Sí. Tenga en cuenta que nunca está realmente "ejecutando funciones" en Mathematica. Solo está aplicando reglas de reescritura para cambiar una expresión por otra.

Considere mapear la función Sqrt sobre una matriz empaquetada de números de punto flotante. La solución más rápida en Mathematica es aplicar la función Sqrt directamente a la matriz empaquetada porque implementa exactamente lo que queremos y está optimizado para este caso especial:

In[1] := N@Range[100000];

In[2] := Sqrt[xs]; // AbsoluteTiming

Out[2] = {0.0060000, Null}

Podríamos definir una regla de reescritura global que tenga los términos de la forma sqrt[x] reescrita en Sqrt[x] manera que se calcule la raíz cuadrada:

In[3] := Clear[sqrt];
         sqrt[x_] := Sqrt[x];
         Map[sqrt, xs]; // AbsoluteTiming

Out[3] = {0.4800007, Null}

Tenga en cuenta que esto es ~ 100 × más lento que la solución anterior.

Alternativamente, podríamos definir una regla de reescritura global que reemplace el símbolo sqrt con una función lambda que invoque Sqrt :

In[4] := Clear[sqrt];
         sqrt = Function[{x}, Sqrt[x]];
         Map[sqrt, xs]; // AbsoluteTiming

Out[4] = {0.0500000, Null}

Tenga en cuenta que esto es ~ 10 × más rápido que la solución anterior.

¿Por qué? Debido a que la segunda solución lenta está buscando la regla de reescritura sqrt[x_] :> Sqrt[x] en el bucle interno (para cada elemento de la matriz) mientras que la tercera solución rápida busca el valor Function[...] de la simboliza sqrt una vez y luego aplica esa función lambda repetidamente. En contraste, la primera solución más rápida es un bucle llamado sqrt escrito en C. Por lo tanto, buscar las reglas de reescritura globales es extremadamente costoso y la reescritura de términos es costosa.

Si es así, ¿por qué es rápido Sqrt ? Puede esperar una ralentización de 2 × en lugar de 10 × porque hemos reemplazado una búsqueda de Sqrt con dos búsquedas de sqrt y Sqrt en el bucle interno, pero esto no es así porque Sqrt tiene el estado especial de ser una función incorporada que coincidirán en el núcleo del propio reescritor de términos de Mathematica en lugar de hacerlo a través de la tabla de reescritura global de propósito general.

Otras personas han descrito diferencias de rendimiento mucho más pequeñas entre funciones similares. Creo que las diferencias de rendimiento en esos casos son solo pequeñas diferencias en la implementación exacta de los aspectos internos de Mathematica. El mayor problema con Mathematica es la tabla de reescritura global. En particular, aquí es donde Mathematica se aparta de los intérpretes tradicionales de término.

Puedes aprender mucho sobre el rendimiento de Mathematica escribiendo mini implementaciones de Mathematica. En este caso, las soluciones anteriores podrían compilarse a (por ejemplo) F #. La matriz se puede crear de esta manera:

> let xs = [|1.0..100000.0|];;
...

La función sqrt incorporada se puede convertir en un cierre y se puede map a la función de map esta manera:

> Array.map sqrt xs;;
Real: 00:00:00.006, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
...

Esto toma 6 ms al igual que Sqrt[xs] en Mathematica. Pero eso es de esperar porque este código ha sido compilado JIT a código de máquina por .NET para una evaluación rápida.

Buscar reglas de reescritura en la tabla de reescritura global de Mathematica es similar a buscar el cierre en un diccionario con el nombre de su función. Este diccionario se puede construir así en F #:

> open System.Collections.Generic;;
> let fns = Dictionary<string, (obj -> obj)>(dict["sqrt", unbox >> sqrt >> box]);;

Esto es similar a la estructura de datos de DownValues en Mathematica, excepto que no estamos buscando varias reglas resultantes para que la primera coincida con los argumentos de la función.

El programa se convierte entonces en:

> Array.map (fun x -> fns.["sqrt"] (box x)) xs;;
Real: 00:00:00.044, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0
...

Tenga en cuenta que obtenemos una degradación del rendimiento similar a 10 × debido a la búsqueda de tabla hash en el bucle interno.

Una alternativa sería almacenar los DownValues asociados con un símbolo en el símbolo mismo para evitar la búsqueda de la tabla hash.

Incluso podemos escribir un reescritor de término completo en solo unas pocas líneas de código. Los términos pueden expresarse como valores del siguiente tipo:

> type expr =
    | Float of float
    | Symbol of string
    | Packed of float []
    | Apply of expr * expr [];;

Tenga en cuenta que Packed implementa las listas empaquetadas de Mathematica, es decir, matrices sin caja.

La siguiente función de init construye una List con n elementos utilizando la función f , devolviendo un Packed si cada valor devuelto era un Float o una Apply(Symbol "List", ...) más general Apply(Symbol "List", ...) contrario:

> let init n f =
    let rec packed ys i =
      if i=n then Packed ys else
        match f i with
        | Float y ->
            ys.[i] <- y
            packed ys (i+1)
        | y ->
            Apply(Symbol "List", Array.init n (fun j ->
              if j<i then Float ys.[i]
              elif j=i then y
              else f j))
    packed (Array.zeroCreate n) 0;;
val init : int -> (int -> expr) -> expr

La siguiente función de rule usa la coincidencia de patrones para identificar expresiones que puede entender y las reemplaza con otras expresiones:

> let rec rule = function
    | Apply(Symbol "Sqrt", [|Float x|]) ->
        Float(sqrt x)
    | Apply(Symbol "Map", [|f; Packed xs|]) ->
        init xs.Length (fun i -> rule(Apply(f, [|Float xs.[i]|])))
    | f -> f;;
val rule : expr -> expr

Tenga en cuenta que el tipo de esta función expr -> expr es característico de la reescritura de términos: la reescritura reemplaza las expresiones con otras expresiones en lugar de reducirlas a valores.

Nuestro programa ahora puede ser definido y ejecutado por nuestro reescritor de términos personalizados:

> rule (Apply(Symbol "Map", [|Symbol "Sqrt"; Packed xs|]));;
Real: 00:00:00.049, CPU: 00:00:00.046, GC gen0: 24, gen1: 0, gen2: 0

¡Hemos recuperado el rendimiento de Map[Sqrt, xs] en Mathematica!

Incluso podemos recuperar el rendimiento de Sqrt[xs] agregando una regla apropiada:

| Apply(Symbol "Sqrt", [|Packed xs|]) ->
    Packed(Array.map sqrt xs)

Escribí un artículo sobre la reescritura de términos en F # .

Answer 2

Algunas medidas

Basado en la respuesta de @gdelfino y los comentarios de @rcollyer, hice este pequeño programa:

j = # # + # # &;
g[x_] := x x + x x ;
h = Function[{x}, x x + x x ];


anon = Table[Timing[Do[ # # + # # &[i], {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
jj   = Table[Timing[Do[ j[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
gg   = Table[Timing[Do[ g[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];
hh   = Table[Timing[Do[ h[i],           {i, k}]][[1]], {k, 10^5, 10^6, 10^5}];

ListLinePlot[ {anon,   jj,    gg,   hh}, 
 PlotStyle -> {Black, Red, Green, Blue},
 PlotRange -> All]

Los resultados son, al menos para mí, muy sorprendentes:

¿Alguna explicación? Por favor, siéntase libre de editar esta respuesta (los comentarios son un desastre para texto largo)

Editar

Probado con la función de identidad f [x] = x para aislar el análisis de la evaluación real. Resultados (mismos colores):

Nota: los resultados son muy similares a este gráfico para funciones constantes (f [x]: = 1);

Answer 3

La coincidencia de patrones parece más rápida:

In[1]:= g[x_] := x*x
In[2]:= h = Function[{x}, x*x];

In[3]:= Do[h[RandomInteger[100]], {1000000}] // Timing
Out[3]= {1.53927, Null}

In[4]:= Do[g[RandomInteger[100]], {1000000}] // Timing
Out[4]= {1.15919, Null}

La coincidencia de patrones también es más flexible, ya que le permite sobrecargar una definición:

In[5]:= g[x_] := x * x
In[6]:= g[x_,y_] := x * y

Para funciones simples que puede compilar para obtener el mejor rendimiento:

In[7]:= k[x_] = Compile[{x}, x*x]
In[8]:= Do[k[RandomInteger[100]], {100000}] // Timing
Out[8]= {0.083517, Null}

Answer 4

La forma en que entiendo Mathematica es que es un motor de reemplazo de búsqueda gigante. Todas las funciones, variables y otras asignaciones se almacenan esencialmente como reglas y, durante la evaluación, Mathematica pasa por esta base de reglas globales y las aplica hasta que la expresión resultante deja de cambiar.

De ello se deduce que cuantas menos veces tenga que revisar la lista de reglas, más rápida será la evaluación. Mirando lo que sucede usando Trace (usando la función gdelfino de gdelfino )

In[1]:= Trace@(#*#)&@x
Out[1]= {x x,x^2}
In[2]:= Trace@g@x
Out[2]= {g[x],x x,x^2}
In[3]:= Trace@h@x
Out[3]= {{h,Function[{x},x x]},Function[{x},x x][x],x x,x^2}

queda claro por qué las funciones anónimas son más rápidas y por qué el uso de Function introduce una sobrecarga adicional sobre un simple SetDelayed . Recomiendo mirar la introduction del excelente libro de Leonid Shifrin, donde se explican estos conceptos con cierto detalle.

En ocasiones, he construido una tabla de Dispatch todas las funciones que necesito y la apliqué manualmente a mi expresión inicial. Esto proporciona un aumento significativo de la velocidad en comparación con la evaluación normal, ya que ninguna de las funciones incorporadas de Mathematica debe coincidir con mi expresión.

Answer 5

Puede usar la función recordSteps en la answer anterior para ver qué hace Mathematica realmente con las funciones. Lo trata igual que cualquier otra cabeza. IE, supongamos que tienes lo siguiente

f = Function[{x}, x + 2];
f[2]

Primero transforma f [2] en

Function[{x}, x + 2][2]

En el siguiente paso, x+2 se transforma en 2+2 . Esencialmente, la evaluación de "Funciones" se comporta como una aplicación de reglas de coincidencia de patrones, por lo que no debería sorprender que no sea más rápido.

Puedes pensar en todo en Mathematica como una expresión, donde la evaluación es el proceso de reescritura de partes de la expresión en una secuencia predefinida , esto se aplica a la función como a cualquier otra cabeza.