So sánh số nguyên Java: lớn hơn

Question

Tôi có một mảng gồm một triệu số nguyên vì tôi đang thử nghiệm với quicksort song song. Tôi có những hành vi kỳ lạ sau đôi:

Để kiểm tra thời tiết mảng được sắp xếp một cách chính xác tôi bước vào đoạn mã sau sau khi phân loại:

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!"); 

Trong một số trường hợp tôi nhận được đầu ra lỗi mà nó không được sắp xếp một cách chính xác và khi tôi gỡ lỗi, tôi tìm thấy thông tin sau (ví dụ: luôn khác nhau):

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

(thử bỏ qua các số, không phải bất kỳ giá trị hoặc dải ô cụ thể nào) Vì vậy, luôn trong trường hợp giá trị bên trái bằng giá trị phù hợp. Vâng, để so sánh lớn hơn điều này sẽ trở lại sai, nhưng tôi chắc chắn có được đầu ra.

Cái quái gì vậy !?

Tôi thậm chí đã kiểm tra chéo mảng và nó được sắp xếp chính xác. Nếu tôi vẽ một mảng nhỏ (khoảng 100) nó cũng tốt. Tôi đã bỏ lỡ điều gì đó tâm trí của tôi lừa tôi?

Sửa 21:32 (UTC + 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); 
      } 
     } 
    } 

tôi một tham gia vào các chủ đề mà khởi loại song song. Thread đầu tiên xuất hiện tối đa 4 luồng tối đa cùng một lúc. Tôi không chắc chắn 100% những gì concurrency nó có thể được, như tôi có thể nhìn thấy trong trình gỡ lỗi mảng được sắp xếp. Tôi sẽ thêm đầu ra của hai số nguyên và có một cái nhìn khác.

Edited 23/05/12 16:46 UTC + 1

tôi đã thay đổi toàn bộ điều để làm việc với các mới, và thực sự dễ dàng, ForkJoinPool từ JDK 1.7. Tested với mảng số nguyên lên đến 10 mio số nguyên và có kết quả thú vị: Tôi đã thử nghiệm nó trên một Core2Duo (2010) MacBook Pro và Core-i5 (2011) Windows 7:

Core2Duo và i5 có thể làm hyperthreading, vì vậy Bây giờ tôi đã thử nghiệm với availableProcessors() * 2 -> core2duo có một chút tăng tốc để tăng tốc lên 1.8 và 1.7 cho 2 luồng; i5 hiện đang có tốc độ tăng gấp 3,2 lần với tối đa 8 chủ đề cho mỗi bộ xử lý sẵn có() * 2

Vẫn thử nghiệm máy tính của tôi. Tất cả các thử nghiệm đã được thực hiện với cùng một mảng và mức trung bình được tính từ 1000 lần lặp sắp xếp trên mỗi kích thước mảng.

Answer 1

Nhìn qua mã của bạn, bạn đẻ trứng một sợi nhưng ngay sau đó tham gia lại cho các chủ đề thực hiện chính:

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

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

     try { 
      t1.join(); 

Câu hỏi đặt ra trở thành - bạn đang làm gì w/trong các thói quen Quicksort_Parallel? Bạn có sinh ra các chủ đề bổ sung không? Bạn có đang tham gia trên tất cả trong số họ không? Nếu không, bạn đã tạo ra một điều kiện chủng tộc có thể giải thích kết quả bạn đang thấy.

Answer 2

Bạn có thể là nạn nhân của tình trạng chủng tộc, điều này có nghĩa là đầu ra của bạn phụ thuộc vào chuỗi các sự kiện khác.Vì vậy, nếu bạn có một chủ đề đang hoạt động nhanh hơn, bạn sẽ nhận được một điều kiện chủng tộc. Một cách để ngăn chặn điều này là sử dụng semaphores hoặc chia vòng lặp của bạn trong số các chủ đề. Làm thế nào bạn đang làm sắp xếp của bạn? Bạn đang sử dụng giảm?

Answer 3

Nếu bạn đang sử dụng Java SE 7, hãy xem xét sử dụng nĩa mới/join 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