在一个范围列表中查找数字的最快方法

Question

在一个范围列表中查找数字的最快方法

c#performancealgorithmc#-4.0optimization

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()方法将被频繁使用，因此我正在寻找更快的搜索方法。更改数据结构或以任何方式拆分数据都不是问题。

编辑：

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

结果：

使用ikh's code进行了测试，结果比我的代码快大约7000倍。测试代码和结果可以在here中查看。

- M. Mennan Kara

也许使用 SortedList 类可以稍微提高性能。 - user854301

1

你是想返回包含该数字的任何范围，还是该范围必须符合任何条件（例如最早添加）？ - ikh

只返回符合条件的范围，所有范围都是唯一的，并按照低端点的顺序添加，它们不会重叠。 - M. Mennan Kara

1

顺便说一句，如果你在搜索时用“区间”这个词可能会比“范围”得到更好的结果。也许可以找找区间树之类的东西。 - user541686

在问题的结尾可以看到linq和二分查找之间的性能比较测试，感谢大家的帮助 :) - M. Mennan Kara

显示剩余3条评论

5个回答

4

区间树正是为了您所需要的而创建的。

- alinsoar

3

与二分搜索相比，区间树的优点在于你拥有重叠的区间。在这种情况下，没有重叠。二分搜索更简单且足够。 - Rafael Baptista

2

如果您只需要填充列表一次，您可以做一个魔术技巧：

对列表进行排序
使用二分查找

排序需要O(Nlog(N))的时间，仅需执行一次。二分查找需要O(log(N))的时间，对于100,000个项目最多需要17次比较。

- oleksii

在这种情况下，简单的二分查找无法工作。您需要考虑范围的低部和高部。 - Sam I am says Reinstate Monica

这个列表已经排序好了，据我所知，为了能够使用二分查找，我需要知道我要查找的内容。如果您能给出一个二分查找的例子，那会很有帮助，谢谢。 - M. Mennan Kara

@MennanKara，让我试着给你提供一个示例。你能发布一些你如何填充这个列表的实例吗？ - oleksii

你的算法复杂度大于O(logn)。需要确保值从 max 减小。 - barak1412

@oleksii 添加了一些示例数据，通常我会在 Application_Start() 中从数据库中填充它。 - M. Mennan Kara

@MennanKara 似乎IKH已经搞定了。 - oleksii

1

可以使用排序列表并执行二分搜索。这样可以将比较次数降至O(logN)。

- Jeff

好的，让我更清楚地解释一下。他正在按顺序添加这些间隔，它们不重叠。因此，您有一个已排序的列表。 - Jeff

继续：在排序列表中搜索需要O(logN)的时间。 - Jeff

你必须检查所有的区间，否则无法完成。只有在区间不重叠的情况下，才能以logn的时间复杂度完成。 - alinsoar

1

@alinsoar 在问题中提到区间不重叠。 - Jeff

0

将范围分别按范围内最小值和最大值排序两次，分别存储在两个不同的数组中。然后进行两次二分搜索，保存符合任一约束条件的范围。最后，对这两组可能性进行集合交集操作。

- user1277476

除非必要，否则无需走得那么远，因为范围不会重叠。 - Rafael Baptista

你需要两个二分查找吗？我想他提到了没有任何区间重叠。 - Jeff

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ikh · Accepted Answer

既然您指出RangeGroup是按RangeGroup.Low的顺序添加且不重叠，您不需要进行任何进一步的预处理。您可以在RangeGroups列表上进行二分查找以找到范围（警告：未经完全测试，您需要检查一些边缘条件）：

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

    while (true) {
        if (stepSize == 0) {
            // Worst case found it
            if(RangeGroups[position].High >= number && RangeGroups[position].Low <= number)
            {
                return ranges[position];
            }

            // 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是RangeGroups的数量。