wolfram mathematica - tutorial - Mathematica “listas enlazadas” y performance.

wolfram mathematica online

Question

En Mathematica, creo listas enlazadas individualmente así:

toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]];
fromLinkedList[ll_pair] := List @@ Flatten[ll];
emptyQ[pair[]] := True;
emptyQ[_pair] := False; 

El uso del pair símbolos para las celdas de contras tiene la ventaja de que Flatten funciona de manera segura incluso si las listas contienen listas de estilo Mathematica, y le permite definir una notación personalizada utilizando MakeExpression / MakeBoxes , lo que hace que todo sea mucho más agradable. Para evitar tener que jugar con $IterationLimit , escribí funciones para trabajar con estas listas usando While loops o NestWhile lugar de usar recursión. Naturalmente, quería ver qué enfoque sería más rápido, así que escribí dos candidatos para poder verlos pelear:

nestLength[ll_pair] :=
With[{step = {#[[1, -1]], #[[-1]] + 1} &},
Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];
whileLength[ll_pair] :=
Module[{result = 0, current = ll},
While[! emptyQ@current,
current = current[[2]];
++result];
result];

Los resultados fueron muy extraños. whileLength las funciones en listas enlazadas de longitud 10000, y whileLength fue generalmente un 50% más rápido, alrededor de 0.035 segundos hasta los nestLength segundos de nestLength . Sin embargo, ocasionalmente whileLength tomaría unos ~ 4 segundos. Pensé que podría haber algún comportamiento de almacenamiento en caché, así que comencé a generar listas nuevas y aleatorias para verificar, y whileLength que whileLength no sería necesariamente lento en la primera ejecución con una nueva lista; podría tomar docenas de veces para ver la desaceleración, pero luego no volvería a ocurrir (al menos no para las 200 carreras que estaba tratando con cada lista).

¿Qué podría estar pasando?

Para referencia, la función que utilicé para probar es esta:

getTimes[f_, n_] :=
With[{ll = toLinkedList@RandomInteger[100, 10000]},
Table[Timing[f@ll], {n}][[All, 1]]]

EDIT: me olvidé de mencionar la versión anterior; Conseguí estos resultados con Mathematica 8.

EDITAR el segundo: cuando leí la respuesta de Daniel Lichtblau , me di cuenta de que mis tiempos para carreras "típicas" omitían un 0 inicial. Se ha corregido.

EDITE el tercero: Creo que Leonid Shifrin tiene razón al asociar el problema con el Module ; Puedo obtener el mismo tipo de comportamiento de la versión basada en NestWhile reemplazando el With con un Module :

nestModuleLength[ll_pair] :=
Module[{step = {#[[1, -1]], #[[-1]] + 1} &},
Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];
In[15]:= Select[getTimes[nestModuleLength, 100], # > 3 &]
Out[15]= {3.797}

Answer 1

Los siguientes ejemplos dan resultados típicos.

Un ejemplo lento en una carrera de longitud 20.

In[18]:= getTimes[whileLength, 20]
Out[18]= {0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, /
0.031, 0.047, 0.032, 0.031, 0.031, 3.547, 0.047, 0.031, 0.031, 0.032, /
0.031, 0.031}

Observo de pasada que los tiempos son ~ 10 veces más rápidos que en la publicación original, excepto en los casos lentos que son comparables. No estoy seguro de lo que explica esa diferencia en las proporciones.

No hay ejemplos lentos.

In[17]:= getTimes[nestLength, 20]
Out[17]= {0.047, 0.047, 0.062, 0.047, 0.047, 0.062, 0.047, 0.047, /
0.047, 0.063, 0.046, 0.047, 0.047, 0.063, 0.047, 0.046, 0.047, 0.063, /
0.047, 0.047}

Un ejemplo lento en una carrera de longitud 100.

In[19]:= getTimes[whileLength, 100]
Out[19]= {0.031, 0.031, 0.031, 0.032, 0.031, 3.594, 0.047, 0.031, /
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, /
0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.047, 0.031, 0.031, /
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, /
0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, /
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.031, /
0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.032, /
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.046, 0.032, /
0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.032, 0.031, /
0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.031, 0.032, 0.031, /
0.031, 0.031}

Mathematica implementa, imperfectamente, lo que se llama "evaluación infinita". Es decir, una expresión reevalúa hasta que deja de cambiar. Para hacer esto razonablemente rápido, hay varias optimizaciones que intentan cortocircuitar el proceso siempre que sea posible.

En algunos casos, esto puede ser difícil de discernir (debido a un efecto similar a las colisiones de hash), y las expresiones pueden ser reevaluadas innecesariamente. Las expresiones profundamente anidadas tienden a ser el peor de los casos para esto. Tenemos un código adicional que a menudo abordará esto incluso en casos de colisiones.

El culpable en este caso es exactamente este código que intenta determinar rápidamente si una expresión requiere una reevaluación. Es peculiar, pero posiblemente una pista (para alguien) de que esto sucede como máximo una vez en una carrera dentro de ese bucle While. Entonces, algo sucede en los casos malos que previene la recurrencia mientras está dentro del mismo tiempo.

Hubo un tiempo en que estaba familiarizado con el código de detección de reevaluación, después de haber escrito una parte de él. Pero fue reescrito para la versión 8. Así que incluso después de ver este comportamiento subóptimo en un depurador, es para mí algo misterioso. Sobre todo lo que puedo decir ahora es que presenté un informe de error.

Como observó Leonid Shifrin, los símbolos con el atributo de HoldAllComplete son inmunes a este problema. Entonces, usar ese atributo puede ser beneficioso para este tipo de código.

Daniel Lichtblau Wolfram Research

Answer 2

Parece que está relacionado con el módulo de gestión de memoria de símbolos locales.

Voy a mostrar la serie de tiempos de algunas carreras. Cada ejecución da, por supuesto, un gráfico único, pero he comprobado la "coherencia" entre las ejecuciones. Mira:

whileLength[l2_pair] :=
Module[{result = 0}, current = l2;
While[! emptyQ@current, current = current[[2]];
++result];
result]; 

da las siguientes series de tiempo:

Mientras usa solo símbolos globales:

whileLength[l2_pair] :=
Module[{}, result = 0; current = l2;
While[! emptyQ@current, current = current[[2]];
++result];
result];

da:

Answer 3

Un descargo de responsabilidad: lo siguiente es una especulación. Esto parece estar relacionado con la búsqueda de UpValues . Parece que esto se ha optimizado para las variables globales (de modo que el sistema omita este paso cuando puede determinar que puede hacerlo), pero no para las variables locales generadas por el Module . Para probar esto, asigne el atributo HoldAllComplete al pair , y el efecto desaparecerá (desde entonces, los UpValues no se verifican current ):

SetAttributes[pair, HoldAllComplete];
In[17]:= ll = toLinkedList@RandomInteger[100, 10000];
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]]
Out[18]= 0.047

HTH