diferencia de velocidad en hacer una tabla

Question

Estaba leyendo a useful post at WRI blog on improving speed of code, y necesito ayuda para entender esto.

comparar estas velocidades

Timing[ 
tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];  
] 

{0.031, Null} 

y

Timing[ 
a = 1000; 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
] 

{0.422, Null} 

Por lo tanto, es mucho más rápido si se pone el valor real para el límite interior de la propia tabla vs exterior. La explicación para esto, que estoy seguro es correcta, pero necesito ayuda para entender, es que Table se compila si su límite es numérico vs. no, esto es porque sus atributos son HoldAll.

Pero mi pregunta es: ¿Cómo funcionaría lo anterior, porque los límites a Table deben, en un punto, convertirse en numéricos de todos modos? No puedo escribir

Clear[a] 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}] 

Lo anterior da un error.

Así que, para mí, la escritura a=1000 fuera Table vs. dentro, debería haber hecho ninguna diferencia, ya que sin a tener un valor numérico, Table[] no se puede hacer nada. Entonces, la sustitución de a por el número 1000 debe ocurrir en un punto dado por el evaluador antes de que Table[] pueda hacer algo útil, ¿no es así?

En otras palabras, lo que Table debería ver, finalmente, es {i, 1, 1000}, {j, 1, 1000} en ambos casos.

Por lo tanto, la forma en que pensé que esto sucedería es la siguiente:

1. Evaluador reemplaza por a 1000 en los argumentos de la tabla
2. Evaluador llama Table con el resultado, que ahora es todo lo numérico.
3. Table Compila y ahora funciona más rápido.

Pero lo que parece suceder es otra cosa. (debido a HoldAll?)

1. La tabla toma sus argumentos, tal como está. Como tiene HoldAll, entonces ve a y no 1000.
2. No llama a Compilar ya que sus argumentos no son todos los números.
3. Ahora generar una tabla con el límite a, Evaluador evalúa a a 1000
4. se genera la tabla ahora todos los límites son numéricos, pero más lento ahora ya que el código no se compila.

pregunta es: ¿El tipo más arriba de lo que sucede? ¿Podría alguien explicar los pasos que habrían sucedido para explicar esta diferencia en el tiempo?

Además, ¿cómo se asegurará de que la tabla se compila en ambos casos en el ejemplo anterior, incluso si se utiliza una variable para el límite?No siempre es posible codificar los números para los límites de la tabla, pero a veces se deben usar variables para estos. ¿Debería uno usar explícitamente el comando Compile? (No uso Compile directamente, ya que asumí que se hace automáticamente cuando es necesario).

edición (1)

En respuesta a mensaje por Mike continuación en encontrar ninguna diferencia en el tiempo cuando se utiliza una llamada.

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[a]] 
] 

da

{0.031, True} 

Pero eso es porque a es ahora el número 1000 dentro de la función, una vez que se llama. Como M pasa cosas por VALOR.

Si forzamos la llamada a ser por referencia, de manera que a se deja sin evaluar, entonces tenemos

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[Unevaluated@a]] 
] 

Ahora vemos el resultado esperado, ya que ahora a sigue siendo simbólica dentro de la función, estamos volver al punto uno, y ahora es lento, ya que no está empaquetado. Y dado que no está empaquetado, no se usa Compilar.

{0.437, False} 

edición (2) Gracias a todos por las respuestas, creo que aprendí de adjudicar de ellos.

Aquí hay un resumen ejecutivo, solo para asegurarse de que todo estaba bien.

edición (3)

Aquí están los enlaces especialmente he relacionados con consejos a utilizar para hacer el código Mathematica funciona más rápido.

1. http://library.wolfram.com/howtos/faster/
2. http://blog.wolfram.com/2011/12/07/10-tips-for-writing-fast-mathematica-code/
3. https://stackoverflow.com/questions/4721171/performance-tuning-in-mathematica
4. Using Array and Table Functions in Mathematica. Which is best when

Answer 1

Así que esto es lo que creo que está pasando. La razón por la que ve la ralentización entre un límite numérico y simbólico en Table se debe al hecho de que realiza un doble índice. Cada subtabla (por ejemplo, revisar todos los índices j para un índice fijo i) se construye por separado y cuando el límite es simbólico, hay que dar un paso adicional para calcular ese límite antes de construir cada subtabla. Puedes ver esto examinando, p. Ej.

Trace[a = 3; 
     tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
    ] 

David da un buen ejemplo de por qué usted quiere hacer esta comprobación para cada sub-lista. En cuanto a por qué Mathematica no puede entender cuándo esta verificación no es necesaria, no tengo ni idea.Si sólo tiene un índice de resumir más de que no hay diferencia de velocidad entre la versión simbólica y numérica

Timing[tbl = Table[i + j, {j, 1, 1000}];] 
{0.0012, Null} 

Timing[a = 1000; 
     tbl = Table[i + j, {j, 1, a}]; 
     ] 
{0.0013, Null} 

para responder a su seguimiento respecto a la velocidad; haciendo tbl una función es más rápida para los límites numéricos y simbólicos.

Timing[a = 1000; 
     tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
     tblFunc[a]; 
     ] 

{0.045171, Null} 

vs

Timing[tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];] 
{0.066864, Null} 

Timing[a = 1000; 
     tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
     ] 
{0.632128, Null} 

Ganas velocidad aún más si tiene la intención de reutilizar la construcción tbl.

b=1000; 
Timing[tblFunc[b];] 
{0.000013, Null} 

Answer 2

Las cosas clave a controlar, como han mencionado otros, son el embalaje y la longitud de la lista. En realidad no veo las diferencias que informa Timo:

ClearAll[tblFunc]; 
Timing[a = 1000; 
tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tblFunc[a]]] 

{0.077706, True} 

vs 

ClearAll[tbl]; 
Timing[ 
tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}]; 
Developer`PackedArrayQ[tbl]] 

{0.076661, True} 

ClearAll[tbl]; 
Timing[a = 1000; 
tbl = Table[i + j, {i, 1, a}, {j, 1, a}]; 
Developer`PackedArrayQ[tbl]] 

{1.02879, False} 

Así que para mí la única diferencia es si la lista está llena. Si se trata de una función, no hay diferencia en el tiempo en mi configuración. Y como era de esperar, al apagar autocompilation los tiempos son los mismos para todo lo anterior porque ninguna de embalaje se produce:

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> Infinity}]; 

{1.05084, False} 

vs 

{1.00348, False} 

{1.01537, False} 

restablecer la longitud de la tabla de autocompilado:

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> 250}] 

Answer 3

Esta cifra es ligeramente OT, pero para En este caso, es posible que desee evitar el uso del procesamiento elemento por elemento implícito en el uso de Table. Más bien, usa Exterior. Esto es lo que estoy viendo en mi sistema:

Timing[Outer[Plus, Range[5000], Range[5000]];] 
{0.066763,Null} 

    Timing[Table[i + j, {i, 1, 5000}, {j, 1, 5000}];] 
{0.555197,Null} 

Toda una diferencia dramática.