在元组列表上使用二分法，但仅使用第一个值进行比较

Question

我读了that question about how to use bisect on a list of tuples, and I used that information to answer 。它有效，但我想要一个更通用的解决方案。

因为 bisect 不允许指定 key 函数，如果我有这个：

import bisect
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)]

我想找到 x > 5 那些 (x,y) 元组的第一个项目（根本不考虑 y，我目前正在这样做：

bisect.bisect_left(test_array,(5,10000))

我得到了正确的结果，因为我知道没有y大于10000，所以bisect将我指向[=的索引24=]。如果我用 1000 代替，那就错了。

对于整数，我可以做到

bisect.bisect_left(test_array,(5+1,))

但是在一般情况下，当可能有浮动时，如何在不知道第二个元素的最大值的情况下做到这一点？

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,))

它没有用，但我已经试过了：

bisect.bisect_left(test_array,(min_value+sys.float_info.epsilon*3,))

它奏效了。但这感觉像是一个糟糕的黑客。有没有干净的解决方案？

Answer 1

为此：

...want to find the first item where x > 5 for those (x,y) tuples (not considering y at all)

类似于：

import bisect
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)]

first_elem = [elem[0] for elem in test_array]
print(bisect.bisect_right(first_elem, 5))

bisect_right 函数将获取第一个索引，并且由于您只关心元组的第一个元素，所以这部分看起来很简单。 ...仍然没有概括到我意识到的特定关键功能。

正如@Jean-FrançoisFabre 指出的那样，我们已经在处理整个数组，因此使用 bisect 可能甚至没有多大帮助。

不确定它是否更快，但我们也可以使用类似 itertools 的东西（是的，这有点难看）：

import itertools
test_array = [(1,2),(3,4),(5,6),(5,7000),(7,8),(9,10)]

print(itertools.ifilter(
    lambda tp: tp[1][0]>5, 
    ((ix, num) for ix, num in enumerate(test_array))).next()[0]
)

Answer 2

这是一个（又快又脏）bisect_left 允许任意键函数的实现：

def bisect(lst, value, key=None):
    if key is None:
        key = lambda x: x
    def bis(lo, hi=len(lst)):
        while lo < hi:
            mid = (lo + hi) // 2
            if key(lst[mid]) < value:
                lo = mid + 1
            else:
                hi = mid
        return lo
    return bis(0)

> from _operator import itemgetter
> test_array = [(1, 2), (3, 4), (4, 3), (5.2, 6), (5.2, 7000), (5.3, 8), (9, 10)]
> print(bisect(test_array, 5, key=itemgetter(0)))
3

这可以保持 O(log_N) 性能，因为它 而不是 assemble 一个新的 list 键。二进制搜索的实现是广泛可用的，但这是直接取自 bisect_left source。还需要注意的是，列表需要针对同一个key函数进行排序

Answer 3

除了这些不错的建议之外，我还想添加我自己的适用于浮点数的答案（正如我刚刚弄明白的那样）

bisect.bisect_left(test_array,(min_value+abs(min_value)*sys.float_info.epsilon),))

会起作用（无论 min_value 是否为正数）。 epsilon 乘以 min_value 与 min_value 相加保证有意义（不是 absorbed/cancelled）。所以它是最接近 min_value 的更大值，bisect 将与之配合使用。

如果您只有整数，仍然会更快更清晰：

bisect.bisect_left(test_array,(min_value+1,))

Answer 4

bisect 支持任意序列。如果您需要使用 bisect 和一个键，而不是将键传递给 bisect，您可以将它构建到序列中：

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 源代码或编写您自己的二进制搜索：

bisect.bisect_right(KeyList(test_array, key=lambda x: x[0]), 5)

在元组列表上使用二分法，但仅使用第一个值进行比较

using bisect on list of tuples but compare using first value only

python

comparison

tuples

bisect