Используя bisect в списке кортежей?

Question

Я пытаюсь выяснить, как использовать bisect в списке кортежей, например

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

Что дает мне unorderable types: int() < tuple()

Answer 1

Вы можете разделить значения в отдельные списки.

from bisect import bisect

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

Обратите внимание, что для bisect на работу, ваши данные действительно должны быть упорядочены...

Answer 2

В некоторых случаях просто

bisect(list_of_tuples, (3, None))

будет достаточно.

Так как None будет сравнивать меньше любого целого числа, это даст вам индекс первого кортежа, начинающийся как минимум с 3, или len(list_of_tuples) если все они меньше 3. Обратите внимание, что list_of_tuples отсортировано

Answer 3

Начиная с версии 3.10вы можете передать ключ bisectметоды для указания индекса, по которому вы хотите выполнить поиск — больше информации здесь:

key указывает ключевую функцию одного аргумента, которая используется для извлечения ключа сравнения из каждого элемента в массиве. Для поддержки поиска сложных записей функция 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])

Answer 4

Проверьте нижний раздел документации: http://docs.python.org/3/library/bisect.html. Если вы хотите сравнить с чем-то другим, кроме самого элемента, вы должны создать отдельный список так называемых ключей. В вашем случае список целых, содержащий только [1] кортежа. Используйте этот второй список, чтобы вычислить индекс с помощью bisect. Затем используйте это, чтобы вставить элемент в оригинал (список кортежей) и ключ ([1] кортежа) в новый список ключей (список целых).

Answer 5

Ответы, предлагающие преобразовать входной список, противоречат цели деления пополам, преобразовывая то, что должно быть 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)

Answer 6

Я столкнулся с той же проблемой. Я хранил список(file_id, word_frequency) кортежей и хотел получить список, отсортированный по второму элементу в кортеже, который word_frequency. Я провел небольшое исследование и выяснил, как python сравнивает кортежи, описанные здесь https://howtodoinjava.com/python/compare-tuples/.

По сути, он смотрит на первый элемент двух кортежей и берет меньший. Если первые элементы совпадают, сравниваются вторые значения и так далее.

Итак, я заменил элементы в кортеже (word_frequency, file_id). Теперь мой список отсортирован по частоте слов с помощью биссектрисы.

Надеюсь это поможет