在元组列表上使用二等分,但仅使用第一个值进行比较 [英] using bisect on list of tuples but compare using first value only
问题描述
我阅读了该问题有关如何使用bisect
在元组列表中,我使用该信息来回答
I read that question about how to use bisect
on a list of tuples, and I used that information to answer that question. It works, but I'd like a more generic solution.
由于bisect
不允许指定key
函数,如果我有此功能:
Since bisect
doesn't allow to specify a key
function, if I have this:
import bisect
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)]
并且我想找到第一个项,其中x > 5
用于那些(x,y)
元组(根本不考虑y
,我目前正在这样做:
and I want to find the first item where x > 5
for those (x,y)
tuples (not considering y
at all, I'm currently doing this:
bisect.bisect_left(test_array,(5,10000))
,我得到了正确的结果,因为我知道,没有y
大于10000,所以bisect
将我指向(7,8)
的索引.如果我改用1000
,那肯定是错的.
and I get the correct result because I know that no y
is greater than 10000, so bisect
points me to the index of (7,8)
. Had I put 1000
instead, it would have been wrong.
对于整数,我可以做
bisect.bisect_left(test_array,(5+1,))
但是在通常情况下可能有浮点数的情况下,如何在不知道第二个元素的最大值的情况下实现该目标?
but in the general case when there may be floats, how to to that without knowing the max values of the 2nd element?
test_array = [(1,2),(3,4),(5.2,6),(5.2,7000),(5.3,8),(9,10)]
我已经尝试过了:
bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon,))
它没有用,但是我已经尝试过了:
and it didn't work, but I have tried this:
bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon*3,))
,它奏效了.但这感觉很糟糕.有干净的解决方案吗?
and it worked. But it feels like a bad hack. Any clean solutions?
推荐答案
bisect
支持任意序列.如果需要将bisect
与一个键一起使用,而不是将键传递给bisect
,则可以将其构建到序列中:
bisect
supports arbitrary sequences. If you need to use bisect
with a key, instead of passing the key to bisect
, you can build it into the sequence:
class KeyList(object):
# bisect doesn't accept a key function, so we build the key into our sequence.
def __init__(self, l, key):
self.l = l
self.key = key
def __len__(self):
return len(self.l)
def __getitem__(self, index):
return self.key(self.l[index])
然后,您可以将bisect
与KeyList
一起使用,性能为O(log n),而无需复制bisect
源或编写自己的二进制搜索:
Then you can use bisect
with a KeyList
, with O(log n) performance and no need to copy the bisect
source or write your own binary search:
bisect.bisect_right(KeyList(test_array, key=lambda x: x[0]), 5)
这篇关于在元组列表上使用二等分,但仅使用第一个值进行比较的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!