Como obter os maiores números fora da enorme quantidade de números?

Question

Eu gostaria de obter os 100 maiores elementos a partir de uma lista de pelo menos 100000000 números.

Eu poderia ordenar a lista inteira e apenas tomar os últimos 100 elementos da lista ordenada, mas que seria muito caro em termos de memória e tempo.

Existe alguma maneira existente fácil, pythônico de fazer isso?

O que eu quero é seguinte função em vez de uma espécie pura. Na verdade eu não quero perder tempo para classificar os elementos que eu não me importo.

Por exemplo, esta é a função que eu gostaria de ter:

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

Note que esta exigência é apenas para perspectiva de desempenho.

Answer 1

O módulo heapq nas ofertas da biblioteca padrão do nlargest () função para fazer isso:

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

Não vai tipo toda a lista, assim você não vai perder tempo com os elementos que você não precisa.

Answer 2

Seleção algoritmos deve ajudar aqui.

Uma solução muito fácil é encontrar o maior elemento 100, em seguida, executado através da lista de picking off elementos que são maiores do que este elemento. Isso vai dar-lhe as 100 maiores elementos. Esta é linear no comprimento da lista; este é o melhor possível.

Existem algoritmos mais sofisticados. A pilha , por exemplo, é muito receptivo a este problema. O algoritmo baseado em pilha é n log k onde n é o comprimento da lista e k é o número de maiores elementos que você deseja selecionar.

Há uma discussão deste problema na página da Wikipedia para algoritmos de seleção.

Edit: Outro cartaz salientou que Python foi construído em um solução para este problema. Obviamente que é muito mais fácil do que rolar seus próprios, mas eu vou manter este post se no caso de você gostaria de saber sobre como tais algoritmos de trabalho.

Answer 3

Você pode usar uma estrutura de dados Heap. A pilha não vai necessariamente ser solicitados, mas é uma maneira bastante rápido para manter os dados semi-ordenadas, e tem o benefício da menor item sendo sempre o primeiro elemento na pilha.

A pilha tem duas operações básicas que irão ajudá-lo:. Adicionar e substituir

Basicamente o que você faz é itens adicionar a ele até chegar a 100 itens (o seu número superior N por sua pergunta). Então, depois disso, você substitui o primeiro item com cada novo item, enquanto o novo item é maior do que o primeiro item.

Sempre que substituir o primeiro item com algo maior, o código interno na pilha irá ajustar o conteúdo da pilha de modo que se o novo item não o menor é, ele vai borbulhar para dentro da pilha, eo menor vontade do artigo "bolha down" para o primeiro elemento, pronto para ser substituído ao longo do caminho.

Answer 4

A melhor maneira de fazer isso é manter uma pilha ordenada fila de prioridade que você estalar fora de uma vez que tem 100 entradas nele.

Enquanto você não se importa se os resultados são classificados é intuitivamente óbvio que você vai ter isso de graça. A fim de saber que você tem o top 100, você precisa pedir a sua lista atual de números superiores a fim através de alguma estrutura de dados eficiente. Essa estrutura vai saber o mínimo, o máximo, e a posição relativa de cada elemento de alguma maneira natural que você pode fazer valer a sua posição próxima à sua vizinhos.

Como já foi mencionado em python você usaria heapq. Em java PriorityQueue: http://java.sun.com/javase/ 6 / docs / api / java / util / PriorityQueue.html

Answer 5

Aqui está uma solução que tenho usado que é independente das bibliotecas e que irá trabalhar em qualquer linguagem de programação que tem matrizes:

Inicialização:

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, dizem CURRENT_VALUE, na 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 vai rapidamente obter um alto valor e, portanto, a maioria dos valores na lista de entrada só terão de ser comparado a minvalue (O resultado da comparação vai ser maioritariamente false).

Answer 6

Para os weenies algoritmos na platéia: você pode fazer isso com uma simples variação do algoritmo de Tony Hoare Procurar :

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)

Esse algoritmo coloca as maiores elementos topn para os primeiros elementos topn de a matriz, sem classificando-os. Claro, se você quer que eles ordenados, ou por pura simplicidade, uma pilha é melhor, e chamando a função de biblioteca é melhor ainda. Mas é um algoritmo cool.