Сравнение скорости между функцией bisect.insort и list.index и функцией вставки

Question

Как говорит Python doc, я думал, что модуль bisect намного быстрее встроенного метода списка, индекса и вставки для вставки элемента в длинный упорядоченный список. Итак, я просто измеряю затраты времени на обе функции, bisect_func() а также insert_func() как ниже код.

bisect_func() оценка 1,27 с и insert_func() оценка 1,38 с, что не является значительной разницей во времени. Мой вопрос заключается в том, что я что-то пропускаю, чтобы проверить эффективность bisect в этом примере? Или bisect не единственный эффективный подход для вставки элемента в упорядоченный список?

import bisect

HAYSTACK = [n for n in range(100000000)]
NEEDLES = [0, 10, 30, 400, 700, 1000, 1100, 2200, 3600, 32000, 999999]

def bisect_func():
    for needle in reversed(NEEDLES):
        bisect.insort(HAYSTACK, needle)

def insert_func():
    for needle in reversed(NEEDLES):
        position = HAYSTACK.index(needle)
        HAYSTACK.insert(position, needle)

if __name__ == '__main__':
    import time
    start = time.time()
    # bisect_func()
    insert_func()
    end = time.time()
    print(end - start)

Answer 1

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

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

Важная часть: Имейте в виду, что в поиске O (log n) преобладает медленный шаг вставки O (n). Таким образом, оба подхода являются O (n) в конце, поэтому их эффективность одинакова, с insort быть немного лучше.

Answer 2

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