0

私のプロジェクトでは、ユーザーが決定した長さのオブジェクト (object[]) の配列を使用しています。また、アプリケーションの実行中に、少なくとも 1 秒間に数百回ループします。この配列には、占有された要素ごとに設定されたビットを持つ配列を使用して、配列への追加が最初の空きスポットを埋めることを保証するクラスも関連付けられています。割り当てられた配列エントリは、それらを移動するために要素の追跡に影響を与えるため、そのままの場所にとどまるため、ギャップが発生する可能性があります。削除または追加できる要素の数は不明です。追加と削除は、要素がループしてアクセスされるよりもはるかに少ない頻度で発生します。

私が知る必要があるのは、この配列をループするときに、どちらがより良い平均パフォーマンスを提供するかということです...

  1. 各エントリの null を確認する

また

  1. 次のコードを呼び出して、停止する -1 をチェックするループで次のインデックスを取得します。Tracker には、要素のビットごとの位置が含まれています。この関数は、塗りつぶされた要素ごとに 1 回だけ実行する必要があります。&= 行と次の行の減算により、最下位ビット セットの整数値が得られます。DeBruijn シーケンス ビットは、対数底 2 を実行してビット位置を取得します。

    private List<Int32> Tracker = new List<Int32>();
private int EnumTemp;
private int EnumTemp2;
private int EnumResult;
private int EnumIndex = -1;
//from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
protected internal static readonly Int32[] MultiplyDeBruijnBitPosition2 =
{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
public int NextIndex()
        {
            if (EnumIndex == -1)
            {
                EnumTemp = Tracker[0];
                EnumIndex = 0;
            }
            while (EnumTemp == 0)
            {
                if (EnumIndex == Tracker.Count -1)
                {
                    EnumIndex = -1;
                    return -1;
                }
                EnumIndex++;
                EnumTemp = Tracker[EnumIndex];
            }
            EnumTemp2 &= EnumTemp - 1;
            EnumResult = Engine.MultiplyDeBruijnBitPosition2[(UInt32)((EnumTemp-EnumTemp2) * 0x077CB531U) >> 27];
            EnumResult += (EnumIndex * 32);
            EnumTemp = EnumTemp2;
            return EnumResult;
        }
    }

    どちらの場合も、配列要素がアクセスされ、一時変数に格納されると仮定します。

4

1 に答える 1

0

x null-rows の null をチェックする速度が、トラッカーでのクイックステップとして遅くなるポイントがあります。ギャップがどれくらい大きくなるかをある程度把握する必要があります。しかし、私の直感では、これが役立つ前に、かなり大きなギャップがあるはずです (たとえば、空の行が埋められた行の 5 倍になる)。なぜそう思うかというと、

  • 配列アクセスは、シーケンシャルかつ完全にプリフェッチされます。したがって、いっぱいになったエントリの後の最初の y エントリは、すでにキャッシュにあります。それらをスキップしても、メモリアクセスは妨げられません

  • Null チェックは非常に高速です。それと比較すると、トラッカーは「複雑」です

  • コードは非常に複雑になり、わずかな利益しか得られません。

  • doublelylinkedlist はギャップがまったくなく、効率的にループできるため、あなたの場合はより高速になる可能性があると思います。リンクリスト参照を使用してオブジェクトを削除できるため、配列内のスポットは必要ありません。

于 2012-09-13T08:52:03.480 に答える