Почему моя "сортировка Вставками" на Python такая медленная?

Question

я только учусь кодить на Python. Задача "Сделать сортировку Вставками". У людей на с++ уходит +- 6 сек, а у меня больше 9 мин. Подскажите, это я криворукий или проблема в python? Если ставит 100000 элементов и больше


from random import randint
import time
def insertion_sort(array):
    length = len(array)
    for i in range(1, length):
        key = array[i]
        j = i
        if a == 1:
            while (j - 1 >= 0) and (array[j - 1] > key):
                array[j - 1], array[j] = array[j], array[j - 1]
                j = j - 1
            array[j] = key
        elif a == 2:
            while (j - 1 >= 0) and (array[j - 1] < key):
                array[j] = array[j-1]
                j = j - 1
            array[j] = key

print("Сортировка вставками")
arr = []
length = int(input("Введите длину массива: "))
a = int(input("Введите тип сортировки: 1- по возрастанию, 2- по убыванию "))
start_time = time.time()
for i in range(0, length):
    arr.append(randint(0, 100))
print ("Рандомный массив: ")
print (arr)
    
insertion_sort(arr) 
print("Отсортированный массив: ") 
print(arr)
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

def insert_sort(lst):
    for i in range(len(lst)):
            v = lst [i]
            j = i;
            while (lst [j-1] > v) and (j > 0):
                lst [j] = lst [j-1]
                j = j - 1
            lst [j] = v

На моем компе сокращение времени с

--- 757.0937943458557 seconds ---

до

--- 469.13333559036255 seconds ---

Не думаю, что дело просто в отсутствии проверки if a == 1:. Скорее всего, и в сокращении количества пересчетов индексов. Но надо бы это проверить.

Не 6 сек, конечно (хотя и не очень верится), но уже быстрее.

Ну и по хорошему - начальный замер времени надо делать непосредственно перед вызовом процедуры, а не перед генерацией массива и выводом.

Answer 2

Зайду из далека. Разработку программы можно разделить на два этапа - получение правильного решения, оптимизация. В нашей задаче правильное решение уже есть, займёмся оптимизацией.

Оптимизацию делают только если она нужна и тут она нужна - в этом и состоит вопрос.

Оптимизация состоит из двух кусков - О-большое и константа. О-большое не зависит от компьютера, языка и компилятора, только от алгоритма. Алгоритм фиксирован - сортировка вставками. Получается повлиять на О-большое мы не можем. Зачем я его тогда поминаю? Затем что буду отвечать на вопрос "почему медленно?" и О-большое понадобится чтобы понять где улучшать константу, а где не имеет смысла.

Константа - единственное что нам остаётся. Один и тот-же алгоритм можно записать с помощью разных примитивных операций, что меняет константу.

Вот кусок оригинального кода. Я убрал некоторые элементы:

for i in range(1, length):
    key = array[i]
    j = i
    while (j - 1 >= 0) and (array[j - 1] > key):
        array[j - 1], array[j] = array[j], array[j - 1]
        j = j - 1
    array[j] = key

Это квадратичный алгоритм: внешний цикл выполняется N раз (N - длина массива), внутренний может выполняться от 1 до N раз. На случайном массиве, он потребует в среднем N/4 операций. Сложности перемножаются, получаем сложность N^2.

Как можно его ускорить? На что обратить внимание? Чем больше раз инструкция повторяется, тем больше её вклад в общее время работы. Поэтому смотрим в самый глубокий цикл. В нём операции исполняются квадратичное количество раз. В отличие например от оператора j = i, который выполняется только N раз.

Внутренний цикл делает две вещи: находит место куда вставить новый элемент и вставляет его. При вставке все элементы правее его должны сдвинутся вправо на одно место. Сейчас это сделано в одном цикле. Но функции могут быть разделены.

Интерпретатор Питона работает не торопясь, это правда. Поэтому нам надо чтобы он работал как можно меньше. Попытаемся переработать внутренний цикл так чтобы он перестал быть циклом. Можно ли отыскать место для вставки элемента без цикла? Да, можно. bisect.bisect отыскивает позицию для вставки элемента в сортированный участок массива. Она делает это быстрее чем за линейное время (что в данном случае не важно, как ни странно) и она написана на C. Последнее важно, так как у кода на C лучше константа - инструкции выполняются быстрее.

Когда место найдено, надо подвинуть элементы справа от этого места. Сейчас это делает цикл, но это можно сделать в одну операцию используя нотацию a[i:j]. Копирование всё равно будет сделано по элементам в цикле, но это цикл на C - снова лучшая константа.

Влияет ли if a == 1: на время работы? Нет, не влияет. Или влияет, но вы это влияние не измерите и не почувствуете. Сам if выполняется за константу, сразу за ним идёт цикл while, который исполняется за N. Удаление if для N = 100_000 даст выигрыш в одну стотысячную (я огрубляю). Такой выигрыш не стоит байтов, которые пошли на этот абзац.

Однако if в коде ниже удалён, но не потому что так быстрее. А потому что bisect не умеет вставлять в убывающий массив.

Собирая всё вместе получим код который сортирует 100_000 чисел за сорок секунд:

import bisect
import time


def insertion_sort(array):
    for i, key in enumerate(array):
        j = bisect.bisect(array, key, lo=0, hi=i)
        array[j + 1:i + 1] = array[j:i]
        array[j] = key


n = 100000
arr = list(reversed(range(n)))
start_time = time.time()
insertion_sort(arr)
stop_time = time.time()
print(arr)
print(stop_time - start_time)

P.S. Отвечая на ваш вопрос: главная проблема - алгоритм. Он квадратичный. Это значит если вы увеличить размер массива в 10 раз, время работы вырастет в 100 раз. Это важный факт, который не зависит от компьютера, языка программирования и ваших программистских талантов. Сортировка вставками медленная (хотя из этого утверждения есть исключения).

Вторая проблема - константа. Тут вы можете сделать лучше или хуже. Обычно, чтобы было лучше нужно передать ответственность от кода на Питоне коду на C. Учите стандартную библиотеку и будет вам счастье.

БЛОГ НА HUSL

Почему моя "сортировка Вставками" на Python такая медленная?

Ответы (2 шт):