Comparación de Java Integer: mayor que

Question

Tengo una matriz de un millón de enteros porque estoy experimentando con Quicksort paralelo. Tengo el siguiente comportamiento extraño veces:

Para comprobado si la matriz se solucionó correctamente entré en el siguiente código después de la clasificación:

for(int j=0; j < array_parallel.length-1; ++j) 
    if(array_parallel[j] > array_parallel[j+1]) 
    System.out.println("ERROR! NOT SORTED CORRECTLY!"); 

En algunos casos me da la salida de error que no se solucionó correctamente , y cuando depuro encuentro lo siguiente (ejemplo, siempre diferente):

j = 1942 array_parallel [1942] = 6000; array_parallel [1943] = 6000;

(intente ignorar los números, no es cualquier valor o rango específico) lo que su siempre en los casos en que el valor de la izquierda es igual al valor correcto. Bueno, para la comparación de mayor esto debería regresar en falso, pero definitivamente obtengo el resultado.

¿Qué diablos está mal?

Incluso compruebo la matriz y está ordenada correctamente. Si trazo una pequeña matriz (alrededor de 100) también está bien. ¿Echo de menos algo que mi mente me engaña?

Editado 21:32 (GMT + 1):

private static int ANZAHL = 1000000;  // Größe des Arrays 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     int array_single[] = new int[ANZAHL]; 
     int array_parallel[] = new int[ANZAHL]; 

     Speedmeasure sp_single = new Speedmeasure(); 
     Speedmeasure sp_parallel = new Speedmeasure(); 
     ArrayReader ar = null; 

     try { 
      ar = new ArrayReader(array_single, array_parallel); 
     } catch (FileNotFoundException e1) { 
      // TODO Auto-generated catch block 
      e1.printStackTrace(); 
     } catch (IOException e1) { 
      // TODO Auto-generated catch block 
      e1.printStackTrace(); 
     } catch (ClassNotFoundException e1) { 
      // TODO Auto-generated catch block 
      e1.printStackTrace(); 
     } 

     if(ar == null) { 
      System.err.println("Großes Problem. Lass es sein!"); 
      System.exit(-1); 
     } 
     else { 

      for(int i=0; i < 5; ++i) { 
       Quicksort_Single qs = new Quicksort_Single(); 
       sp_single.setStart(System.currentTimeMillis()); 

       qs.quicksort_start(array_single); 
       sp_single.setStop(System.currentTimeMillis()); 

       //printArray(array); 
       PrintSpeed(sp_single.getSpeed(), "Single"); 


       System.out.print("\nUnd jetzt treiben wir es parallel! \n\n"); 
       Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel)); 

       sp_parallel.setStart(System.currentTimeMillis()); 
       t1.start(); 

       try { 
        t1.join(); 
       } catch (InterruptedException e) { 
        // TODO Auto-generated catch block 
        e.printStackTrace(); 
       } 

       sp_parallel.setStop(System.currentTimeMillis()); 

       //printArray(array_parallel); 
       PrintSpeed(sp_parallel.getSpeed(),"Parallel"); 

       System.out.println("Speed up was: "+sp_parallel.calcSpeedup(sp_single.getSpeed(), sp_parallel.getSpeed())); 
       System.out.println("******************************************"); 

       for(int j=0; j < array_single.length-1; ++j) 
        if(array_single[j] > array_single[j+1]) 
         System.out.println("ERROR! NICHT SORTIERT KORREKT BEI SINGLE!"); 

       for(int j=0; j < array_parallel.length-1; ++j) 
        if(array_parallel[j] > array_parallel[j+1]) 
         System.out.println("ERROR! NICHT SORTIERT KORREKT BEI PARALLEL!"); 



       ar.copyArray(array_single, array_parallel); 
      } 
     } 
    } 

me uno a un hilo en el que inicia el tipo paralelo. El primer subproceso que genera hasta 4 subprocesos como máximo al mismo tiempo. No estoy 100% seguro de qué concurrencia podría ser, como puedo ver en el depurador, la matriz está ordenada. Agregaré el resultado de los dos enteros y tendré otro aspecto.

Editado 23/05/12 16:46 GMT + 1

yo estaba cambiando todo lo que hay que trabajar con el nuevo, y realmente fácil, ForkJoinPool de JDK 1.7. probado con matrices de enteros máximo de 10 millones de números enteros y tiene resultados interesantes: he probado en un Core2Duo (2010) MacBook Pro y Core i5 (2011) de Windows 7:

Core2Duo e i5 pueden hacer hyperthreading es así, probé ahora con availableProcessors() * 2 -> core2duo recibió un poco de impulso para acelerar a 1.8 y 1.7 para 2 hilos; i5 se encuentra actualmente en una aceleración de 3.2 con hasta 8 hilos por cadaprocesadorProcesadores() * 2

Todavía experimentando la mierda de mi máquina. Todas las pruebas se realizaron con las mismas matrices y el promedio se calculó a partir de 1000 iteraciones de clasificación sobre cada tamaño de matriz.

Answer 1

Mirando a través de su código, se generará un subproceso pero luego unirse inmediatamente de nuevo al subproceso de ejecución principal:

 Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel)); 

     sp_parallel.setStart(System.currentTimeMillis()); 
     t1.start(); 

     try { 
      t1.join(); 

La pregunta es - ¿qué haces w/en la rutina Quicksort_Parallel? ¿Estás generando hilos adicionales? ¿Estás haciendo un join en todos de ellos? Si no, has creado una condición de carrera que explicaría los resultados que estás viendo.

Answer 2

Puede ser una víctima de una condición de carrera, esto significa que su salida depende de la secuencia de otros eventos.Entonces, si tienes un hilo que funciona más rápido, obtendrás una condición de carrera. Una forma de detener esto es usar semáforos o dividir su ciclo entre los hilos. ¿Cómo estás haciendo tu tipo? ¿Estás usando una reducción?

Answer 3

Si está utilizando Java SE 7, considere utilizar el nuevo tenedor/unirse a la API:

http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinTask.html

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinWorkerThread.html