Encuentra los N elementos principales en una matriz

¿Cuál sería la mejor solución para encontrar elementos N superiores (por ejemplo, 10) en una lista desordenada (de, por ejemplo, 100)?

La solución que surgió en mi cabeza fue 1. ordenarla usando clasificación rápida, 2. obtener los 10 mejores.

¿Pero hay alguna mejor alternativa?

El tiempo se puede reducir a tiempo lineal:

  1. Utilice el algoritmo de selección , que efectivamente encuentra el elemento k-ésimo en una matriz no ordenada en tiempo lineal. Puede usar una variante de ordenación rápida o algoritmos más robustos.

  2. Obtenga la parte superior k usando el pivote obtenido en el paso 1.

Si se trata de elementos simples como enteros de longitud fija, siempre que pueda disponer de un búfer de memoria del mismo tamaño que los datos de entrada, la clasificación se puede hacer en el tiempo O (n) utilizando tipos de balde o raíz, y esto hará sé el más rápido.

Aunque hay algoritmos de selección de tiempo lineal, la constante oculta es muy alta, alrededor de 24 . Eso significa que un algoritmo O (nlog n) será típicamente más rápido para menos de varios millones de elementos.

De lo contrario, en el caso general, cuando solo puede comparar 2 elementos y determinar cuál es mayor, el problema se resuelve mejor mediante una estructura de datos de stack .

Supongamos que quiere la parte superior de n elementos. Todas las soluciones basadas en ordenar completamente los datos requieren tiempo O (nlog n), mientras que usar un montón solo requiere tiempo O (nlog k) – solo construye un montón sobre los primeros k elementos, luego sigue agregando un elemento y eliminando el máximo. Esto te dejará con un montón que contiene los elementos k más pequeños.

¿Qué hay de delegar todo a 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 } 

No estoy tratando de decir que esta es la mejor manera. Sigo pensando que el método de Yin Zhu para encontrar el k-ésimo elemento más grande es la mejor respuesta.

Sí, puede hacerlo en O (n) simplemente manteniendo una lista de ejecución (ordenada) de la parte superior N. Puede ordenar la lista en ejecución usando las funciones de biblioteca normales o una red de clasificación . Por ejemplo, una demostración simple usando 3 y mostrando qué elementos en la lista de ejecución cambian cada iteración.

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 

La mejor solución es usar las facilidades que brinde el idioma elegido, lo que hará que su vida sea más fácil.

Sin embargo, asumiendo que esta era una pregunta más relacionada con el algoritmo que debe elegir, voy a sugerir un enfoque diferente aquí. Si habla de 10 de 100, generalmente no debería preocuparse demasiado por el rendimiento a menos que quiera hacerlo muchas veces por segundo.

Por ejemplo, este código C (que es tan ineficiente como puedo hacerlo sin ser tonto) aún tarda mucho menos de una décima de segundo en ejecutarse. No es suficiente tiempo para pensar siquiera en ir a tomar un 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; } 

Ejecutarlo a través del time te da (he formateado la salida un poco para que sea legible, pero no ha afectado los 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 

Solo cuando las cantidades de los números se vuelvan grandes, por lo general debes preocuparte. No me malinterpretes, no digo que no debas pensar en el rendimiento. Lo que no debes hacer es perder demasiado tiempo optimizando cosas que no importan: YAGNI y todo ese jazz.

Al igual que con todas las preguntas de optimización, ¡no lo adivine!

Bueno, puede crear un montón de una matriz no ordenada en el tiempo O (n), y puede obtener el elemento superior del montón en el tiempo O (log (n)). Entonces, su tiempo de ejecución total es O (n + k * log (n)).

Escrito debajo de ambas implementaciones de ordenación de selección e inserción. Para un conjunto de datos más grande, sugiero que el tipo de inserta sea mejor que el tipo de selección

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

Implementación de la clase de inserción:

 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); } } 

Implementación del tipo de selección:

 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); } } 

Sí, hay una manera de hacerlo mejor que la vía rápida. Como señala Yin Zhu, primero puedes buscar el elemento k-ésimo más grande y luego usar ese valor de elemento como tu pivote para dividir el conjunto

Me pidieron el mismo algoritmo en la entrevista. Lo hice, si alguien puede comparar eso con el algoritmo más rápido en Java, será muy ú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; } 

y prueba para eso:

 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; } 

El resultado es algo así 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 de resultado promedio, para obtener 1000 enteros máximos de un conjunto de 100.000,000 elementos iniciales. ¡no está mal!

Acabo de probar ese conjunto desde arriba:

 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] 

El mejor algoritmo dependerá en gran medida del tamaño de K. Si K es pequeño, entonces simplemente siguiendo el algoritmo BubbleSort e iterando el ciclo externo K veces daría los valores K superiores. La complejidad será O (n * k).

Sin embargo, para valores de K cercanos a n la complejidad se aproximará a O (n ^ 2). En tal escenario, quicksort podría ser una buena 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); } } 

Puede usar List y la clase de Comparators de guayaba para obtener los resultados deseados. Es una solución altamente optimizada. Por favor, vea una muestra a continuación, que obtiene los 5 primeros números. Api se puede encontrar aquí .

 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); } } 

Salida: [9, 8, 7, 6, 5]