"listas enlazadas" Mathematica y desempeño

Question

En Mathematica, que crear listas ligadas sencillas de este modo:

toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]]; 

fromLinkedList[ll_pair] := List @@ Flatten[ll]; 

emptyQ[pair[]] := True; 
emptyQ[_pair] := False;  

Usando el símbolo pair de las cons cells tiene la ventaja de Flatten trabajar con seguridad incluso si las listas contienen Mathematica- estilo List s, y le permite definir notación personalizada usando MakeExpression/MakeBoxes, que hace que todo sea mucho más agradable. Para evitar tener que perder el tiempo con $IterationLimit, escribí funciones para trabajar con estas listas usando While bucles o NestWhile en lugar de usar recursión. Naturalmente, yo quería ver qué enfoque sería más rápido, así que escribí dos candidatos para que pudiera ver 'em luchar:

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ña. Probé las funciones en listas vinculadas de longitud 10000, y whileLength fue generalmente un 50% más rápido, aproximadamente 0.035 segundos a nestLength de 0.055 segundos. Sin embargo, de vez en cuando whileLength tomaría aproximadamente ~ 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 no necesariamente sería lento en la primera ejecución con una nueva lista; podría tomar docenas de veces ver la desaceleración, pero luego no volvería a ocurrir (al menos no para las 200 carreras que estaba probando con cada lista).

¿Qué podría estar pasando?

Como referencia, la función que he usado para las pruebas es la siguiente:

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

EDIT: me he olvidado de mencionar la versión anterior; Tengo estos resultados con Mathematica 8.

editar el segundo: Cuando leí Daniel Lichtblau's answer, me di cuenta de que mis tiempos de carreras "típicos" omiten una de las principales 0. Se ha fijado.

EDITAR el tercero: Creo que Leonid Shifrin es correcto asociar el problema con 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 ejemplos siguientes dan resultados típicos.

Un ejemplo lento en un recorrido 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} 

Noto de paso que los tiempos son ~ 10x más rápidos que en la publicación original, excepto en los casos lentos que son comparables. No estoy seguro de qué es 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 longitud 100 de ejecución.

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 se vuelve a evaluar hasta que deja de cambiar. Para que esto sea 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 hash), y las expresiones pueden ser innecesariamente reevaluadas. Las expresiones profundamente anidadas tienden a ser el peor caso para esto. Tenemos más código que a menudo abordará estos casos 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) que esto suceda a lo sumo una vez en una carrera dentro de ese ciclo While. Entonces sucede algo en los casos malos que previene la recurrencia mientras que dentro del mismo tiempo.

En un momento estaba familiarizado con el código de detección de reevaluación, habiendo escrito una porción de él. Pero fue reescrito para la versión 8. Por lo tanto, incluso después de ver este comportamiento subóptimo en un depurador, es algo así como un misterio para mí. Sobre todo lo que puedo decir ahora es que archivé un informe de error.

Como observó Leonid Shifrin, los símbolos con 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 la gestión de memoria Módulo símbolos locales.

Voy a mostrar la serie de tiempos de algunas carreras. Cada ejecución da, por supuesto, un argumento único, pero verifiqué la "consistencia" entre las ejecuciones.Mira:

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

dicta la siguiente serie Tiempo:

Durante el uso de sólo 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: la siguiente es una especulación. Esto parece estar relacionado con la búsqueda de UpValues. Parece que esto se ha optimizado para variables globales (por lo que el sistema omite este paso cuando puede determinar que puede hacerlo), pero no para Module - variables locales generadas. Para probar esto, asignar HoldAllComplete atributo a pair, y desaparece el efecto (desde entonces, UpValues no se comprueban para current):

SetAttributes[pair, HoldAllComplete]; 

In[17]:= ll = toLinkedList@RandomInteger[100, 10000]; 
Max[Table[Timing[whileLength[ll]], {1000}][[All, 1]]] 

Out[18]= 0.047 

HTH