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()ではなくで開始され、現在のスレッドでメソッドを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/JoinAtomicReferenceArray<E>を使用し、 a の代わりにan を使用Listして、スレッドセーフな方法でその場で並べ替えを行うことをお勧めします。

于 2012-05-06T19:20:40.873 に答える
0

別の解決策 (Java 5 以降を実行していると仮定) はcurrentThreads、揮発性クラス メンバーとして宣言できます。

private static volatile int currentThreads = 0;

volatileキーワードの詳細については、こちらをご覧ください。

于 2012-05-06T19:28:03.350 に答える