6

我阅读了关于如何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))

我得到了正确的结果，因为我知道noy大于 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,))

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

4

4 回答 4

7

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

然后您可以使用bisecta KeyList，具有 O(log n) 性能，无需复制bisect源代码或编写自己的二进制搜索：

bisect.bisect_right(KeyList(test_array, key=lambda x: x[0]), 5)
于 2017-10-09T23:20:30.697 回答
4

这是一个（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 源代码中获取的。还需要注意的是，列表需要针对相同的按键功能进行排序。

于 2017-02-09T21:49:22.910 回答
2

为了这：

...想要为那些 (x,y) 元组找到 x > 5 的第一项（根本不考虑 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))

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]
)
于 2017-02-09T21:05:33.460 回答
2

作为好的建议的补充，我想添加我自己的答案，它适用于浮点数（正如我刚刚发现的那样）

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

会起作用（无论是否min_value积极）。epsilon乘以min_value保证在添加时是有意义的min_value（它不会被吸收/取消）。因此，它是最接近的更大价值，min_value并将bisect与之合作。

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

bisect.bisect_left(test_array,(min_value+1,))
于 2017-02-10T13:21:27.203 回答