Используя bisect в списке кортежей, но сравнивать, используя только первое значение

Question

Я прочитал этот вопрос о том, как использовать 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,))

но в общем случае, когда могут быть числа с плавающей запятой, как это сделать, не зная максимальных значений 2-го элемента?

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

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)

Answer 2

Это реализация (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 источник. Следует также отметить, что список должен быть отсортирован по той же ключевой функции.

Answer 3

В дополнение к хорошим предложениям, я хотел бы добавить свой собственный ответ, который работает с плавающими (как я только что понял)

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

Answer 4

За это:

... хочу найти первый элемент, где 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))

Функция 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]
)