有没有办法避免对此进行线性搜索？

我有一个很大的对象的起始编号和结束编号。例如：有没有办法避免对此进行线性搜索？

(999, 2333, data) 
(0, 128, data) 
(235, 865, data) 
...

假设间隔不相互重叠。我正在编写一个函数，它需要一个数字并找到（低，高）包含它的对象。说给333，我想列表中的第三个对象。

有没有什么办法可以尽可能有效地做到这一点，缺少线性搜索？我在考虑二分查找，但在应对范围检查时遇到了一些困难。

来源

2012-01-18 Oliver

它是“值得”排序它，以便使用二进制搜索？ [如果你打算只搜索几次，它不会“值得”分类，如果你打算搜索很多次，它是] – amit

对象将不得不被排序。 – rplnt

这些数字的绝对上限和下限是什么？您可以将范围扩展到适当的“位映射索引”，您只需枚举该范围中的所有值即可。 –

首先，它不是完全清楚二进制搜索在这里保证。当间隔数很小时，线性搜索可能会更快。

如果您关注性能，谨慎的做法是对代码进行剖析，并可能在您的典型输入上对两种方法进行基准测试。

免责声明之外，二进制搜索可以通过排序间隔一次，然后重复地使用所述bisect模块做搜索来实现：

import bisect 

intervals = [(999, 2333, 'int1'), (0, 128, 'int2'), (235, 865, 'int3')] 
intervals.sort() 

def find_int(intervals, val): 
    pos = bisect.bisect_left([interval[1] for interval in intervals], val) 
    if pos < len(intervals) and val >= intervals[pos][0]: 
     return intervals[pos] 
    else: 
     return None 

print(find_int(intervals, 0)) 
print(find_int(intervals, 1)) 
print(find_int(intervals, 200)) 
print(find_int(intervals, 998)) 
print(find_int(intervals, 999)) 
print(find_int(intervals, 1000)) 
print(find_int(intervals, 2333)) 
print(find_int(intervals, 2334))

在上文中，我假定间隔是不重叠的，并且该间隔包括其开始点和结束点。

最后，为了提高性能，可以考虑将[interval[1] for interval in intervals]从功能中分解出来，并在开始时只做一次。

来源

2012-01-18 15:43:11 NPE

想想看是否值得整理数据。
如果您只想搜索几次，那么它不会 - 并且您无法避免线性搜索。您搜索的总体复杂度将为O(n*k)，其中n是元素的数量，k是搜索的数量。

如果您想搜索很多次，那么您应该先排序，然后使用二进制搜索进行搜索。排序为O(nlogn)，搜索次数为O(klogn)，所以总计为O((n+k)logn)。

因此，排序和然后搜索应该做的只有k>=logn

附：您可以使用另一种方法进行排序和搜索，在其他的答案提出的，在各方面，结论依然是：做到这一点只有k>=logn

来源

2012-01-18 15:42:23 amit

是的，虽然对象池是固定的，但我期望多次搜索，因此排序似乎是有保证的。谢谢。 – Oliver

可以使用对开模块：http://docs.python.org/library/bisect.html

您需要将您的数据进行排序，然后使用对开：

import bisect 
data=None 
tuples=[(0, 128, None), (235, 865, None), (999, 2333, None)] 
tuples.sort() 
print tuples 
print bisect.bisect(tuples, (-1,)) # 0 
print bisect.bisect(tuples, (1,)) # 1 
print bisect.bisect(tuples, (333,)) # 2 
print bisect.bisect(tuples, (3333,)) # 3

来源

2012-01-18 15:45:16 guettli

感谢分歧的建议，这似乎是在这种情况下的共识。 – Oliver

如果搜索速度是最重要的，那么你可以创建一个look- （正如S.Lott所评论的）。这将需要ø（- [R）存储器（其中，- [R是该范围的大小），Ô（- [R）预处理时间，和ö（1）搜索时间。创建一个范围大小的数组，并用指向数据的指针或null填充每个元素。

lookup = {} 
for low, high, data in source_ranges: 
    for i in range(low,high): # or maybe high+1 if the ranges are inclusive 
     lookup[i] = data

现在查找是微不足道的。

来源

2012-01-18 16:20:07 cyborg

有没有办法避免对此进行线性搜索？

回答

相关问题