最快的方式来搜索一个数字范围的列表 [英] Fastest way to search a number in a list of ranges
问题描述
我有以下的code找到匹配的数量范围内的清单。
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);
}
}
在RangeGroup的名单包括500多万项和查找()方法中使用的很多,所以我在寻找一个更快的方法来使搜索。这是没有问题的,改变的数据的结构或将其以任何方式分割
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.
编辑:
的所有范围是独一无二的,通过以低的加入它们不重叠。
All ranges are unique and added by in order of Low and they don't overlap.
结果:
做了一个测试用<一个href="http://stackoverflow.com/questions/11868837/fastest-way-to-search-a-number-in-a-list-of-ranges/11869161#11869161">ikh's code ,结果比我的code快约7000倍。测试code和结果可以看出这里。
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.
推荐答案
既然你指出, RangeGroup
s的增加,从而 RangeGroup.Low的
,他们不重叠,你不需要做任何进一步的pre-处理。你可以做 RangeGroups
名单上的二进制搜索找到的范围内(警告:没有完全测试,你需要检查一些边界条件):
Since you indicated that RangeGroup
s are added in order of RangeGroup.Low
and that they do not overlap, you don't need to do any further pre-processing. You can do binary search on the RangeGroups
list to find the range (warning: not fully tested, you'd need to check some edge conditions):
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是RangeGroups的数目
The worst-case run time should be around O(log(N)), where N is the number of RangeGroups.
这篇关于最快的方式来搜索一个数字范围的列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!