爲什麼我的線程排序算法比非線程版本慢？

我已經實現了合併排序的線程版本。 ThreadedMerge.java：http://pastebin.com/5ZEvU6BV 爲什麼我的線程排序算法比非線程版本慢？

因爲合併排序是一個分而治之的算法，所以我爲每個數組的一半創建一個線程。但在Java虛擬機可用的編緝線程的數量是有限的，所以我檢查創建線程之前：

if(num <= nrOfProcessors){ 
    num += 2; 
    //create more threads 
}else{ 
    //continue without threading 
}

但是螺紋排序約需~ 6000 ms同時非線程版本是隻~ 2500 ms快得多。

非螺紋：http://pastebin.com/7FdhZ4Fw

爲什麼線程版本慢，我該如何解決這個問題？

更新：我現在用atomic integer線程計數，並宣佈靜態字段Runtime.getRuntime().availableProcessors()。現在排序大約需要~ 1400 ms。

但是創造歸併方法只有一個線程，並讓當前線程完成剩下的沒有sigificant的性能提升。 爲什麼？

而且當後我請一個線程，該減量後使用的線程數聯同

num.set(num.intValue() - 1);

排序約需~ 200 ms更長的時間。這裏是我的算法的更新http://pastebin.com/NTZq5zQp爲什麼這行代碼使它更糟？

來源

2011-05-07 Lost in OWL

我不知道你的數據，但創建線程的爲小型陣列的開銷會很容易超過平行收益。另外，你知道這些線程是否真的在不同的處理器中？ – entonio 2011-05-07 23:03:24

HHM，你不應該創建每一個步驟一個線程（它們是昂貴，而且有重量輕的選擇。）

理想情況下，你應該只創建4個線程，如果有4個CPU's。

所以let's說你有4個CPU's，然後創建在第一級一個線程（現在你有2個），並在第二個層次，你還可以創建一個新的線程。這給了你4

你之所以只能創建一個，而不是二是，你可以使用你當前正在運行，如螺紋：

Thread t = new Thread(...); 
t.start(); 

// Do half of the job here 

t.join(); // Wait for the other half to complete.

如果你有，let's說，5 CPU （而不是兩者的權力），那麼只需創建8個線程。

在實踐中做到這一點的一個簡單方法是創建在達到適當級別時已經創建的非線程版本。這樣，當if語句等時，你可以避免混淆合併方法。

來源

2011-05-07 23:03:49

感謝迄今，我已更新我的問題。 – 2011-05-08 08:51:30

將你的代碼分成兩部分:)一個做實際的排序和一個啓動線程。這會容易得多。在我的筆記本電腦上（雙核），你的代碼開始了4個線程，所以在處理你的線程時有些不妥。 – 2011-05-08 09:10:24

我只是將最大數目設置爲4，與創建1000個線程相比，性能沒有改變：D。爲什麼不擁有這1000個線程，並以相同的方式爲每個線程分配整個計算工作量？ – 2011-05-08 09:24:13

第一關你的訪問num是不是線程安全的（檢查http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html）

您創建的進程核心等量但你阻止它們的一半與加入通話

num += 1; 
ThreadedMerge tm1 = new ThreadedMerge(array, startIndex, startIndex + halfLength); 
tm1.start(); 
sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex); 
try{ 
    tm1.join(); 
    num-=1 
    sortedLeftPart = tm1.list; 
}catch(InterruptedException e){ 
}

這並未」 t阻止調用線程，但使用它來排序右側部分，並讓創建的線程執行另一個部分，當該線程返回其佔用的空間時可以被另一個線程使用

來源

2011-05-07 23:04:26

感謝至今，我更新了我的問題。 – 2011-05-08 08:50:38

對Runtime.availableProcessors() ap梨將佔用相當多的額外時間。你只需要調用它一次，所以只是將它的方法之外，並把它定義爲一個靜態的，例如：

static int nrOfProcessors = Runtime.getRuntime().availableProcessors();

來源

2011-05-07 23:10:25 WhiteFang34

爲什麼我的線程排序算法比非線程版本慢？

回答

相關問題