为什么我的线程排序算法比非线程版本慢？
我刚刚实现了合并排序的线程版本。 ThreadedMerge.java：http://pastebin.com/5ZEvU6BV
由于合并排序是分而治之算法我为数组的每一半创建一个线程。但是 Java-VM 中可用线程的数量是有限的，因此我在创建线程之前检查了这一点：
if(num <= nrOfProcessors){
num += 2;
//create more threads
}else{
//continue without threading
}
但是，线程排序大约需要 ~ 6000 ms，而非线程版本则要快得多，只需 约 2500 毫秒。
非线程：http://pastebin.com/7FdhZ4Fw
为什么是线程版本速度较慢，我该如何解决这个问题？
更新：我现在使用原子整数进行线程计数，并为Runtime.getRuntime().availableProcessors()声明了一个静态字段。现在排序大约需要~ 1400 ms。
然而，在 mergeSort 方法中仅创建一个线程并让当前线程执行其余操作并不会显着提高性能。 为什么？
减少使用的线程数，
num.set(num.intValue() - 1);
此外，当我在线程上调用 join 之后，然后通过排序 需要大约 ~ 200 ms 更长的时间。这是我的算法的更新 http://pastebin.com/NTZq5zQp 为什么这行代码使它均匀更糟？
I just have implemented a threaded version of the merge sort. ThreadedMerge.java: http://pastebin.com/5ZEvU6BV
Since merge sort is a divide and conquer algorithm I create a thread for every half of the array. But the number of avialable threads in Java-VM is limited so I check that before creating threads:
if(num <= nrOfProcessors){
num += 2;
//create more threads
}else{
//continue without threading
}
However the threaded sorting takes about ~ 6000 ms while the non-threaded version is much faster with just ~ 2500 ms.
Non-Threaded: http://pastebin.com/7FdhZ4Fw
Why is the threaded version slower and how do I solve that problem?
Update: I use atomic integer now for thread counting and declared a static field for Runtime.getRuntime().availableProcessors(). The sorting takes about ~ 1400 ms now.
However creating just one thread in the mergeSort method and let the current thread do the rest has no sigificant performance increase. Why?
Besides when after I call join on a thread and after that decrement the number of used threads with
num.set(num.intValue() - 1);
the sorting takes about ~ 200 ms longer. Here is the update of my algorithm http://pastebin.com/NTZq5zQp Why does this line of code make it even worse?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，您对 num 的访问不是线程安全的（检查 http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html ）
您创建了与核心相同数量的进程，但您阻止了其中一半使用 join 调用，
这不会阻塞调用线程，而是使用它对正确的部分进行排序，并让创建的线程在返回它占用的空间时执行另一部分，可供另一个线程使用
first off your accesses to num is not threadsafe (check http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html )
you create an equal amount of processes to cores but you block half of them with the join call
this doesn't block the calling thread but uses it to sort the right part and let the created thread do the other part when that one returns the space it takes up can be used by another thread
嗯，您不应该为每个步骤创建一个线程（它们很昂贵并且有轻量级替代方案。）
理想情况下，如果有 4 个 CPU，您应该只创建 4 个线程。
假设您有 4 个 CPU，那么您在第一级创建一个线程（现在您有 2 个），在第二级您还创建一个新线程。这给了你 4。
你只创建一个而不是两个的原因是你可以使用当前正在运行的线程，例如：
如果你有，比方说，5 个 CPU（不是 2 的幂），那么只需创建8个线程。
在实践中执行此操作的一种简单方法是，当您达到适当的级别时，创建您已经制作的无线程版本。通过这种方式，您可以避免在使用 if 语句等时使合并方法变得混乱。
Hhm, you should not create a thread for every single step (they are expensive and there are lightweight alternatives.)
Ideally, you should only create 4 threads if there are 4 CPU´s.
So let´s say you have 4 CPU´s, then you create one thread at the first level (now you have 2) and at the second level you also create a new thread. This gives you 4.
The reason why you only create one and not two is that you can use the thread you are currently running like:
If you have, let´s say, 5 CPU´s (not in the power of two) then just create 8 threads.
One simple way to do this in practice, is to create the un-threaded version you already made when you reach the appropriate level. In this way you avoid to clutter the merge method when if-sentences etc.
对 Runtime.availableProcessors() 的调用似乎占用了相当多的额外时间。您只需要调用它一次，因此只需将其移到方法之外并将其定义为静态，例如：
The call to
Runtime.availableProcessors()appears to be taking up a fair amount of extra time. You only need to call it once, so just move it outside of the method and define it as a static, e.g.: