2012-05-22 19 views
5

से अधिक मेरे पास एक मिलियन पूर्णांक की एक सरणी है क्योंकि मैं समांतर quicksort के साथ प्रयोग कर रहा हूं।जावा इंटीजर तुलना:

जांच करने के लिए मौसम सरणी सही ढंग से हल कर रहा था मैं छँटाई के बाद निम्नलिखित कोड में प्रवेश किया:

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

कुछ मामलों मैं त्रुटि उत्पादन कि इसे सही ढंग से हल नहीं किया गया था मिल में मैं निम्नलिखित अजीब व्यवहार कभी कभी है , और जब मैं डिबग मैं निम्नलिखित (उदाहरण के लिए, हमेशा अलग) पाते हैं:

j = 1942 array_parallel [1942] = 6000; array_parallel [1 9 43] = 6000;

(संख्या अनदेखी, इसकी न कोई विशेष मान या श्रेणी कोशिश) तो इसकी हमेशा ऐसे मामलों में जहां छोड़ दिया मूल्य सही मूल्य के बराबर में। ठीक है, अधिक की तुलना में यह झूठी में वापस आना चाहिए, लेकिन मुझे निश्चित रूप से आउटपुट मिलता है।

क्या गलत है !?

मैंने भी सरणी की जांच की है और इसे सही ढंग से क्रमबद्ध किया गया है। अगर मैं एक छोटी सी सरणी (लगभग 100) प्लॉट करता हूं तो यह भी ठीक है। क्या मुझे कुछ याद आया क्या मेरा दिमाग मुझे चाल करता है?

संपादित 21:32 (यूटीसी +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); 
      } 
     } 
    } 

मैं एक धागा है कि समानांतर तरह शुरू की पर शामिल होते हैं। एक ही समय में अधिकतम 4 धागे तक स्पॉन की तुलना में पहला थ्रेड। मैं 100% निश्चित नहीं हूं कि यह कितना समेकन हो सकता है, क्योंकि मैं डीबगर में देख सकता हूं कि सरणी क्रमबद्ध है। मैं दो पूर्णांक के आउटपुट को जोड़ दूंगा और एक और नजर रखूंगा।

संपादित 23/05/12 16:46 यूटीसी +1

मैं नए के साथ काम करने से पूरी बात बदल रहा था, और वास्तव में आसान, ForkJoinPool JDK 1.7 से। 10 Mio पूर्णांकों अप करने के लिए पूर्णांक सरणियों के साथ परीक्षण किया गया और दिलचस्प परिणाम मिल गया: मैं एक Core2Duo (2010) मैकबुक प्रो और कोर-i5 (2011) विंडोज 7 पर यह परीक्षण किया है: तो

core2duo और i5 हाइपरथ्रेडिंग कर सकते हैं, मैंने अब उपलब्ध प्रोसेसर() * 2 के साथ परीक्षण किया -> कोर 2duo को 2 थ्रेड के लिए 1.8 और 1.7 तक गति के लिए थोड़ा बढ़ावा मिला; i5 वर्तमान में प्रति उपलब्ध 8 धागे के साथ 3.2 की गति के आसपास है प्रोसेसर() * 2

अभी भी मेरी मशीन से बाहर निकलने का प्रयोग कर रहा है। सभी परीक्षण एक ही सरणी के साथ किए गए थे और औसत को प्रत्येक सरणी आकार पर 1000 सॉर्टिंग पुनरावृत्तियों से गणना की गई थी।

+1

आप चलाने के अपने एकाधिक धागे में एल्गोरिदम सॉर्टिंग? – assylias

+0

हाँ मैं करता हूं। लेकिन जब मैं तुलना करता हूं तो वे समाप्त हो जाते हैं। – Stefan

+0

क्या यह एक int या इंटीजर है? –

उत्तर

3

अपने कोड के माध्यम से देख रहे हैं, तो आप एक धागा अंडे लेकिन फिर तुरंत यह मुख्य निष्पादन धागा करने के लिए वापस शामिल हो:

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

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

     try { 
      t1.join(); 

प्रश्न बन जाता है - तुम क्या कर रहे w/Quicksort_Parallel दिनचर्या में? क्या आप अतिरिक्त धागे पैदा कर रहे हैं? क्या आप पर सभी पर शामिल हो रहे हैं? यदि नहीं, तो आपने एक दौड़ की स्थिति बनाई है जो आपके द्वारा देखे जा रहे परिणामों की व्याख्या करेगी।

+0

जैसा कि मैंने उपरोक्त टिप्पणियों में उल्लेख किया है, मेरे quicksort_parallel 3 अन्य थ्रेड तक पहुंच सकता है। मैं वहां शामिल नहीं हूं - इसलिए हमने कहा कि यह दौड़ की स्थिति है। अगर मैं quicksort_parallel में शामिल होता हूं तो मेरी सॉर्टिंग "सामान्य" क्विकॉर्ट से बहुत धीमी है। – Stefan

+0

स्पॉन्गिंग धागे से जुड़े ओवरहेड हैं। क्या समांतरता से लाभ उठाने के लिए काम काफी बड़ा किया जा सकता है? – Mike

+0

मैं 10 मिलियन पूर्णांक के साथ परीक्षण करता हूं। – Stefan

1

आप दौड़ की स्थिति का शिकार हो सकते हैं, इसका मतलब है कि आपका आउटपुट अन्य घटनाओं के अनुक्रम पर निर्भर है।तो यदि आपके पास एक धागा है जो तेजी से काम कर रहा है तो आपको दौड़ की स्थिति मिल जाएगी। इसे रोकने का एक तरीका सेमफोर का उपयोग कर रहा है या धागे के बीच अपने लूप को विभाजित कर रहा है। आप अपनी तरह कैसे कर रहे हैं? क्या आप कमी का उपयोग कर रहे हैं?

1

आप जावा SE 7 का उपयोग कर रहे हैं, नए कांटा का उपयोग करने पर विचार करें/में शामिल होने के एपीआई:

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

+0

संकेत के लिए धन्यवाद - मैंने आज एक फोर्कजोइनपूल को एक और संस्करण में कार्यान्वित किया और औसत गति 1 माइओ पूर्णांक के लिए लगभग 1.5 है। 100 मीओ पूर्णांक के साथ एक बड़ा परीक्षण उत्पन्न करेगा और चारों ओर खेलेंगे। लेकिन 1।5 अभी भी बहुत कुछ नहीं है और न कि मैं क्या उम्मीद कर रहा था और उम्मीद कर रहा हूं कि – Stefan

+0

आपके पास कितने कोर हैं? – Puce

+0

इसके इंटेल कोर 2 डुओ (2010)। 2011 के अंत में कोर-आई 5 – Stefan