Encontrar el enésimo elemento de la lista sin ordenar sin ordenar la lista

Question

Hey. Tengo una matriz muy grande y quiero encontrar el enésimo valor más grande. Trivialmente, puedo ordenar la matriz y luego tomar el elemento Nth, pero solo estoy interesado en un elemento, así que probablemente exista una forma mejor que ordenar la matriz completa ...

Answer 1

Ordenando requeriría O tiempo de ejecución al mínimo (nlogn) - Hay muy eficiente selection algorithms que puede resolver el problema en tiempo lineal.

Partition-based selection (a veces Quick select), que se basa en la idea de ordenación rápida (partición recursiva), es una buena solución (ver enlace para pseudocódigo + Another example).

Answer 2

Usar heapsort. Solo ordena parcialmente la lista hasta que saques los elementos.

Answer 3

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 sencillo ordenar la lista.

Answer 4

Básicamente, desea generar una lista "N superior" y seleccionar la que se encuentra al final de esa lista.

Para que pueda escanear la matriz una vez e insertarla en una lista vacía cuando el elemento granArray sea mayor que el último elemento de su lista superior-N, luego suelte el último elemento.

Después de que termine de escanear, elija el último elemento en su lista de N superior.

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 5

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

Sin embargo, puede almacenar sus Kth valores 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 6

Una simple clasificación rápida modificado funciona muy bien en la práctica. Tiene un tiempo promedio de funcionamiento proporcional a N (aunque en el peor de los casos, el tiempo de mala suerte es O (N^2)).

Proceda como un quicksort. Elija un valor de pivote aleatoriamente, luego transmita 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, entonces ordenaría recursivamente cada uno de esos dos contenedores. Pero para el cómputo N-ésimo de valor más alto, solo tiene que ordenar UNO de los contenedores. La población de cada contenedor le dice qué contenedor contiene su valor n-ésimo más alto. Entonces, por ejemplo, si quiere el valor 125 más alto y ordena 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 7

Un montón es la mejor estructura de datos para esta operación y Python tiene una excelente biblioteca incorporada para hacer 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 

resultado Confirmar por clasificar:

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

Answer 8

Usted podría intentar la mediana de método Medianas - su velocidad es O (N).

Answer 9

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

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

Entonces, incluso si quickselect es O (n) frente a O (nlogn) ordenado, eso no tiene en cuenta cuántas instrucciones de código máquina reales procesar cada n elementos tomará, cualquier impacto en pipelining, usos de cachés de procesador y otras cosas que los creadores y mantenedores de los clasificados formarán en el código python.