clasificación 50 000 000 números

Question

Supongamos que tenemos que ordenar 50 000 000 números. supongamos que los números están almacenados en un archivo. ¿Cuál es el algoritmo más eficiente para resolver este problema? Algoritmo paralelo para ordenar ...

¿Cómo hacerlo? Tal vínculo útil)

no puedo usar algoritmo estándar

tanto, le pido acerca de los métodos y algoritmos :)

Ok .. He leído acerca de mergesort paralelo ... Pero no está claro para mí .

solución, la primera versión

code is located here

Answer 1

Desde la parte superior de mi cabeza, merge sort parece ser la mejor opción cuando se trata de paralelización y distribución, ya que utiliza divide y -conquer enfoque. Para obtener más información, google para "fusión paralela ordenar" y "tipo de combinación distribuida".

Para de una sola máquina, varios núcleos ejemplo, consulte ver Correctly multithreaded quicksort or mergesort algo in Java?. Si puede usar Java 7 fork/join, consulte: "Java 7: more concurrency" y "Parallelism with Fork/Join in Java 7".

Para distribuirlo sobre muchas máquinas, ver Hadoop, tiene una aplicación de combinación de tipo distribuido: ver MergeSort y MergeSorter. También de interés: Hadoop Sorts a Petabyte in 16.25 Hours and a Terabyte in 62 Seconds

Answer 2

para la clasificación de muchos elementos, su mejor tiro es Merge Sort. Por lo general, son los algoritmos utilizados por las bases de datos. Aunque no es tan rápido como Quick Sort, usa almacenamiento intermedio por lo que no necesita grandes cantidades de memoria para realizar el ordenamiento.

Además, como lo señalan sje397 y Scott en los comentarios, Merge Sort es altamente paralelizable.

Answer 3

Depende mucho del dominio del problema. Por ejemplo, si todos los números son positivos, la mejor manera puede ser hacer una matriz de 0-MAX_INT y luego simplemente contar cuántas veces ocurre cada número al leer el archivo, y luego imprimir cada int con un no- cero cuente sin embargo muchas veces ocurrió. Ese es un O (n) "género". Hay un nombre oficial para ese tipo, pero olvido lo que es.

Por cierto, me hicieron esta pregunta en una entrevista de Google. A partir de las limitaciones del problema, se me ocurrió esta solución, y parecía ser la respuesta que estaban buscando. (Rechacé el trabajo porque no quería moverse.)

Answer 4

No son tantos. Si tienen 10 bytes de longitud extendida, por ejemplo, sería una matriz de 500Mbytes, ¡casi puede permanecer en mi teléfono! ;) Entonces yo diría que vaya por Quicksort si es solo eso.

Answer 5

50 millones no es particularmente grande. Solo los leería en la memoria. Ordenarlos y escribirlos. Debería tomar solo unos segundos. ¿Qué tan rápido lo necesitas? ¿Cuán compilado es necesario que sea?

En mi viejo laboratorio, tomó 28 segundos. Si tuviera más procesadores, podría ser un poco más rápido, pero pasaría la mayor parte del tiempo leyendo y escribiendo el archivo (15 segundos), que no sería más rápido.

Uno de los factores críticos es el tamaño de su caché. La comparación en sí es muy económica siempre que los datos estén en caché. Como la caché L3 se comparte, un hilo es todo lo que necesita para hacer un uso completo de la misma.

public static void main(String...args) throws IOException { 
    generateFile(); 

    long start = System.currentTimeMillis(); 
    int[] nums = readFile("numbers.bin"); 
    Arrays.sort(nums); 
    writeFile("numbers2.bin", nums); 
    long time = System.currentTimeMillis() - start; 
    System.out.println("Took "+time+" secs to sort "+nums.length+" numbers."); 
} 

private static void generateFile() throws IOException { 
    Random rand = new Random(); 
    int[] ints = new int[50*1000*1000]; 
    for(int i= 0;i<ints.length;i++) 
     ints[i] = rand.nextInt(); 
    writeFile("numbers.bin", ints); 
} 

private static int[] readFile(String filename) throws IOException { 
    DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(filename), 64*1024)); 
    int len = dis.readInt(); 
    int[] ints = new int[len]; 
    for(int i=0;i<len;i++) 
     ints[i] = dis.readInt(); 
    return ints; 
} 

private static void writeFile(String name, int[] numbers) throws IOException { 
    DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(name), 64*1024)); 
    dos.writeInt(numbers.length); 
    for (int number : numbers) 
     dos.writeInt(number); 
    dos.close(); 
} 

Answer 6

no tenga miedo del número grande. de hecho, 50 000 000 de números no es tan grande. Entonces, si los números son enteros, cada número tiene 4 bytes de tamaño, por lo que la memoria total que se debe asignar a esta matriz es de 50 000 000 * 4/1024/1024 = 190,7 Mega bytes, que es relativamente pequeño. Habiendo hecho los cálculos, puede proceder a hacer QuickSort que se ejecuta en O (nLogn). tenga en cuenta que el método de ordenamiento incorporado en matrices .net utiliza QuickSort, no estoy seguro si este es el caso también en Java.

clasificación 250 000 000 enteros en mi máquina tomó unos 2 minutos por lo que ir a por ello :)

Answer 7

números 50e6 es muy pequeña hoy en día, no hacer las cosas más complejas de lo que tienen que ser ...

bash$ sort <file> sorted.file