Блог

Главная - Вопросы по программированию - Почему моему коду требуется в 1000 раз больше времени для сортировки списков из 2, чем из 4

Почему моему коду требуется в 1000 раз больше времени для сортировки списков из 2, чем из 4

#python

#python

Вопрос:

Я пытаюсь подсчитать, сколько времени требуется коду selectionsort для сортировки списка длиной 2 ^ i, но по какой-то причине сортировка 2 ^ 1 занимает больше времени, чем 2 ^ 2 с большим отрывом.

 import random
import time

def selectionsort(mylist):
    sortedlist=[]
    while len(mylist) > 0:
        lowest = mylist[0]
        for i in mylist:
            if i < lowest:
                lowest=i
        sortedlist.append(lowest)
        mylist.remove(lowest)
    return sortedlist

mylist = []
ivalues = []
sorttimelist = []
for i in range(2):
    ivalues.append(2**i)
    for x in range(2**i):
        mylist.append(random.random())
    start_time=time.perf_counter()
    selectionsort(mylist)
    end_time=time.perf_counter()
    sorttime=end_time-start_time
    sorttimelist.append(sorttime)
    mylist.clear()
print(sorttimelist)

Использование печати только для проверки правильности.

Комментарии:

1. Пожалуйста, убедитесь, что ваш пример является полным — достаточно кода, чтобы кто-то другой мог его запустить. Здесь вы вызываете selectionsort(mylist) , а затем выполняете mylist.clear() , по-видимому, используя глобальный mylist , который здесь не показан. В любом случае, вы должны использовать стандартный библиотечный timeit модуль для синхронизации производительности, а не пытаться сделать это самостоятельно.

2. Зачем уничтожать список в процессе его сортировки? Вы должны быть в состоянии избежать remove (что неэффективно).

3. Подобное тестирование с одной тестовой итерацией и такими маленькими размерами данных бессмысленно. Я предполагаю, что первый тест «прогревает» систему и поэтому занимает больше времени. Какой бы тест вы ни запустили вторым, он будет быстрее из-за этого. Попробуйте изменить порядок тестов, и я уверен, вы получите разные результаты. Кроме того, попробуйте выполнить каждый тест 1000 раз в цикле и сравнить это время.

Ответ №1:

Подобное тестирование с одной тестовой итерацией и такими маленькими размерами данных бессмысленно. Я предполагаю, что первый тест «прогревает» систему и поэтому занимает больше времени. Какой бы тест вы ни запустили вторым, он будет быстрее из-за этого.

Я улучшил ваш код, чтобы запускать каждый тест 10000 раз, суммируя отдельные времена. Когда я делаю это, второе число больше первого каждый раз, когда я его запускаю. Вот новый тестовый код:

 sorttimelist = []
for i in range(2):
    total_time = 0
    for iter in range(10000):
        mylist = []
        for x in range(2 ** i):
            mylist.append(random.random())
        start_time = time.perf_counter()
        selectionsort(mylist)
        end_time = time.perf_counter()
        sorttime = end_time - start_time
        total_time  = sorttime
        mylist.clear()
    sorttimelist.append(total_time)

print(sorttimelist)

И несколько примеров результатов:

 [0.0065520769999985184, 0.0096335120000004]
[0.00565655999999945,   0.009094481000001708]
[0.005614095000000513,  0.00950561699999955]
Метки: