9

I have the following code to find a match for a number in a list of ranges.

public class RangeGroup
{
    public uint RangeGroupId { get; set; }
    public uint Low { get; set; }
    public uint High { get; set; }
    // More properties related with the range here
}

public class RangeGroupFinder
{
    private static readonly List<RangeGroup> RangeGroups=new List<RangeGroup>();

    static RangeGroupFinder()
    {
        // Populating the list items here
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023238144, High = 1023246335 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023246336, High = 1023279103 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023279104, High = 1023311871 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023311872, High = 1023328255 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023328256, High = 1023344639 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023344640, High = 1023410175 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023410176, High = 1023672319 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023672320, High = 1023688703 });
        RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023692800, High = 1023696895 });
       // There are many more and the groups are not sequential as it can seen on last 2 groups
    }

    public static RangeGroup Find(uint number)
    {
        return RangeGroups.FirstOrDefault(rg => number >= rg.Low && number <= rg.High);
    }
}

The list of the RangeGroup consists about 5000000 items and the Find() method will be used a lot, so I'm looking for a faster way to make the search. It's no problem to change the structure of the data or split it in any way.

Edit:

All ranges are unique and added by in order of Low and they don't overlap.

Result:

Did a test using ikh's code and the result is approximately 7000 times faster than my code. The test code and results can be seen here.

4

5 に答える 5

7

RangeGroupsが順番に追加され、RangeGroup.Low重複しないことを示したので、それ以上の前処理を行う必要はありません。リストでバイナリ検索を実行しRangeGroupsて範囲を見つけることができます（警告：完全にはテストされていません。いくつかのエッジ条件を確認する必要があります）：

public static RangeGroup Find(uint number) {
    int position = RangeGroups.Count / 2;
    int stepSize = position / 2;

    while (true) {
        if (stepSize == 0) {
            // Couldn't find it.
            return null;
        }

        if (RangeGroups[position].High < number) {
            // Search down.
            position -= stepSize;

        } else if (RangeGroups[position].Low > number) {
            // Search up.
            position += stepSize;

        } else {
            // Found it!
            return RangeGroups[position];
        }

        stepSize /= 2;
    }
}

最悪の場合の実行時間は、O（log（N））前後である必要があります。ここで、NはRangeGroupの数です。

于 2012-08-08T16:39:32.167 に答える
4

区間木。あなたが求めているもののために正確に作成されました。

于 2012-08-08T17:01:21.643 に答える
2

リストに一度だけ入力すると、魔法のトリックを実行できます。

ソートにはO（Nlog（N））時間がかかり、1回だけ実行されます。二分探索はO（log（N））を取ります。これは、100.000アイテムに対して最大17の比較を取ります。

于 2012-08-08T16:34:10.650 に答える
1

ソートされたリストを使用して、バイナリ検索を実行する場合があります。そうすれば、O（logN）との比較の数を減らすことができます。

于 2012-08-08T17:00:50.050 に答える
0

2つの異なる配列で、範囲を2回並べ替えます。範囲内の最小値で1回、範囲内で最大値で1回。次に、2つの二分探索を実行し、いずれかの制約に一致する範囲を保存します。最後に、2つの可能性のセットの共通部分を実行します。

于 2012-08-08T16:58:36.380 に答える