Porque procesar un array ordenado es mas rapido que uno en desorden?
 

Una pregunta ligeramente interesante con una respuesta impresionante:

http://stackoverflow.com/questions/1...unsorted-array

Importante tambien notar el analisis de los ciclos....

Son las 1am por aquí y ya tengo fiaquitis de leer ¡sobre todo inglés! :D
A vista gorda y rápida, se debe, a ese caso en particular, a que dado por la naturaleza del problema cuando los elementos son ordenados realizar tal evaluación o comparación ya no tiene demasiado sentido.
Resulta demasiado lógico, ya que en realidad si los tenemos ordenados es posible determinar el punto en el cual la evaluación para a ser verdadera y de allí en más no tiene sentido seguir evaluando y directamente aplicar una suma.

No sucede lo mismo cuando los datos están desordenados y no hay modo de determinar cuando optimizar. En este punto necesita hacer esta iteración e ir evaluando dato a dato.

Seguramente si se hiciera otro tipo de operatoria, y ni que decir más compleja que un simple if-then, sobre el array no habría de esperarse demasiada diferencia entre disponer de datos ordenados o no.
Por otro lado esto como dije depende fuertemente de la naturaleza del problema... no debiera llegarse a la conclusión de que siempre será preferible los datos ordenados. Habrá casos en los que no y otros que si.

Saludos,

Me impresionó, porque me hizo entender que:

• Sin conocer la existencia del "Predictor de Saltos", haría falta mucha malicia para sospechar la razón de la diferencia de desempeño.

• Conociendo la existencia del "Predictor de Saltos", hace falta mucho ingenio para determinar un buen balance entre facilidad de lectura del código contra desempeño de ejecución.

Gracias por compartirnos el tema.

-