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