Extraindo um determinado número de valores mais altos em uma lista

Question

Estou procurando exibir um número fixo de itens em uma página da web de acordo com seu respectivo peso (representado por um Integer). A lista em que esses itens são encontrados pode ter praticamente qualquer tamanho.

A primeira solução que vem à mente é fazer um Collections.sort() e para obter os itens um por um passando pelo List. Existe uma solução mais elegante que possa ser usada para preparar, digamos, os oito principais itens?

Answer 1

Apenas vá para Collections.sort(..). É eficiente o suficiente.

Este algoritmo oferece desempenho garantido de log (n).

Você posso Tente implementar algo mais eficiente para o seu estojo concreto Se você conhece algumas propriedades distintas da sua lista, isso não seria justificado. Além disso, se sua lista vier de um banco de dados, por exemplo, você pode LIMIT Encome -o lá em vez de em código.

Answer 2

Suas opções:

1. Faça um linear Pesquise, mantendo os n pesos principais encontrados ao longo do caminho. Isso deve ser mais rápido do que classificar uma lista longa se, por algum motivo, você não puder reutilizar os resultados de classificação entre exibir a página (por exemplo, a lista está mudando rapidamente).

   ATUALIZAÇÃO: Fico corrigido na pesquisa linear necessariamente sendo melhor do que classificar. Veja o artigo da Wikipedia "Selection_algorithm - Selecionando K Menores ou Maiores Elementos"Para melhores algoritmos de seleção.

2. Manter manualmente um List (o original ou um paralelo) classificado em ordem de peso. Você pode usar métodos como Coleções.BinarySearch () Para determinar onde inserir cada novo item.

3. Manter um List (o original ou um paralelo) classificado em ordem de peso ligando Coleções.sort () Após cada modificação, modificações em lote, ou logo antes da exibição (possivelmente mantendo um sinalizador de modificação para evitar classificar uma lista já classificada).

4. Use uma estrutura de dados que mantém ordem de peso classificada para você: Fila de prioridade, conjunto de árvores, etc. Você também pode criar sua própria estrutura de dados.

5. Mantenha manualmente uma segunda estrutura de dados (possivelmente ordenada por peso) dos principais itens. Essa estrutura de dados é atualizada sempre que a estrutura de dados original é modificada. Você pode criar sua própria estrutura de dados para embrulhar a lista original e este "Top N Cache" juntos.

Answer 3

Você poderia usar um Max-heap.

Se seus dados se originarem de um banco de dados, coloque um índice nessa coluna e use a ordem e o limite superior ou o limite para buscar apenas os registros que você precisa exibir.

Answer 4

Ou a Fila de prioridade.

Answer 5

usando dólar:

List<Integer> topTen = $(list).sort().slice(10).toList();

sem usar o dólar, você deveria sort() usando Collections.sort(), então obtenha os primeiros n itens usando list.sublist(0, n).

Answer 6

Como você diz que a lista de itens para extrair esses principais n pode ser de qualquer tamanho e, portanto, pode ser grande, presumo, eu aumentaria o simples sort() As respostas acima (que são inteiramente apropriadas para entrada de tamanho razoável) sugerindo que a maior parte do trabalho aqui é encontrar os principais n-então classificar esses n é trivial. Aquilo é:

Queue<Integer> topN = new PriorityQueue<Integer>(n);
for (Integer item : input) {
  if (topN.size() < n) {
    topN.add(item);        
  } else if (item > topN.peek()) {
    topN.add(item);          
    topN.poll();
  }
}

List<Integer> result = new ArrayList<Integer>(n);
result.addAll(topN);
Collections.sort(result, Collections.reverseOrder());

A pilha aqui (um min-heap) é pelo menos limitada em tamanho. Não há necessidade real de fazer uma pilha de todos os seus itens.

Answer 7

Não, na verdade não. Pelo menos não usa os métodos internos de Java.

Existem maneiras inteligentes de obter o número mais alto (ou mais baixo) n de itens de uma lista mais rápida que um O(n*log(n)) Operação, mas isso exigirá que você codifique esta solução manualmente. Se o número de itens permanecer relativamente baixo (não mais que algumas centenas), classificá -lo usando Collections.sort() E então agarrar os números principais dos N é o caminho a seguir.

Answer 8

Depende de quantos. Vamos definir n como o número total de chaves e m como o número que você deseja exibir.
Classificando a coisa toda: O(nlogn)
Examinando a matriz sempre para o próximo número mais alto: O(n*m)
Então, a questão é - qual é a relação entre n e m?
Se m < log n, a digitalização será mais eficiente.
Por outro lado, m >= log n, o que significa que a classificação será melhor. (Já que para o caso de borda de m = log n Na verdade, não importa, mas a classificação também lhe dará o benefício de, bem, classificar a matriz, o que é sempre bom.

Answer 9

Se o tamanho da lista for n e o número de itens a serem recuperados é k, você precisará chamar Heapify na lista, que converte a lista (que deve ser indexível, por exemplo, uma matriz) em uma fila de prioridade. (Veja a função Heapify em http://en.wikipedia.org/wiki/heapsort)

A recuperação de um item na parte superior da pilha (o item máximo) leva o tempo O (LG n). Então, seu tempo total seria:

O (n + k lg n)

o que é melhor que o (n lg n) assumindo que K é muito menor que o N.

Answer 10

Se manter uma matriz classificada ou usar uma estrutura de dados diferente não for uma opção, você pode tentar algo como o seguinte. O tempo O é semelhante à classificação da grande matriz, mas na prática isso deve ser mais eficiente.

small_array = big_array.slice( number_of_items_to_find );
small_array.sort();
least_found_value = small_array.get(0).value;

for ( item in big_array ) {  // needs to skip first few items
  if ( item.value > least_found_value ) {
    small_array.remove(0);
    small_array.insert_sorted(item);
    least_found_value = small_array.get(0).value;
  }
}

Small_array pode ser um objeto [] e o loop interno pode ser feito com a troca em vez de realmente remover e inserir uma matriz.