gpt4 book ai didi

c# - 在范围列表中搜索数字的最快方法

转载 作者:太空狗 更新时间:2023-10-29 18:18:51 25 4
gpt4 key购买 nike

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

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's code 进行了测试结果比我的代码快大约 7000 倍。测试代码和结果可见here .

最佳答案

由于您指出 RangeGroup 是按 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 的数量。

关于c# - 在范围列表中搜索数字的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11868837/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com