25

配列または配列で動作できる並列化（マルチスレッド）ソートアルゴリズムの単純な実装を探していますList<T>。並列拡張機能を使用することもできますが、その部分は厳密には必要ありません。

編集：Frank Kruegerが良い答えを提供しますが、その例をLINQを使用しない例に変換したいと思います。また、Parallel.Do()に取って代わられたようParallel.Invoke()です。

ありがとう。

4

5 に答える 5

46

彼の記事ParallelExtensionsの「TheDarkside」から.NetFrameworkまで、クイックソートのこの並列拡張バージョンがあります。

（編集：リンクが無効になっているため、興味のある読者はWayback Machineでそのアーカイブを見つけることができます）

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    if (right > left)
    {
        int pivot = Partition(arr, left, right);
        QuicksortSequential(arr, left, pivot - 1);
        QuicksortSequential(arr, pivot + 1, right);
    }
}

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    const int SEQUENTIAL_THRESHOLD = 2048;
    if (right > left)
    {
        if (right - left < SEQUENTIAL_THRESHOLD)
        {

            QuicksortSequential(arr, left, right);
        }
        else
        {
            int pivot = Partition(arr, left, right);
            Parallel.Do(
                () => QuicksortParallelOptimised(arr, left, pivot - 1),
                () => QuicksortParallelOptimised(arr, pivot + 1, right));
        }
    }
}

アイテムの数が2048未満になると、彼は順次ソートに戻ることに注意してください。

于 2009-12-13T19:36:48.807 に答える
8

アップデート私は今、デュアルコアマシンで1.7倍以上のスピードアップを達成しています。

.NET 2.0で動作し（これを確認してください）、。以外のものを使用しない並列ソーターを作成してみようと思いましたThreadPool。

2,000,000個の要素配列を並べ替えた結果は次のとおりです。

時間並列時間シーケンシャル
------------- ---------------
2854ミリ秒5052ミリ秒
2846ミリ秒4947ミリ秒
2794ミリ秒4940ミリ秒
.....。
2815ミリ秒4894ミリ秒
2981ミリ秒4991ミリ秒
2832ミリ秒5053ミリ秒

平均：2818ミリ秒平均：4969ミリ秒
標準：66ミリ秒標準：65ミリ秒
Spd：1.76x

この環境では、1.76倍のスピードアップ（期待していた最適な2倍にかなり近い）が得られました。

  1. 2,000,000個のランダムModelオブジェクト
  2. DateTime2つのプロパティを比較する比較デリゲートによるオブジェクトの並べ替え。
  3. MonoJITコンパイラバージョン2.4.2.3
  4. 2.4 GHz Intel Core2Duo上のMaxOSX 10.5.8

今回は、C＃でBenWatsonのQuickSortを使用しました。私は彼のQuickSort内側のループを次のように変更しました：

QuickSortSequential:
    QuickSortSequential (beg, l - 1);
    QuickSortSequential (l + 1, end);

に：

QuickSortParallel:
    ManualResetEvent fin2 = new ManualResetEvent (false);
    ThreadPool.QueueUserWorkItem (delegate {
        QuickSortParallel (l + 1, end);
        fin2.Set ();
    });
    QuickSortParallel (beg, l - 1);
    fin2.WaitOne (1000000);
    fin2.Close ();

（実際、コードでは、役立つように見える少しの負荷分散を行っています。）

この並列バージョンを実行すると、アレイに25,000を超えるアイテムがある場合にのみ効果があることがわかりました（ただし、最低50,000を使用すると、プロセッサの呼吸が増えるようです）。

私は私の小さなデュアルコアマシンで考えられる限り多くの改善を行いました。8ウェイモンスターのアイデアを試してみたいです。また、この作業は、Monoを実行している小さな13インチMacBookで行われました。他の人が通常の.NET2.0インストールでどのように動作するのか興味があります。

その醜い栄光のソースコードはここで入手できます：http：//www.praeclarum.org/so/psort.cs.txt。興味があれば片付けます。

于 2009-12-13T23:31:22.967 に答える
7

ここでの記録は、C＃2および.Net 2 +ParallelExtensionsでコンパイルされるlamda式のないバージョンです。これは、Parallel Extensionsの独自の実装（コード2008のGoogle Summerから）を備えたMonoでも機能するはずです。

/// <summary>
/// Parallel quicksort algorithm.
/// </summary>
public class ParallelSort
{
    #region Public Static Methods

    /// <summary>
    /// Sequential quicksort.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T>
    {
        QuicksortSequential(arr, 0, arr.Length - 1);
    }

    /// <summary>
    /// Parallel quicksort
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T>
    {
        QuicksortParallel(arr, 0, arr.Length - 1);
    }

    #endregion

    #region Private Static Methods

    private static void QuicksortSequential<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        if (right > left)
        {
            int pivot = Partition(arr, left, right);
            QuicksortSequential(arr, left, pivot - 1);
            QuicksortSequential(arr, pivot + 1, right);
        }
    }

    private static void QuicksortParallel<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        const int SEQUENTIAL_THRESHOLD = 2048;
        if (right > left)
        {
            if (right - left < SEQUENTIAL_THRESHOLD)
            {
                QuicksortSequential(arr, left, right);
            }
            else
            {
                int pivot = Partition(arr, left, right);
                Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);},
                                               delegate {QuicksortParallel(arr, pivot + 1, right);}
                });
            }
        }
    }

    private static void Swap<T>(T[] arr, int i, int j)
    {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int Partition<T>(T[] arr, int low, int high) 
        where T : IComparable<T>
    {
        // Simple partitioning implementation
        int pivotPos = (high + low) / 2;
        T pivot = arr[pivotPos];
        Swap(arr, low, pivotPos);

        int left = low;
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i].CompareTo(pivot) < 0)
            {
                left++;
                Swap(arr, i, left);
            }
        }

        Swap(arr, low, left);
        return left;
    }

    #endregion
}
于 2009-12-13T22:33:42.997 に答える
6

プロセッサ間でブロックが分割されている、プロセッサキャッシュのサイズに基づくマージソートが思い浮かびます。

マージステージは、マージをnビットに分割し、各プロセッサが正しいオフセットからブロックへのブロックのマージを開始することで実行できます。

私はこれを書いてみませんでした。

（CPUキャッシュとメインRAMの相対速度は、マージソートが検出されたときのように、RAMとテープの相対速度からそれほど遠くないので、マージソートの使用を再開する必要があります）

于 2010-02-23T15:32:13.303 に答える
1

必要なリストを、使用しているプロセッサの数に応じて同じサイズのサブリストに分割し、2つの部分が完了するたびに、残りが1つだけになり、すべてのスレッドが完了するまで、それらを新しい部分にマージします。非常に単純で、自分で実装できるはずです。各スレッド内のリストの並べ替えは、既存の並べ替えアルゴリズム（ライブラリなど）を使用して実行できます。

于 2009-12-13T19:37:18.757 に答える