Странные результаты при измерении сортировки по Radix

Question

Я измеряю время выполнения сортировки Radix и Counting, используя timeit модуль. Я использую 100 наборов случайных целых чисел, лежащих на интервале <0; 1000000>. Все целые числа уникальны в наборе. Первый набор состоит из 10000 целых чисел, последний набор - 1000000 целых чисел. Каждый набор сортируется в десять раз, а среднее время записывается (как full time/10). В лог-файле сортировки Radix есть некоторые странные результаты, и я не уверен, что это проблема timeit модуль или мой алгоритм сортировки:

Radix сортировка журнала

integers count, average time
......,.............
760000,1.51444417528
770000,1.31519716697
780000,1.33663102559
790000,1.3484539343
800000,1.37114722616
810000,1.61706798722
820000,1.4034960851
830000,1.65582925635
840000,1.68017826977
850000,1.69828582262
860000,1.47601140561
870000,1.73875506661
880000,1.75641094733
890000,1.54894320189
900000,1.80121665926
910000,1.56070168632
920000,1.8451221867
930000,1.8612749805
940000,1.61202779665
950000,1.63757506657
960000,1.64939744866
970000,1.66534313097
980000,1.68155078196
990000,1.69781920007
1000000,2.00389959994

Вы можете видеть, что сортировка большего набора, чем предыдущий, иногда занимает меньше времени. В случае Counting Sort время увеличивается нормально.

Вот мой код для сортировки по Radix:

from __future__ import division

def sortIntegerList (listToSort, base):
    maxkey = len(str(max(listToSort)))

    for i in range(maxkey):
        bucketList = [[] for x in range(base)]

        for number in listToSort:
            bucketList[(number//base**i) % base].append(number)

        listToSort = []

        for l in bucketList:
            listToSort.extend(l)

    return listToSort

Вот мой код для подсчета сортировки:

def sortIntegerList (listToSort):
    maxkey = max(listToSort)
    countingList = [0 for x in range(maxkey + 1)]

    for i in listToSort:
        countingList[i] += 1

    for i in range(1, len(countingList)):
        countingList[i] += countingList[i-1]

    sortedList = [0 for x in range(len(listToSort) + 1)]

    for i in listToSort:
        sortedList[countingList[i]] = i
        countingList[i] -= 1

    del sortedList[0]
    return sortedList

Вот код для измерения времени выполнения:

import timeit

outputFileCounting = "count,time\n"
outputFileRadix = "count,time\n"

# Counting Sort
for x in range(10, 1001, 10):
    setup_counting = """
from sorters import counting_sort
import cPickle
with open("ri_0-1000k_{0}k.pickle", mode="rb") as f:
    integerList = cPickle.load(f)
        """.format(x)

    time_counting = timeit.timeit("""counting_sort.sortIntegerList(integerList)""",
                                setup = setup_counting, number=10)

    outputFileCounting += "{0},{1}\n".format(str(x*1000), time_counting/10)

    with open("sort_integer_counting_results.csv", mode="w") as f:
        f.write(outputFileCounting)

# Radix Sort
for x in range(10, 1001, 10):
    setup_radix = """
from sorters import radix_sort
import cPickle
with open("ri_0-1000k_{0}k.pickle", mode="rb") as f:
    integerList = cPickle.load(f)
        """.format(x)

    time_radix = timeit.timeit("""radix_sort.sortIntegerList(integerList, 10)""",
                                setup = setup_radix, number=10)

    outputFileRadix += "{0},{1}\n".format(str(x*1000), time_radix/10)

    with open("sort_integer_radix_results.csv", mode="w") as f:
        f.write(outputFileRadix)

Каждый набор целых чисел хранится в виде списка в pickle файл.

Answer 1

Ваша сортировка radix делает много распределения и перераспределения памяти, как она идет. Интересно, может быть, в этом проблема? Что делать, если вы только один раз выделили память для своих структур данных, и приняли тот факт, что вам нужно будет перераспределить.

Кроме этого, вы проверили, чтобы убедиться, что окончательные списки действительно отсортированы? Рассматривали ли вы другие статистические данные для своего времени радикальной сортировки (например, мин / макс / медиана), возможно, есть случайные выбросы, изучение которых может помочь вам объяснить вещи.