5

現在、2 つの配列を比較し、それらが等しいかどうかを判断するための for ループがあります。

public override bool Equals(object obj)
{
    RushHourPathLengthNode otherNode = (RushHourPathLengthNode)obj;

    // Compare their carCoords and return false as soon as we find a difference
    for (int i = 0, l = carCoords.Length; i < l; ++i)
        if (carCoords[i].x != otherNode.carCoords[i].x || carCoords[i].y != otherNode.carCoords[i].y)
            return false;
    return true;
}

これはうまくいきますが、私のプログラムの中で最も遅い部分の 1 つです。このように、テストケースの計算には約 7 秒かかります。

50K のタスクを実行している可能性がありますが、CPU 使用率は i7 860 CPU (4 コア、8 スレッド) で約 50% でした。

私の考えは、並列 for ループを使用して CPU 使用率を最大化し、これを高速化することでした。これが私が思いついたものです。

public override bool Equals(object obj)
    {
        RushHourPathLengthNode otherNode = (RushHourPathLengthNode)obj;
        bool result = true;

        Parallel.For(0, carCoords.Length, (i, loopState) =>{
            if (!result)
                loopState.Stop();

            if (carCoords[i].x != otherNode.carCoords[i].x || carCoords[i].y != otherNode.carCoords[i].y)
                result = false;
        });

        return result;
    }

私には、これは並行して実行しようとし、loopState.Stop のために違いが見つかるとすぐに作業を停止するように見えます。このように CPU 使用率は 90% 以上ですが、テストケースの計算には約 35 秒かかり、その理由がわかりません。

私の実装に何か問題がありますか、それとも私のアプローチ全体が間違っていますか?

編集: carCoords.Length は 2 と +-100 の間の値になります。これを並行して行うことを正当化するには、その値が低すぎるようです。

4

2 に答える 2

3

まず、for ループが数 100 回の繰り返ししか実行しない場合は、わざわざ並列化しないでください。各反復で行っている作業を価値のあるものにするためには、何千回もの反復が必要です。

多くの反復があると仮定すると、大幅な速度低下の主な理由は、各反復でほんの少しの作業しか行っていないことです。タスクのスケジューリング、メソッド本体の呼び出しなどには多くのオーバーヘッドがあり、それが全体の実行時間の大半を占めています。

Partinioner.Create(System.Collections.Concurrent名前空間から)を使用して範囲をセグメントに分割することで、これを回避できます。これにより、各範囲の開始インデックスと終了インデックスを含む一連のタプルが得られます。その後、各タスクを範囲にわたって反復させることができます。これははるかに効率的です。

第 2 に、ローカル変数はクロージャー オブジェクトに取り込まれるため、メソッド本体内で変数のローカル コピーを使用する方が高速な場合があります。

これが得られるものです。

    Parallel.ForEach(Partitioner.Create(0, carCoords.Length), (r, loopState) => {
        var c1 = carCoords;
        var c2 = otherNode.carCoords;
        int end = r.Item2;
        for (int i = r.Item1; i < end; ++i) {
            if (loopState.IsStopped)
                return;
            if (c1[i].x != c2[i].x || c1[i].y != c2[i].y) {
                loopState.Stop();
                return;
            }
        }
    });

IsStoppedすべての反復をチェックする価値があるかどうかはわかりません。Partitioner.Createパーティションを増やして (オーバーロードで遊んで)、 for ループの前にチェックを入れる方が効率的かもしれません。

于 2013-11-09T18:38:11.043 に答える
1

クラスにインターフェイスを実装IEqutable<RushHourPathLengthNode>して、キャストを回避します。それはあなたの秒を獲得します。

carCoords.Length が小さい場合、スレッドの管理と切り替えにコストがかかるため、並列ループに時間がかかります。

于 2013-11-09T18:05:31.307 に答える