Является ли вставка heapq быстрее, чем вставка пополам?

Question

У меня есть вопрос о bisect и heapq.

Сначала я покажу вам 2 версии кода, а затем задам вопрос об этом.

версия использования bisect :

while len(scoville) > 1:
    a = scoville.pop(0)
    #pops out smallest unit
    if a >= K:
        break
    b = scoville.pop(0)
    #pops out smallest unit
    c = a + b * 2
    bisect.insort(scoville, c)

версия использования heapq

while len(scoville) > 1:
    a = heapq.heappop(scoville)
    #pops out smallest unit
    if a >= K:
        break
    b = heapq.heappop(scoville)
    #pops out smallest unit
    c = a + b * 2
    heapq.heappush(scoville, c)

Оба алгоритма используют 2 всплывающих окна и 1 вставку.

Как я знаю, в версии с использованием bisect операция pop для списка равна O (1), а операция вставки класса bisect - O (logn).

А в версии с использованием heapq операция pop для heap равна O (1), а операция вставки heap в среднем O (logn).

Таким образом, оба кода должны иметь одинаковую эффективность по временипримерно.Тем не менее, версия использования bisect - это постоянный провал теста эффективности времени на каком-то сайте с вызовом кода.

У кого-нибудь есть надежда?

* scoville - список целых чисел

Answer 1

Ваши предположения неверны. Ни pop(0) O (1), ни bisect.insort O (logn).

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

Из документации bisect.insort:

bisect.insort_left(a, x, lo=0, hi=len(a))

Вставить x в отсортированном порядке. Это эквивалентно a.insert (bisect.bisect_left (a, x, lo, hi), x) при условии, что a уже отсортировано. Имейте в виду, что в поиске O (log n) преобладает медленный шаг вставки O (n).

Вы можете проверить это, создав действительно длинный список, скажем l = list(range(10**8)), а затем выполнить l.pop(0) или l.pop() и bisect.insort(l, 0) или bisect.insort(l, 10**9). Операции выталкивания и вставки в конце должны быть мгновенными, в то время как другие имеют небольшую, но заметную задержку. Вы также можете использовать %timeit для повторного тестирования в более коротких списках, если вы поочередно извлекаете и вставляете так, чтобы длина списка оставалась постоянной на протяжении многих тысяч прогонов:

>>> l = list(range(10**6))
>>> %timeit l.pop(); bisect.insort(l, 10**6)
100000 loops, best of 3: 2.21 us per loop
>>> %timeit l.pop(0); bisect.insort(l, 0)
100 loops, best of 3: 14.2 ms per loop

Таким образом, версия, использующая bisect, равна O (n), а версия с heapq - O (logn).