Encontre os principais elementos N em uma matriz

Qual seria a melhor solução para encontrar elementos top N (digamos 10) em uma lista não ordenada (digamos 100).

A solução que veio na minha cabeça foi para 1. classificá-lo usando quick sort, 2. get top 10.

Mas existe alguma alternativa melhor?

O tempo pode ser reduzido para o tempo linear:

  1. Use o algoritmo de seleção , que efetivamente encontra o k-ésimo elemento em uma matriz não ordenada em tempo linear. Você pode usar uma variante de sorting rápida ou algoritmos mais robustos.

  2. Obtenha o k superior usando o pivô obtido na etapa 1.

Se você está lidando com elementos simples como inteiros de comprimento fixo, desde que você possa poupar um buffer de memory do mesmo tamanho que os dados de input, a ordenação pode ser feita em tempo O (n) usando ordenações bucket ou radix, e isso seja o mais rápido.

Embora existam algoritmos de seleção de tempo linear, a constante oculta é muito alta – em torno de 24 . Isso significa que um algoritmo O (nlog n) será normalmente mais rápido para menos de vários milhões de elementos.

Caso contrário, no caso geral, quando você só pode comparar 2 elementos e determinar qual é maior, o problema é melhor resolvido por uma estrutura de dados de heap .

Suponha que você queira o top k de n itens. Todas as soluções baseadas na sorting completa dos dados requerem tempo O (nlog n), enquanto o uso de um heap requer apenas tempo O (nlog k) – basta construir um heap nos primeiros elementos k, continuar adicionando um elemento e removendo o máximo. Isso vai deixar você com uma pilha contendo os menores k elementos.

Que tal delegar tudo para Java;)

function findTopN(Array list, int n) { Set sortedSet = new TreeSet<>(Comparators.naturalOrder()); // add all elements from list to sortedSet // return the first n from sortedSet } 

Não estou tentando dizer que este é o melhor caminho. Eu ainda acho que o método de Yin Zhu de encontrar o k maior elemento é a melhor resposta.

Sim, você pode fazê-lo em O (n) apenas mantendo uma lista de execução (ordenada) do topo N. Você pode classificar a lista de execução usando as funções de biblioteca regulares ou uma rede de sorting . Por exemplo, uma simples demonstração usando 3 e mostrando quais elementos na lista de execução mudam cada iteração.

5 2 8 7 9

 i = 0 top[0] <= 5 i = 1 top[1] <= 2 i = 2 top[2] <= top[1] (2) top[1] <= top[0] (5) top[0] <= 8 i = 3 top[2] <= top[1] (5) top[1] <= 7 i = 4 top[2] <= top[1] (7) top[1] <= top[0] (8) top[0] <= 9 

A melhor solução é usar as instalações que o idioma escolhido fornecer, o que facilitará sua vida.

No entanto, supondo que essa seja uma questão mais relacionada a qual algoritmo você deve escolher, sugiro uma abordagem diferente aqui. Se você está falando de 10 a 100, você geralmente não deve se preocupar muito com o desempenho, a menos que você queira fazê-lo várias vezes por segundo.

Por exemplo, esse código C (que é tão ineficiente quanto eu posso conseguir sem ser bobo) ainda leva menos de um décimo de segundo para ser executado. Isso não é tempo suficiente para eu sequer pensar em ir tomar um café.

 #include  #include  #include  #define SRCSZ 100 #define DSTSZ 10 int main (void) { int unused[SRCSZ], source[SRCSZ], dest[DSTSZ], i, j, pos; srand (time (NULL)); for (i = 0; i < SRCSZ; i++) { unused[i] = 1; source[i] = rand() % 1000; } for (i = 0; i < DSTSZ; i++) { pos = -1; for (j = 0; j < SRCSZ; j++) { if (pos == -1) { if (unused[j]) { pos = j; } } else { if (unused[j] && (source[j] > source[pos])) { pos = j; } } } dest[i] = source[pos]; unused[pos] = 0; } printf ("Source:"); for (i = 0; i < SRCSZ; i++) printf (" %d", source[i]); printf ("\nDest:"); for (i = 0; i < DSTSZ; i++) printf (" %d", dest[i]); printf ("\n"); return 0; } 

Executá-lo através do time dá a você (eu formatei a saída um pouco para torná-la legível, mas não afetou os resultados):

 Source: 403 459 646 467 120 346 430 247 68 312 701 304 707 443 753 433 986 921 513 634 861 741 482 794 679 409 145 93 512 947 19 9 385 208 795 742 851 638 924 637 638 141 382 89 998 713 210 732 784 67 273 628 187 902 42 25 747 471 686 504 255 74 638 610 227 892 156 86 48 133 63 234 639 899 815 986 750 177 413 581 899 494 292 359 60 106 944 926 257 370 310 726 393 800 986 827 856 835 66 183 901 Dest: 998 986 986 986 947 944 926 924 921 902 real 0m0.063s user 0m0.046s sys 0m0.031s 

Somente quando as quantidades de números se tornam grandes, você deve se preocupar. Não me entenda mal, não estou dizendo que você não deveria pensar em performance. O que você não deve fazer é gastar muito tempo otimizando coisas que não importam - YAGNI e todo aquele jazz.

Como em todas as questões de otimização, a medida não adivinha!

Bem, você pode criar um heap a partir de um array não ordenado no tempo O (n), e você pode obter o elemento top do heap no tempo O (log (n)). Portanto, seu tempo de execução total é O (n + k * log (n)).

Escrito abaixo de ambas as implementações de sorting e inserção de seleção. Para um dataset maior, sugiro que o tipo de inserção seja melhor que o tipo de seleção

 public interface FindTopValues { int[] findTopNValues(int[] data, int n); } 

Implementação de sorting de inserção:

 public class FindTopValuesInsertionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=1; i 0) && (values[i] > values[curPos-1])) { curPos--; } if (curPos != i) { int element = values[i]; System.arraycopy(values, curPos, values, curPos+1, (i-curPos)); values[curPos] = element; } } return Arrays.copyOf(values, n); } } 

Implementação de sorting de seleção:

 public class FindTopValuesSelectionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=0; i<=n; i++) { int maxPos = i; for (int j=i+1; j values[maxPos]) { maxPos = j; } } if (maxPos != i) { int maxValue = values[maxPos]; values[maxPos] = values[i]; values[i] = maxValue; } } return Arrays.copyOf(values, n); } } 

Sim, existe uma maneira de fazer melhor que o quicksort. Como apontado por Yin Zhu, você pode procurar o kth maior elemento primeiro e, em seguida, usar esse valor de elemento como seu pivô para dividir o array

Me pediram o mesmo algoritmo na entrevista. Eu fiz isso, se alguém pode comparar isso com o algoritmo mais rápido em Java – será muito útil.

  public int[] findTopNValues(int[] anyOldOrderValues, int n) { if (n < 0) { return new int[]{}; } if (n == 1) { return new int[]{findMaxValue(anyOldOrderValues)}; } int[] result = new int[n + 1]; for (int i = 0; i < Math.min(n, anyOldOrderValues.length); i++) { result[i] = anyOldOrderValues[i]; } Arrays.sort(result); int max = result[0]; for (int i = n - 1; i < anyOldOrderValues.length; i++) { int value = anyOldOrderValues[i]; if (max < value) { result[n] = value; Arrays.sort(result); int[] result1 = new int[n + 1]; System.arraycopy(result, 1, result1, 0, n); result = result1; max = result[0]; } } return convertAndFlip(result, n); } public static int[] convertAndFlip(int[] integers, int n) { int[] result = new int[n]; int j = 0; for (int i = n - 1; i > -1; i--) { result[j++] = integers[i]; } return result; } 

e teste para isso:

 public void testFindTopNValues() throws Exception { final int N = 100000000; final int MAX_VALUE = 100000000; final int returnArray = 1000; final int repeatTimes = 5; FindTopValuesArraySorting arraySorting = new FindTopValuesArraySorting(); int[] randomArray = createRandomArray(N, MAX_VALUE); for (int i = 0; i < repeatTimes; i++) { long start = System.currentTimeMillis(); int[] topNValues = arraySorting.findTopNValues(randomArray, returnArray); long stop = System.currentTimeMillis(); System.out.println("findTopNValues() from " + N + " elements, where MAX value=" + (MAX_VALUE - 1) + " and return array size " + returnArray + " elements : " + (stop - start) + "msec"); // System.out.println("Result list = " + Arrays.toString(topNValues)); } } private static int[] createRandomArray(int n, int maxValue) { Random r = new Random(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = r.nextInt(maxValue); } return arr; } 

Resultado é algo como:

 findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 395msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 311msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 473msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 380msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 406msec 

~ 400msc resultado médio, para obter 1000 números inteiros máximos de matriz de 100.000.000 elementos iniciais. não é ruim!

Apenas tentei esse conjunto de cima:

 findTopNValues() from 101 elements and return array size 10 elements : 1msec Result list = [998, 986, 986, 986, 947, 944, 926, 924, 921, 902] Original list = [403, 459, 646, 467, 120, 346, 430, 247, 68, 312, 701, 304, 707, 443, 753, 433, 986, 921, 513, 634, 861, 741, 482, 794, 679, 409, 145, 93, 512, 947, 19, 9, 385, 208, 795, 742, 851, 638, 924, 637, 638, 141, 382, 89, 998, 713, 210, 732, 784, 67, 273, 628, 187, 902, 42, 25, 747, 471, 686, 504, 255, 74, 638, 610, 227, 892, 156, 86, 48, 133, 63, 234, 639, 899, 815, 986, 750, 177, 413, 581, 899, 494, 292, 359, 60, 106, 944, 926, 257, 370, 310, 726, 393, 800, 986, 827, 856, 835, 66, 183, 901] 

O melhor Algoritmo dependeria, em grande medida, do tamanho de K. Se K é pequeno, basta seguir o Algoritmo BubbleSort e iterar os tempos K do laço externo daria os valores K superiores. A complexidade será O (n * k).

No entanto, para valores de K próximos de n, a complexidade se aproximará de O (n ^ 2). Nesse cenário, o quicksort pode ser uma boa alternativa.

 public class FindTopValuesSelectionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=0; i<=n; i++) { int maxPos = i; for (int j=i+1; j values[maxPos]) { maxPos = j; } } if (maxPos != i) { int maxValue = values[maxPos]; values[maxPos] = values[i];**strong text** values[i] = maxValue; } } return Arrays.copyOf(values, n); } } 

Você pode usar a List e pode class de Comparators de goiaba para obter os resultados desejados. É uma solução altamente otimizada. Por favor, veja uma amostra abaixo, que obtém os 5 principais números. Api pode ser encontrado aqui .

 import java.util.Comparator; import java.util.List; import java.util.stream.Collector; import org.junit.Test; import com.google.common.collect.Comparators; import com.google.common.collect.Lists; public class TestComparator { @Test public void testTopN() { final List numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0); final Collector> collector = Comparators.greatest(5, Comparator.naturalOrder()); final List top = numbers.stream().collect(collector); System.out.println(top); } } 

Saída: [9, 8, 7, 6, 5]