<p>如果有许多值要测试,那么可以使用<a href="http://docs.python.org/library/bisect.html#module-bisect" rel="nofollow">bisect module</a>更快地找到这些值所在的范围。在</p>
<p>如果</p>
<ul>
<li><code>m</code>=要测试的值的数目,以及</li>
<li>^{{cd2>}<cd3}</li>
</ul>
<p>然后按照您的建议在值和范围列表中循环将花费<code>O(m*n)</code>时间。在</p>
<p>如果使用二等分,则必须首先对起始地址<code>O(nlogn)</code>进行排序,并找到每个值在范围列表<code>O(m*logn)</code>中的位置。
所以如果</p>
<pre><code>O(nlogn + m*logn) < O(m*n)
</code></pre>
<p>然后平分获胜。对于大的<code>n</code>,与<code>O(m*n)</code>相比,<code>O(m*logn)</code>很小。
因此,如果</p>
^{pr2}$
<p>或者等效地,当</p>
<pre><code>C log(n) < m
</code></pre>
<p>对于某个常数C</p>
<hr/>
<p>因此,当<code>n</code>较大且<code>C log(n) < m</code>时,您可以尝试类似的方法</p>
<pre><code>import bisect
class RangeClass(object):
def __init__(self,address,size):
self.address=address
self.size=size
def __str__(self):
return '[{0},{1})'.format(self.address,self.address+self.size)
def __lt__(self,other):
return self.address<other.address
rangelist=sorted([RangeClass(i,1) for i in (1,3,4,5,7.5)])
starts=[r.address for r in rangelist]
def find_range(value):
start_idx=bisect.bisect(starts,value)-1
try:
r=rangelist[start_idx]
except IndexError:
return None
start=r.address
end=r.address+r.size
if start<=value<end:
return rangelist[start_idx]
return None
print(','.join(str(r) for r in rangelist))
for value in (0,1,1.5,2,3,4,5,6,7,8,9,10):
r=find_range(value)
if r:
print('{v} in {r}'.format(v=value,r=str(r)))
else:
print('{v} not in any range'.format(v=value))
</code></pre>