multithreading合并排序算法
我有一个类在genericsList上进行一些递归合并排序，只要该元素实现Comparable。 我正在尝试使代码multithreading以提高性能，为此，我有一个静态变量maxThreads ，它保持我创建的线程数不爆炸，我有一个静态变量currentThreads跟踪我目前运行的线程数。 我的currentThreads变量似乎存在竞争条件，但我无法找到解决方案来修复它。
import java.util.ArrayList; import java.util.List; public class ThreadedMergeSorter<E extends Comparable> implements, Runnable { private List list; private List left, right; private Thread t1, t2; private static final int maxThreads = 4; private static AtomicInteger currentThreads = new AtomicInteger(0); private ThreadedMergeSorter(List list) { this.list = list; } public ThreadedMergeSorter(){} /** * Sorts a List using the merge sorting algorithm * @param list the list to be merge sorted * @return * @throws InterruptedException */ public void sort(List list) { if(list.size() > 1) { left = new ArrayList(list.subList(0, list.size()/2)); right = new ArrayList(list.subList(list.size()/2, list.size())); list.clear(); if(currentThreads.get() < maxThreads) { t1 = new Thread(new ThreadedMergeSorter(left)); t1.start(); currentThreads.incrementAndGet(); } else sort(left); if(currentThreads.get() < maxThreads) { t2 = new Thread(new ThreadedMergeSorter(right)); t2.start(); currentThreads.incrementAndGet(); } else sort(right); try{ if(t1 != null) { t1.join(); currentThreads.decrementAndGet(); } if(t2 != null) { t2.join(); currentThreads.decrementAndGet(); } }catch(InterruptedException e){} list.addAll(mergeSortedLists(left, right)); } } /** * Merges two previously sorted List<E extends Comparable> into a single List * @param leftArray a List of previously sorted elements * @param rightArray a List of previously sorted elements * @return an new sorted List */ private List mergeSortedLists(List leftList, List rightList) { ArrayList list = new ArrayList(); while(!leftList.isEmpty() && !rightList.isEmpty()) { if((leftList.get(0)).compareTo(rightList.get(0)) <= 0) list.add(leftList.remove(0)); else list.add(rightList.remove(0)); } if(!leftList.isEmpty()) list.addAll(leftList); if(!rightList.isEmpty()) list.addAll(rightList); return list; } @Override public void run() { sort(this.list); } }
问题出在if语句和try catch块的sort(List list)方法中。
首先，你没有并行运行任何东西。 线程以start()而不是run() ，它只是调用当前线程上的run方法。
其次，如果您要更新共享变量，请尝试将它们声明为AtomicInteger ：
private static AtomicInteger currentThreads = new AtomicInteger(0);
然后使用这些方法以primefaces方式递增/递减：
currentThreads.incrementAndGet(); currentThreads.decrementAndGet();
不要不断创建，终止和销毁线程。 不要试图微观管理线程 – 这是非常困难和容易出错的，正如你已经发现的那样。
如果你想断开合并排序，（并且这不是一个坏主意:)，请查看ThreadPoolExecutor和CountDownLatch。
如果您使用的是Java 7，我建议使用新的Fork / Join ，并使用AtomicReferenceArray而不是List以便您可以以线程安全的方式进行排序。
另一个解决方案（假设您运行的是Java 5和更新版本）可以将currentThreads声明为volatile类成员：
private static volatile int currentThreads = 0;
您可以在此处详细了解volatile关键字。