¿Cómo sacar los números más grandes de una gran cantidad de números?

Question

Me gustaría obtener los 100 elementos más grandes de una lista de al menos 100000000 números.

Pude ordenar toda la lista y solo tomar los últimos 100 elementos de la lista ordenada, pero eso sería muy costoso en términos de memoria y tiempo.

¿Existe alguna forma fácil y pitónica de hacer esto?

Lo que quiero es seguir la función en lugar de una clasificación pura. En realidad, no quiero perder el tiempo para ordenar los elementos que no me importan.

Por ejemplo, esta es la función que me gustaría tener:

getSortedElements(100, lambda x,y:cmp(x,y)) 

Nota este requisito es sólo para la perspectiva del rendimiento.

Answer 1

El módulo heapq en la biblioteca estándar ofrece la función nlargest() para hacer esto:

top100 = heapq.nlargest(100, iterable [,key]) 

No va a ordenar la lista entera, para que no se pierda el tiempo en los elementos que Don' Necesito

Answer 2

Selection algorithms debería ayudar aquí.

Una solución muy fácil es encontrar el centésimo elemento más grande, luego ejecutar a través de la lista seleccionando elementos que son más grandes que este elemento. Eso te dará los 100 elementos más grandes. Esto es lineal en la longitud de la lista; esto es lo mejor posible

Hay algoritmos más sofisticados. Un heap, por ejemplo, es muy susceptible a este problema. El algoritmo basado en el montón es n log k donde n es la longitud de la lista y k es la cantidad de elementos más grandes que desea seleccionar.

Hay una discusión de este problem en la página de Wikipedia para los algoritmos de selección.

Editar: Otro afiche ha señalado que Python tiene una solución integrada a este problema. Obviamente, eso es mucho más fácil que hacer rodar el suyo propio, pero mantendré esta publicación en caso de que quiera aprender sobre cómo funcionan dichos algoritmos.

Answer 3

Puede usar una estructura de datos Heap. Un montón no necesariamente se pedirá, pero es una manera bastante rápida de mantener los datos semiordenados, y tiene la ventaja de que el elemento más pequeño es siempre el primer elemento del montón.

Un montón tiene dos operaciones básicas que te ayudarán: Agregar y Reemplazar.

Básicamente lo que haces es agregarle elementos hasta llegar a 100 artículos (tu número N superior para tu pregunta). Luego, después de eso, reemplazas el primer elemento con cada nuevo elemento, siempre que el nuevo sea más grande que el primero.

Siempre que reemplace el primer elemento con algo más grande, el código interno en el montón ajustará el contenido del montón para que si el nuevo elemento no es el más pequeño, burbujeará en el montón, y el elemento más pequeño " burbuja hacia abajo "para el primer elemento, listo para ser reemplazado en el camino.

Answer 4

La mejor manera de hacer esto es mantener una pila ordenada cola de prioridad que usted hace estallar fuera de una vez que tiene 100 entradas en el mismo.

Si bien no le importa si los resultados están ordenados es intuitivamente obvio obtendrá esto de forma gratuita. Para saber que tiene los 100 mejores, debe ordenar su lista actual de números principales en orden a través de una estructura de datos eficiente. Esa estructura conocerá el mínimo, el máximo y la posición relativa de cada elemento de forma natural, de forma que pueda afirmar su posición junto a sus vecinos.

Como se ha mencionado en Python que usaría heapq. En java PriorityQueue: http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

Aquí es una solución que he usado que es independiente de las bibliotecas y que funcionará en cualquier lenguaje de programación que tiene matrices:

inicialización:

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array. 

Para cada valor, decir current_value, en la lista de entrada:

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!> 

minvalue wil Obtendré rápidamente un valor alto y, por lo tanto, la mayoría de los valores en la lista de entrada solo deberán compararse con el valor mínimo (el resultado de la comparación será en su mayoría falso).

Answer 6

Para las salchichas algoritmos en la audiencia: usted puede hacer esto con una simple variación en el algoritmo de Tony Hoare Find:

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j) 

Este algoritmo pone las mayores topn elementos en los primeros topn elementos de la matriz a, sin clasificándolos. Por supuesto, si quiere que se clasifiquen, o por pura simplicidad, un montón es mejor, y llamar a la función de la biblioteca es aún mejor. Pero es un algoritmo genial.