¿Cómo obtener 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.

Podría ordenar toda la lista y simplemente 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 un tipo puro. 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))

Tenga en cuenta que este requisito es solo para la perspectiva de 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 ordenará toda la lista, por lo que no perderá tiempo en los elementos que no necesita.

Answer 2

Los algoritmos de selección deberían ayudar aquí.

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

Hay algoritmos más sofisticados. Un montón , 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 el número de elementos más grandes que desea seleccionar .

Se discute este problema en la página de Wikipedia para algoritmos de selección.

Editar: otro póster ha señalado que Python tiene una solución integrada para este problema. Obviamente, eso es mucho más fácil que rodar el tuyo, pero mantendré esta publicación en caso de que quieras aprender sobre cómo funcionan estos algoritmos.

Answer 3

Puede usar una estructura de datos Heap. No necesariamente se ordenará un montón, pero es una forma bastante rápida de mantener datos semiorpedidos, y tiene la ventaja de que el elemento más pequeño siempre es el primer elemento en el montón.

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

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

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 de modo 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 abajo " al primer elemento, listo para ser reemplazado en el camino.

Answer 4

La mejor manera de hacer esto es mantener una cola de prioridad ordenada en el montón de la que salga una vez que tenga 100 entradas.

Si bien no le importa si los resultados están ordenados, es intuitivamente obvio que 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 sabrá el mínimo, el máximo y la posición relativa de cada elemento de una manera natural para que pueda afirmar su posición al lado de sus vecinos.

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

Answer 5

Aquí hay una solución que he usado que es independiente de las bibliotecas y que funcionará en cualquier lenguaje de programación que tenga 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, diga 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 obtendrá rápidamente un valor alto y, por lo tanto, la mayoría de los valores en la lista de entrada solo será necesario compararlo con el valor mínimo (el resultado de la comparación será mayormente falso).

Answer 6

Para los algoritmos weenies en la audiencia: puede hacer esto con una simple variación en el algoritmo de Tony Hoare Buscar :

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 coloca los elementos topn más grandes en los primeros elementos topn de la matriz a , sin ordenándolos . Por supuesto, si desea ordenarlos, o por pura simplicidad, un montón es mejor, y llamar a la función de biblioteca es aún mejor. Pero es un algoritmo genial.