在元组列表上使用二等分，但仅使用第一个值进行比较 [英] 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屋！