在元组列表中使用bisect？

Question

我正在尝试弄清楚如何在元组列表中使用二分法，例如：

[(3, 1), (2, 2), (5, 6)]

如何根据每个元组中的[1]将此列表二分？

list_dict [(69, 8), (70, 8), ((65, 67), 6)]
tup1,tup2 (69, 8) (70, 8)
list_dict [((65, 67), 6)]
fst, snd ((65, 67),) (6,)

我正在插入以执行二分查找

idx = bisect.bisect(fst, tup1[1]+tup2[1])

这给我带来了 无法比较的类型：int() < tuple()

- user3157919

Answer 1

在某些情况下，仅需简单的

bisect(list_of_tuples, (3, None))

这将足够了。

因为None小于任何整数，所以这将为您提供第一个以至少3开始的元组的索引，或如果它们都小于3，则为list_of_tuples的长度。请注意，list_of_tuples已排序。

- Evgeni Sergeev

---

在Python 3中不起作用。如果您传递确切的数字3，您将得到“TypeError: unorderable types: int() < NoneType()”。但是bisect(list_of_tuples, (3, ))就没问题了。 - Jean-François Fabre

Answer 2

您可以将这些值分开为不同的列表。

from bisect import bisect

data = [(3, 1), (2, 2), (5, 6)]
fst, snd = zip(*data)
idx = bisect(fst, 2)

请注意，bisect 的使用需要您的数据已经排序好。

- Jon Clements

---

这个特定的方法对我不起作用，因为我每次都在更新元组，我会在编辑中解释。 - user3157919

@user3157919，你需要确保你正在二分的内容和你正在处理的内容是分开的（并且二分的内容是可比较的类型），如果需要，稍后再将它们组合在一起... - Jon Clements

使用bisect的主要优势是线性时间搜索。以线性时间方式复制列表意味着您可能会进行线性搜索。 - Brent

如果您使用的是 3.10+ 版本，请查看此答案 https://dev59.com/AmEi5IYBdhLWcg3w2POB#72285263 - Yar

Answer 3

自从版本3.10以后，你可以通过bisect方法传递一个键来指定你要搜索的索引 - 在这里查看更多信息：

key参数指定了一个接受一个参数的键函数，用于从数组中的每个元素中提取比较键。为了支持搜索复杂记录，该键函数不应用于x值。

import bisect
tuple_list = [(4, 117), (10, 129), (30, 197)]
# search among first indices - returns 1
bisect.bisect_left(tuple_list, 10, key=lambda i: i[0])
# search among second indices - returns 1
bisect.bisect_left(tuple_list, 129, key=lambda i: i[1])
# 2
bisect.bisect_left(tuple_list, 130, key=lambda i: i[1])

- Yar

Answer 4

请查看文档底部: http://docs.python.org/3/library/bisect.html。如果您想将元素与其它内容进行比较，您应该创建一个称为key的单独列表。在您的情况下，key是一个只包含元组中[1]的int类型列表。使用这个第二个列表使用bisect计算索引。然后使用它将元素插入到原始的(元组列表)中，并将key([1]的元组)插入到新的keys( int类型列表)。

- Thijs van Dien

---

使用bisect的主要优势是线性时间搜索。以线性时间方式复制列表意味着您可以执行线性搜索。 - Brent

@Brent 这取决于你要搜索多少次。我的想法是让你维护两个数据结构并协同工作。它们最好都从空开始。 - Thijs van Dien

Answer 5

建议对输入列表进行转换的答案会打败使用bisect的目的，因为会将应该是O(log n)的操作转换成O(n)。更好的解决方案是在输入上使用视图：

class _list_view:
    def __init__(self, a, key):
        self.a = a
        self.key = key

    def __getitem__(self, index):
        return self.key(self.a[index])


def bisect_left(a, x, lo=0, hi=None, key=id):
    from bisect import bisect_left
    hi = hi or len(a)
    if key == id:
        return bisect_left(a, x, lo, hi)
    return bisect_left(_list_view(a, key), x, lo, hi)

- Brent

Answer 6

我遇到了同样的问题。我正在存储一个由(file_id, word_frequency)元组列表，并希望按照元组中第二个元素word_frequency对列表进行排序。我进行了一些研究，发现了Python如何比较元组的方法，可以在这里找到https://howtodoinjava.com/python/compare-tuples/。

基本上，它查看两个元组的第一个元素并取较小的值。如果第一个元素相同，则比较第二个值，以此类推。

所以我交换了元组中的元素(word_frequency, file_id)。现在我使用bisect按照单词频率对列表进行了排序。

希望这可以帮助到你。

- samsri