1

我有一个类可以对通用列表进行一些递归合并排序，只要该元素实现 Comparable。我正在尝试使代码成为多线程以提高性能，为此，我有一个静态变量maxThreads来保持我创建的线程数不会爆炸，并且我有一个静态变量currentThreads来跟踪数量我目前正在运行的线程。我的变量似乎存在竞争条件currentThreads，但我无法提出解决方案来解决它。

import java.util.ArrayList;
import java.util.List;

public class ThreadedMergeSorter<E extends Comparable<? super E>> implements, Runnable  
{
  private List<E> list;
  private List<E> left, right;
  private Thread t1, t2;
  private static final int maxThreads = 4;
  private static AtomicInteger currentThreads = new AtomicInteger(0);

  private ThreadedMergeSorter(List<E> list)
  {
    this.list = list;
  }

  public ThreadedMergeSorter(){}


  /**
   * Sorts a List<E> using the merge sorting algorithm
   * @param list the list to be merge sorted
   * @return 
   * @throws InterruptedException 
   */
  public void sort(List<E> list) 
  {
    if(list.size() > 1)
    {                  
      left = new ArrayList<E>(list.subList(0, list.size()/2));
      right = new ArrayList<E>(list.subList(list.size()/2, list.size()));

      list.clear();

      if(currentThreads.get() < maxThreads)
      {
        t1 = new Thread(new ThreadedMergeSorter<E>(left));
        t1.start();
        currentThreads.incrementAndGet();
      }
      else sort(left);

      if(currentThreads.get() < maxThreads)
      {
        t2 = new Thread(new ThreadedMergeSorter<E>(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<E>> 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<E> mergeSortedLists(List<E> leftList, List<E> rightList)
  {
    ArrayList<E> list = new ArrayList<E>();

    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);
  }
}

问题在于语句和块的sort(List<E> list)方法。iftry catch

4

4 回答 4

3

首先，您没有并行运行任何东西。线程以start(), not开头run()，它只是调用run当前线程上的方法。

其次，如果您要更新共享变量，请尝试将它们声明为AtomicInteger：

private static AtomicInteger currentThreads = new AtomicInteger(0);

然后使用这些方法以原子方式递增/递减：

currentThreads.incrementAndGet();
currentThreads.decrementAndGet();
于 2012-05-06T19:15:52.080 回答
2

不要不断地创建、终止和销毁线程。不要尝试对线程进行微观管理 - 正如您所发现的那样，这非常困难且容易出错。

如果您想取消合并排序（这不是一个坏主意：），请查看 ThreadPoolExecutor 和 CountDownLatch。

于 2012-05-06T19:23:01.030 回答
0

如果您使用的是 Java 7，我建议您使用新的Fork/Join，并使用 anAtomicReferenceArray<E>而不是 a List，以便您可以以线程安全的方式进行就地排序。

于 2012-05-06T19:20:40.873 回答
0

另一个解决方案（假设您正在运行 Java 5 和更新版本）可以声明currentThreads为 volatile 类成员：

private static volatile int currentThreads = 0;

您可以在此处阅读有关volatile关键字的更多信息。

于 2012-05-06T19:28:03.350 回答