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

我读到关于如何在元组列表中使用bisect ，我使用该信息来回答。 它有效，但我想要一个更通用的解决方案。

由于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我指向(7,8)的索引。 如果我改为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,))

它起作用了。 但这感觉就像一个糟糕的黑客。 有清洁的解决方案

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

然后你可以使用带有KeyList bisect ，具有O（log n）性能，无需复制bisect源或编写自己的二进制搜索：

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

这是一个（quick'n'dirty）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)性能提升，因为它不组建一个新的list键。 二进制搜索的实现广泛可用，但这是直接从bisect_left 。 还应注意，列表需要根据相同的键功能进行排序。

为了这：

...想要找到第一个项目，其中x> 5表示那些（x，y）元组（根本不考虑y）

就像是：

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

函数将过去的第一个索引，因为你只关心元组的第一个元素，这部分似乎是直截了当的。 ...仍然没有概括到我意识到的特定关键功能。

正如@ 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]
)

作为一个很好的建议的补充，我想添加我自己的回答，它适用于浮动（因为我只是想出来）

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

会工作（ min_value是否为正）。 当添加到min_value时， epsilon乘以min_value保证有意义（它不被吸收/取消）。 因此它是min_value最接近的值，而bisect将使用它。

如果你只有整数仍然更快更清晰：

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

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

问题描述

1楼

2楼

3楼

4楼