¿El método más rápido y eficiente para buscar los 3 mejores números?

Question

Actualmente tengo una matriz de alrededor de 8 a 10 números que cambian periódicamente.

Entonces, cada 5-10 segundos se actualizan los números.

Necesito obtener los 3 primeros números en la matriz cada 10 segundos.

Todo esto se hace en un dispositivo móvil.

La matriz es el RSSI de los puntos de acceso actualmente escaneados, así que en mi oficina de su por lo general alrededor de 10, pero en las pruebas de campo que podría aumentar a alrededor de 50.

En el momento en que iterar a través de la matriz 3 veces y cada vez saco los tres números más altos y los coloco en tres variables previamente declaradas.

Mi pregunta es, ¿qué debo hacer para aumentar la velocidad y la eficiencia en esta instancia?

Answer 1

Los números son solo 10, no hacer nada. Ya es lo suficientemente eficiente.

Si el tamaño aumenta, puede usar un max-heap para almacenar sus números.

Answer 2

Por qué no utilizar el método Arrays.sort que utiliza, hasta donde yo sé, quick sort debajo del capó.

Paul

EDIT: verifica que utiliza un tuned quick sort

Answer 3

Su algoritmo ya es O (n), más o menos rápida es> O (n log n) de manera que no es ciertamente la manera de hacerlo. Puede aumentar la velocidad a O (log n) si usa una estructura de árbol, por ejemplo, árbol AVL. En cuanto a las matrices solamente, la actual es la forma más rápida de hacerlo.

Answer 4

Su algoritmo actual necesita 3 * n comparaciones. Se podría realizar una variación de ordenación por inserción para mejorar esa:

1. Ponga los 3 primeros elementos de la matriz de entrada en la matriz de salida, una especie ellas
2. Iterar por el resto de los elementos de la matriz de entrada,
   1. Ponga cada elemento en la matriz de salida en la posición correcta
   2. Recorte la matriz de salida a 3 artículos

Esto necesita 2 * n comparaciones. (No estoy seguro si vale la pena la complejidad adicional, sin embargo)

Answer 5

Creo que en el caso general que debe usar, utilice el algoritmo QuickSelect que se basa en QuickSort y, en el tiempo O (n) modifica su matriz en línea y 'cuasi-ordenar'.

Supongamos que su matriz es A [1..10] y no está ordenada; al llamar a QuickSelect (A, 7), pregunta "¿Cuál es el número que, en la matriz ordenada debería estar en la séptima posición?", y eso es lo mismo que decir '¿Qué número es el tercero más grande en este conjunto particular?'.Ahora lo mejor es que QuickSelect asegura que después de esta llamada A [i] < = A [7] para todos 0 < i < 7 y que A [7] < = A [j] para todos 7 < j. Más información en wikipedia Quick Selection Algorithm.

De todas formas como el tamaño es 10, se puede utilizar la inserción-tipo (peor caso O (n^2), pero funciona bien con arreglos pequeños) y luego sumar los tres primeros/elementos últimos

EDIT: - Las estructuras de árbol son una exageración para solo diez elementos, y en general implica una compensación de tiempo/espacio (se necesitan muchos apuntadores) - QuickSelect tiene un O (n^2) escenario del peor de los casos, pero 'Median-of-Medians 'logra el mismo resultado en el peor de los casos O (n)