Te sugerimos que pruebes esta respuesta en un ambiente controlado antes de pasarlo a producción, un saludo.
Solución:
Ha pasado bastante tiempo, pero recuerdo que en Algoritmos 101 nos enseñaron un algoritmo de clasificación que usaba la aleatorización. No era un buen estudiante, así que no recuerdo realmente cómo fue o por qué funcionó rápidamente en promedio.
Sin embargo, he decidido que este problema requiere una solución que utilice la aleatorización, que con suerte funcionará a mi favor en promedio.
import random
def arrayIsSorted (arr) :
for i in range(len(arr)-1) :
if arr[i]>arr[i+1] : return False
return True
def rSort (arr) :
random.seed (42)
counter = 0
while not arrayIsSorted(arr) :
random.shuffle (arr)
counter+=1
print ("Sorted in %d iterations." % counter)
return arr
Ya que true La aleatorización es importante, me aseguro de sembrar el RNG con la respuesta a La vida, el universo y todo. Después de un poco de prueba, ¡resultó que fue un movimiento inteligente! Vea qué tan rápido se ordenan estas 2 listas completamente arbitrarias:
rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])
Ambos se ordenan en solo 1 iteración; ¡posiblemente no podría pedir una función más rápida que esa!
Ahora bien, hay que reconocer que algunas otras listas producen resultados ligeramente peores …
rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])
Estos se ordenan en 4,176 y 94,523 iteraciones respectivamente, lo que en realidad lleva más de un segundo … ¡pero mantengamos ese hecho para nosotros para no distraer a nadie de lo asombroso que es este algoritmo!
Editar:
Me pidieron que probara la eficiencia de mi algoritmo en una lista de 100 elementos, así que aquí tienes:
rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])
¡Incluso esta lista larga y completamente arbitraria se ordena instantáneamente! ¡Realmente debo haberme tropezado con el mejor algoritmo de clasificación del mundo!
Si puede crear sus propios datos, entonces es bastante sencillo: obtenga datos que parezcan aleatorios, pero que incluyan un key para una clasificación más rápida. Todos los demás datos utilizan el método de clasificación original, por lo que promedio los tiempos son mejores.
Una forma sencilla es asegurarse de que cada elemento de datos tenga un key, y luego simplemente hash el keys. Tomemos, por ejemplo, una lista con los números del 1 al 10,000, todos multiplicados por 16, y con un número aleatorio del 0 al 15 agregado (ver fillArray () debajo). Se verán aleatorios, pero cada uno tiene un secuencial único. key. Para ordenar, divida por 16 (en C el >> 4 es muy rápido) y luego coloque el número en un array usando el resultado key como el índice. Una pasada y listo. En las pruebas, descubrí que el ordenamiento rápido era 30 veces más lento en diez millones de números.
void fillArray(int *a,int len)
for (int i=0;i>4;
r[key]=a[i];
memcpy(a,r,len*sizeof(int));
delete[] r;
void shuffleArray(int *a,int len)
int swap=0, k=0;
for (int i=0;i Cualquier cosa que tenga un carácter único key se puede ordenar de esta manera, si tiene la memoria para almacenarlo, por supuesto. Por ejemplo, muchas bases de datos usan un ID de cliente numérico único; si la lista es lo suficientemente pequeña / secuencial, esto podría guardarse en la memoria. O alguna otra forma de traducir un registro en un número único. Para obtener más información, investiga Hash Sorts, ya que eso es lo que es ...