9

我有以下代码来查找范围列表中数字的匹配项。

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);
    }
}

RangeGroup 的列表包含大约 5000000 个项目，并且 Find() 方法将被大量使用，因此我正在寻找一种更快的方法来进行搜索。改变数据结构或以任何方式拆分数据都没有问题。

编辑：

所有范围都是唯一的，并且按低的顺序添加，并且它们不重叠。

结果：

使用ikh 的代码进行了测试，结果比我的代码快了大约 7000 倍。测试代码和结果可以在这里看到。

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)) 时间并且只进行一次。二进制搜索需要 O(log(N))，最多需要对 100.000 个项目进行 17 次比较。

于 2012-08-08T16:34:10.650 回答
1

可以使用排序列表并进行二进制搜索。这样您就可以将比较次数减少到 O(logN)

于 2012-08-08T17:00:50.050 回答
0

在两个不同的数组中对范围进行两次排序。一次按范围内的最小值，一次按范围内的最大值。然后进行两次二分搜索，保存与任一约束匹配的范围。最后，对两组可能性做一组交集。

于 2012-08-08T16:58:36.380 回答