9

簡単なメモですが、これは宿題ではありません。アルゴリズムをブラッシュアップしようとしています。私はC#でMergeSortをいじっており、ジェネリックスに基づいてソートできる再帰メソッドを作成しました。

class SortAlgorithms
{

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T>
    {
        T[] left, right;
        int middle = unsortedArray.Length / 2;

        left = new T[middle];
        right = new T[unsortedArray.Length - middle];

        if (unsortedArray.Length <= 1)
            return unsortedArray;

        for (int i = 0; i < middle; i++)
        {
            left[i] = unsortedArray[i];
        }

        for (int i = middle; i < unsortedArray.Length; i++)
        {
            right[i - middle] = unsortedArray[i];
        }

        left = MergeSort(left);

        right = MergeSort(right);


        return Merge<T>(left, right);
    }

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T>
    {
        T[] result = new T[left.Length + right.Length];

        int currentElement = 0;

        while (left.Length > 0 || right.Length > 0)
        {
            if (left.Length > 0 && right.Length > 0)
            {
                if (left[0].CompareTo(right[0]) < 0)
                {
                    result[currentElement] = left[0];
                    left = left.Skip(1).ToArray();
                    currentElement++;
                }
                else
                {
                    result[currentElement] = right[0];
                    right = right.Skip(1).ToArray();
                    currentElement++;
                }
            }
            else if (left.Length > 0)
            {
                result[currentElement] = left[0];
                left = left.Skip(1).ToArray();
                currentElement++;
            }
            else if (right.Length > 0)
            {
                result[currentElement] = right[0];
                right = right.Skip(1).ToArray();
                currentElement++;
            }
        }

        return result;
    }
}

これは機能しますが、非常に遅いです。System.Diagnostic.StopWatchを使用してArray.Sort(QuickSortアルゴリズムを使用)とのパフォーマンスをチェックし、MergeSortと比較しましたが、その違いは非常に大きいので、これを間違って実装しているのではないかと思います。コメントはありますか?

4

4 に答える 4

12

私はC#プログラマーではありませんが、問題はこのようなステートメントの使用である可能性がありますか?

left = left.Skip(1).ToArray();

これは、基になる配列のディープコピーを強制する方法で実装される場合があります。その場合、これにより、マージのパフォーマンスがO(n)からO(n 2)に低下し、結果のマージソートのパフォーマンスがO(n log n)からO(n 2)にすぐに低下します

(これは、再発がから変化するためです

T(1)= O(1)

T(n)≤2T(n / 2)+ O(n)

これは解T(n)= O(n log n)であり、

T(1)= O(1)

T(n)≤2T(n / 2)+ O(n 2

これは解T(n)= O(n 2))を持ちます。

于 2012-08-27T20:02:52.017 に答える
2

常に中間配列の形でメモリを割り当てています。元のアレイを再利用する方向で考えてください。

于 2012-08-27T20:02:20.463 に答える
1

他の2つの答えが言っているように、あなたはあちこちに新しいアレイを作成し、それに多くの時間とメモリを費やしています(おそらく、ほとんどの時間とほとんどすべてのメモリが使用されます)。

繰り返しになりますが、他のすべてが等しい再帰であると、反復よりも遅くなり、より多くのスタックスペースを使用する傾向があることを付け加えます(反復が行われない場合でも、十分に大きな問題でオーバーフローが発生する可能性があります)。

でも。マージソートは、マルチスレッドアプローチに適しています。これは、パーティション化の最初のバッチのさまざまな部分をさまざまなスレッドで処理できるためです。

したがって、これで遊んでいた場合、次の2つの実験は次のようになります。

  1. パーティショニングの最初のビットでは、MergeSort再帰的に呼び出すのではなく、コアごとにスレッドを実行するまで新しいスレッドを起動します(ハイパースレッディングの場合は、物理コアごとに実行するか、仮想コアごとに実行する必要がありますか?それ自体が私が実験したいものです)。
  2. それが終わったら、再帰呼び出しなしで同じことを行うために再帰メソッドを書き直してみます。

問題が処理された後、ToArray()最初に作業を最適な数のコアに分割し、次に各コアに繰り返し作業を行わせるマルチスレッドアプローチを見ると、非常に興味深いものになる可能性があります。

于 2012-08-27T20:13:44.073 に答える
0

まず、同様の質問に対する合理化されたソリューションへのリンクを次に示します。Javaマージソート、「マージ」ステップはキューまたは配列で実行する必要がありますか?

新しいサブアレイを繰り返し割り当てているため、ソリューションは遅くなります。メモリの割り当ては、他のほとんどの操作よりもはるかにコストがかかります(割り当てコスト、収集コスト、およびキャッシュの局所性の喪失があります)。通常、これは問題ではありませんが、厳密な並べ替えルーチンをコーディングしようとしている場合は、問題になります。マージソートの場合、必要な宛先配列と一時配列は1つだけです。

スレッドをフォークして並列化することは、それよりも桁違いにコストがかかります。したがって、ソートするデータが大量にある場合を除いて、フォークしないでください。

上記の回答で述べたように、マージソートを高速化する1つの方法は、入力配列の既存の順序を利用することです。

于 2012-08-28T00:05:30.223 に答える