在元组列表上使用 bisect 但仅使用第一个值进行比较

2022-01-20 00:00:00 python tuples comparison bisect

问题描述

我阅读了关于如何使用 的那个问题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.

对于整数，我可以这样做

For integers, I could do 

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)

相关文章