¿Existe alguna manera más rápida de encontrar los valores mínimo y máximo?

Question

A menudo he escrito: {Min@#, Max@#} &

Sin embargo, esto parece ineficiente, ya que la expresión debe escanearse dos veces, una para encontrar el valor mínimo y otra para encontrar el valor máximo. ¿Hay una manera más rápida de hacer esto? La expresión es a menudo un tensor o matriz.

Answer 1

Esto lo supera un poco.

minMax = Compile[{{list, _Integer, 1}}, 
    Module[{currentMin, currentMax}, 
    currentMin = currentMax = First[list]; 
    Do[ 
    Which[ 
     x < currentMin, currentMin = x, 
     x > currentMax, currentMax = x], 
    {x, list}]; 
    {currentMin, currentMax}], 
    CompilationTarget -> "C", 
    RuntimeOptions -> "Speed"]; 
v = RandomInteger[{0, 1000000000}, {10000000}]; 
minMax[v] // Timing 

creo que es un poco más rápido que la versión de Leonid porque Do es un poco más rápido que For, incluso en el código compilado.

En última instancia, sin embargo, este es un ejemplo del tipo de impacto de rendimiento que se obtiene al utilizar un lenguaje de programación funcional de alto nivel.

adición en respuesta a Leonid:

no creo que el algoritmo puede dar cuenta de la diferencia de tiempo. Mucho más de las veces, creo, ambas pruebas se aplicarán de todos modos. La diferencia entre Do y For es mensurable, sin embargo.

cf1 = Compile[{{list, _Real, 1}}, 
    Module[{sum}, 
    sum = 0.0; 
    Do[sum = sum + list[[i]]^2, 
    {i, Length[list]}]; 
    sum]]; 
cf2 = Compile[{{list, _Real, 1}}, 
    Module[{sum, i}, 
    sum = 0.0; 
    For[i = 1, i <= Length[list], 
    i = i + 1, sum = sum + list[[i]]^2]; 
    sum]]; 
v = RandomReal[{0, 1}, {10000000}]; 
First /@{Timing[cf1[v]], Timing[cf2[v]]} 

{0.685562, 0.898232} 

Answer 2

Creo que esto es lo más rápido posible, dentro de las prácticas de programación de Mathematica. La única manera que veo para tratar de hacerlo más rápido dentro de MMA es utilizar Compile con el objetivo de compilación C, de la siguiente manera:

getMinMax = 
Compile[{{lst, _Real, 1}}, 
    Module[{i = 1, min = 0., max = 0.}, 
     For[i = 1, i <= Length[lst], i++, 
     If[min > lst[[i]], min = lst[[i]]]; 
     If[max < lst[[i]], max = lst[[i]]];]; 
     {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"] 

Sin embargo, aunque esto parece ser algo más lento que su código:

In[61]:= tst = RandomReal[{-10^7,10^7},10^6]; 

In[62]:= Do[getMinMax[tst],{100}]//Timing 
Out[62]= {0.547,Null} 

In[63]:= Do[{Min@#,Max@#}&[tst],{100}]//Timing 
Out[63]= {0.484,Null} 

Probablemente pueda escribir la función completamente en C, y luego compilar y cargar como dll - puede eliminar algunos gastos generales de esta manera, pero dudo que gane más que unos pocos porcentajes - no vale la pena el esfuerzo IMO.

EDITAR

Es interesante que usted puede aumentar significativamente la velocidad de la solución compilado con la eliminación de subexpresiones comunes manual (lst[[i]] aquí):

getMinMax = 
Compile[{{lst, _Real, 1}}, 
    Module[{i = 1, min = 0., max = 0., temp}, 
    While[i <= Length[lst], 
     temp = lst[[i++]]; 
     If[min > temp, min = temp]; 
     If[max < temp, max = temp];]; 
     {min, max}], CompilationTarget -> "C", RuntimeOptions -> "Speed"] 

es un poco más rápido que {Min@#,Max@#}.

Answer 3

Para una matriz, podría hacer lo más simple y funcional utilizar

Fold[{Min[##],Max[##]}&, First@#, Rest@#]& @ data 

Por desgracia, no es demonio de la velocidad. Incluso para listas cortas, 5 elementos, todos de Leonid's answers y Mark's answer son al menos 7 veces más rápidos, no compilados en v.7. Para las listas largas, 25000 elementos, esto empeora con el hecho de que Mark es 19.6 veces más rápido, pero incluso a esta longitud, esta solución tomó solo alrededor de 0.05 segundos para ejecutarse.

Sin embargo, no contaría {Min[#], Max[#]}& como opción. Sin compilar fue 1.7 veces más rápido que Mark para la lista corta y casi 15 veces más rápido para las listas largas (8 veces y casi 300 veces más rápido, respectivamente, que la solución Fold).

Desafortunadamente, no pude obtener buenos números para las versiones compiladas de las respuestas {Min[#], Max[#]}&, Leonid o Mark, sino que recibí numerosos mensajes de error incomprensibles. De hecho, {Min[#], Max[#]}& aumentó en tiempo de ejecución. Sin embargo, la solución Fold mejoró drásticamente, y tomó el doble de tiempo que las respuestas de Leonid en tiempos sin compilar.

Editar: para los curiosos, aquí está algunas mediciones de temporización de las funciones sin compilar -

Cada función se utilizó en 100 listas de la longitud especificada en el eje horizontal y el tiempo medio, en segundos, es el eje vertical. En orden ascendente de tiempo, las curvas son {Min[#], Max[#]}&, la respuesta de Mark, la segunda respuesta de Leonid, la primera respuesta de Leonid y el método Fold de arriba.

Answer 4

Para todos ustedes que están haciendo sincronizaciones, me gustaría advertirles que el orden de ejecución es extremadamente importante. Por ejemplo, un vistazo a los siguientes dos pruebas sincronizaciones sutilmente diferentes:

(1)

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First, 
    Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

El hombre extraño aquí es la última Min

(2)

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    Max[a] // AbsoluteTiming // First, Min[a] // AbsoluteTiming // First, 
    Min[a] // AbsoluteTiming // First, Max[a] // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

Aquí, la sincronización más alta se encuentra para la primera Max, la segunda más alta para la segunda max y las dos Min s son aproximadamente iguales o más bajas. De hecho, esperaría que Max y Min tomaran aproximadamente el mismo tiempo, pero no es así. El primero parece tomar un 50% más de tiempo que el segundo. Tener la pole position también parece tener un handicap del 50%.

ahora una comparación con los algoritmos dados por Mark y Leonid:

res = 
Table[ 
    a = RandomReal[{0, 100}, 10^8]; 
    { 
    {Max[a], Min[a]} // AbsoluteTiming // First, 
    {Min@#, Max@#} &@a // AbsoluteTiming // First, 
    getMinMax[a] // AbsoluteTiming // First, 
    minMax[a] // AbsoluteTiming // First, 
    {Min[a], Max[a]} // AbsoluteTiming // First 
    } 
    , {100} 
    ] 

Aquí nos encontramos con unos 0,3 s para el Max {[a], Min [a]} (que incluye el handicap de posición pole), el nivel .1 es para el método de Mark; los demás son todos iguales.