Buscar elementos N superiores en una matriz

Question

¿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 entró en mi cabeza era de 1. Ordenar que el uso de ordenación rápida, 2. dar los mejores 10.

pero ¿hay alguna alternativa mejor?

Answer 1

El tiempo podría reducirse a tiempo lineal:

1. Usa el selection algorithm, que encuentran efectivamente el elemento k-ésimo en una matriz-un ordenados en tiempo lineal. Puede usar una variante de ordenación rápida o algoritmos más robustos.

2. Consigue la parte superior k usando el pivote obtuvo en el paso 1.

Answer 2

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

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 

Answer 3

Sí hay una manera de hacerlo mejor que la clasificación rápida. Como señaló Yin Zhu, primero puede buscar el elemento k-ésimo más grande y luego usar ese valor de elemento como pivote para dividir el arreglo

Answer 4

La mejor solución es utilizar las instalaciones que proporcione el idioma elegido que le harán la vida 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, en general no debería preocuparse demasiado por el rendimiento a menos que desee hacerlo muchos veces por segundo.

Por ejemplo, este código C (que es casi tan ineficiente como puedo hacerlo sin ser estúpido) 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 <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

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

ejecución a través de time le da (He formateado la salida un poco para que sea legible, pero no han afectado a 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 

Sólo una vez que las cantidades de los números vuelven grande, por lo general, debe preocuparse. No me malinterprete, no estoy diciendo que no debería pensar sobre 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, medida no adivinar!

Answer 5

Si se trata de elementos simples como enteros de longitud fija, siempre que pueda ahorrar un búfer de memoria del mismo tamaño que los datos de entrada, la ordenación se puede hacer en O (n) tiempo utilizando el bote o raíz tipo, y este será el más rápido.

Aunque hay algoritmos de selección de tiempo lineal, the hidden constant is very high -- around 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 se pueden comparar 2 elementos y determinar cuál es mayor, el problema se resuelve mejor con un heap data structure.

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.

Answer 6

¿Qué hay de delegar todo a Java;)

function findTopN(Array list, int n) 
{ 
    Set sortedSet<Integer> = 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.

Answer 7

Bueno, puede crear un montón a partir 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)).

Answer 8

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 la prueba de que:

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 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 resultado de la media, para obtener 1.000 enteros máximo del conjunto de 100.000.000 elementos iniciales. ¡no está nada mal!

sólo trató 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] 

Answer 9

escrito debajo de ambas implementaciones selección ordenar y ordenar la inserción. Para mayor conjunto de datos Sugiero insetion especie mejor que la selección especie

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

ordenación por inserción Implementació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<length; i++) { 
     int curPos = i; 
     while ((curPos > 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);   
} 

} 

Selección Ordenar Implementació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<length; j++) { 
      if (values[j] > values[maxPos]) { 
       maxPos = j; 
      } 
     } 

     if (maxPos != i) { 
      int maxValue = values[maxPos]; 
      values[maxPos] = values[i]; 
      values[i] = maxValue; 
     }   
    } 
    return Arrays.copyOf(values, n);   
} 
} 

Answer 10

el mejor algoritmo sería de gran dependerá de la tamaño de K. Si K es pequeño, simplemente siguiendo el algoritmo BubbleSort e iterando el ciclo externo K veces wo uld da los mejores valores de K La complejidad será O (n * k).

Sin embargo, para valores de K próximos a n, la complejidad se aproximará a O (n^2). En tal escenario, quicksort podría ser una buena alternativa.

Answer 11

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<length; j++) { 
      if (values[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);   
} 
} 

Answer 12

Puede utilizar List y puede clase de guayaba Comparators 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 here.

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<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0); 
     final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5, 
       Comparator.<Integer>naturalOrder()); 
     final List<Integer> top = numbers.stream().collect(collector); 
     System.out.println(top); 
    } 

} 

de salida: [9, 8, 7, 6, 5]