为什么我的线程排序算法比非线程版本慢？

我已经实现了合并排序的线程版本。 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

为什么我的线程排序算法比非线程版本慢？

回答

相关问题