print - sort python 3

Buscando el noveno elemento de la lista sin clasificar sin clasificar la lista

Question

Oye. Tengo una matriz muy grande y quiero encontrar el valor Nth más grande. Trivialmente puedo ordenar la matriz y luego tomar el elemento Nth, pero solo estoy interesado en un elemento, así que probablemente haya una mejor manera de clasificar toda la matriz ...

Answer 1

Básicamente, desea generar una lista "top-N" y seleccionar la que está al final de esa lista.

Por lo tanto, puede escanear la matriz una vez e insertarla en una lista vacía cuando el elemento largeArray sea mayor que el último elemento de su lista de la parte superior-N y luego soltar el último elemento.

Una vez que termine de escanear, elija el último elemento en su lista de las N principales.

Un ejemplo para ints y N = 5:

int[] top5 = new int[5]();
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value

for(int i = 0; i < largeArray.length; i++) {
    if(largeArray[i] > top5[4]) {
       // insert into top5:
       top5[4] = largeArray[i];

       // resort:
       quickSort(top5);
    }
}

Answer 2

Como ha dicho la gente, puede recorrer la lista una vez que realiza un seguimiento de los valores más grandes de K. Si K es grande, este algoritmo estará cerca de O (n ² ).

Sin embargo, puede almacenar sus valores Kth más grandes como un árbol binario y la operación se convierte en O (n log k).

Según Wikipedia, este es el mejor algoritmo de selección:

 function findFirstK(list, left, right, k)
     if right > left
         select pivotIndex between left and right
         pivotNewIndex := partition(list, left, right, pivotIndex)
         if pivotNewIndex > k  // new condition
             findFirstK(list, left, pivotNewIndex-1, k)
         if pivotNewIndex < k
             findFirstK(list, pivotNewIndex+1, right, k)

Su complejidad es O (n).

Answer 3

La clasificación requeriría un tiempo de ejecución de O (nlogn) como mínimo: hay algoritmos de selección muy eficientes que pueden resolver su problema en tiempo lineal.

Partition-based selection (a veces Partition-based selection Quick select ), que se basa en la idea de quicksort (partición recursiva), es una buena solución (consulte el enlace para pseudocódigo + Otro ejemplo ).

Answer 4

Puede iterar toda la secuencia manteniendo una lista de los 5 valores más grandes que encuentre (esto será O (n)). Dicho esto, creo que sería más simple ordenar la lista.

Answer 5

Puedes probar el método de la Mediana de las Medianas, su velocidad es O (N).

Answer 6

Un montón es la mejor estructura de datos para esta operación y Python tiene una excelente biblioteca integrada para hacer precisamente esto, llamada heapq.

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

Ejemplo de uso:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

Confirme el resultado ordenando:

>>> list(sorted(iter))[-10]
920

Answer 7

Un quicksort simple modificado funciona muy bien en la práctica. Tiene un tiempo de ejecución promedio proporcional a N (aunque en el peor de los casos la mala suerte es O (N ^ 2)).

Procede como un quicksort. Elija un valor de pivote al azar, luego transmita a través de sus valores y vea si están por encima o por debajo de ese valor de pivote y colóquelos en dos contenedores según esa comparación. En quicksort, a continuación, clasificaría recursivamente cada uno de esos dos contenedores. Pero para el N-ésimo cálculo del valor más alto, solo necesita ordenar UNO de los contenedores. La población de cada bin le indica qué bin tiene su n-ésimo valor más alto. Así, por ejemplo, si desea el valor 125º más alto y clasifica en dos contenedores que tienen 75 en el contenedor "alto" y 150 en el contenedor "bajo", puede ignorar el contenedor alto y simplemente proceder a encontrar el 125-75 = 50º valor más alto solo en el contenedor bajo.

Answer 8

Una cosa que debe hacer si esto está en el código de producción es probar con muestras de sus datos. Por ejemplo, podría considerar los arreglos ''grandes'' de 1000 o 10000 elementos y codificar un método de selección rápida de una receta.

La naturaleza compilada de las optimizaciones ordenadas y ocultas y en constante evolución hacen que sea más rápido que un método de selección rápida escrito por Python en conjuntos de datos de tamaño pequeño a mediano (<1,000,000 elementos). Además, es posible que a medida que aumente el tamaño de la matriz más allá de esa cantidad, la memoria se maneje de manera más eficiente en el código nativo y el beneficio continúe.

Por lo tanto, incluso si la selección rápida es O (n) frente a O (nlogn) ordenada, eso no tiene en cuenta cuántas instrucciones reales de código de máquina procesarán cada n elementos, ningún impacto en la canalización, el uso de cachés del procesador y otras cosas. los creadores y mantenedores de clasificados ordenarán el código de Python.

Answer 9

Utilice heapsort. Solo ordena parcialmente la lista hasta que dibuja los elementos.