1

学校の課題として、少なくとも2つのスレッドを使用してマルチスレッドのクイックソートアルゴリズムを実行することになっていますが、コードに修正できない問題がいくつかあります。

編集：これは、マルチスレッドでない場合の外観です。これが機能することを確認しました。

public class Sorter
{
    private int[] mInts;

    public void QuickSort()
    {
        QuickSort(mInts, 0, mInts.Length - 1);
    }

    public Sorter(int[] ints)
    {
        mInts = ints;
    }

    private int Partition(int[] ints, int left, int right)
    {
        int pivotIndex = (right + left) / 2;
        int pivotValue = ints[pivotIndex];

        Swap(ints, right, pivotIndex);

        int storeIndex = left;

        for (int i = left; i <= right - 1; i++)
        {
            if (ints[i] < pivotValue)
            {
                Swap(ints, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(ints, storeIndex, right);

        return storeIndex;
    }

    private void Swap(int[] ints, int x, int y)
    {
        int temp = ints[x];
        ints[x] = ints[y];
        ints[y] = temp;
    }

    private void QuickSort(int[] ints, int left, int right)
    {
        if (left < right)
        {
            int newIndex = Partition(ints, left, right);


             QuickSort(ints, left, newIndex - 1);
             QuickSort(ints, newIndex + 1, right);
        }
    }

上記は正常に機能しますが、以下のコードは機能しません。現在、正しくソートされていません。太字のコードは別の場所に配置する必要があるようです...または何か？私はスレッドプログラミングを理解するのに非常に苦労しているので、可能であればプログラム全体を再構築することなく、誰かがこれを修正する方法についていくつかの指針を教えてくれることを望んでいました。以下は、私がスレッドバージョンでどこまで到達したかです。

public class Sorter
{
    private int[] mInts;

    Thread myThread = null;
    int numThreads = 0;
    int maxThreads = 10;

    public void QuickSort()
    {
        QuickSort(mInts, 0, mInts.Length - 1);
    }

    public Sorter(int[] ints)
    {
        mInts = ints;
    }

    private int Partition(int[] ints, int left, int right)
    {
        int pivotIndex = (right + left) / 2;
        int pivotValue = ints[pivotIndex];

        Swap(ints, right, pivotIndex);

        int storeIndex = left;

        for (int i = left; i <= right - 1; i++)
        {
            if (ints[i] < pivotValue)
            {
                Swap(ints, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(ints, storeIndex, right);

        return storeIndex;
    }

    private void Swap(int[] ints, int x, int y)
    {
        int temp = ints[x];
        ints[x] = ints[y];
        ints[y] = temp;
    }

    private void QuickSort(int[] ints, int left, int right)
    {
        if (left < right)
        {
            int newIndex = Partition(ints, left, right);

            if (numThreads < maxThreads)
            {
                numThreads++;
                myThread = new Thread(new ParameterizedThreadStart(startSort));
                myThread.Start(new SortParameters(this, ints, left, newIndex - 1));
                **QuickSort(ints, newIndex + 1, right);**
            }
        }
    }

    static void startSort(Object obj)
    {
        SortParameters sortParams = (SortParameters)obj;
        sortParams.instance.QuickSort(sortParams.ints, sortParams.left, sortParams.right);
    }

    public class SortParameters
    {
        public Sorter instance;
        public int[] ints;
        public int left;
        public int right;

        public SortParameters(Sorter instance, int[] ints, int left, int right)
        {
            this.instance = instance;
            this.ints = ints;
            this.left = left;
            this.right = right;
        }
    }
}

助けてくれてありがとう！

4

1 に答える 1

0

次のことを自問してください。

  1. 一連のn要素に対していくつのスレッドが実行されますか？
  2. その数はあなたのコードによってどういうわけか制限されていますか？
  3. その制限に達するとどうなりますか？

以下に私の解決策を示しますが、最初に自分で考えてみてください。

これが私の答えです：

  1. 理論的には、コードはログ2（n）のクイックソートを計算します。これは、パーティション分割後に各ソートを2つのサブコールに分割するためです。スレッド化されたバージョンでは、サブコールごとに1つの補足スレッドを開始するため、合計でできるだけ多くのスレッドを起動できます。

  2. 指定するコードは、実際に起動されるスレッドの数を値で制限しmaxThreadsます。したがって、実際には、log 2（n）>maxThreadsの場合、つまり。n> 2の場合maxThreads、コードは可能な同時スレッドの最大数に達します。

  3. スレッド化されたコードでは、強調表示された部分の周りで、その最大値でのテストにより、再帰呼び出しの実行が条件付けられます。したがってn、ポイント＃2で説明した制限を超えている場合、コードは正しく機能しなくなります。

修正は非常に簡単elseです。現在のスレッドで並べ替えを完了するための句を追加します。

        if (numThreads < maxThreads)
        {
            numThreads++;
            myThread = new Thread(new ParameterizedThreadStart(startSort));
            myThread.Start(new SortParameters(this, ints, left, newIndex - 1));
        }
        else {
            QuickSort(ints,left,newIndex - 1);
        }
        QuickSort(ints, newIndex + 1, right);

ご覧のとおり、とにかく現在のスレッドによって実行される部分もテストから外しました。

于 2013-02-24T11:47:56.197 に答える