Я реализовал простой алгоритм сортировки слиянием в Python. Алгоритм и тестовый код приведены ниже:
import time
import random
import matplotlib.pyplot as plt
import math
from collections import deque
def sort(unsorted):
if len(unsorted) <= 1:
return unsorted
to_merge = deque(deque([elem]) for elem in unsorted)
while len(to_merge) > 1:
left = to_merge.popleft()
right = to_merge.popleft()
to_merge.append(merge(left, right))
return to_merge.pop()
def merge(left, right):
result = deque()
while left or right:
if left and right:
elem = left.popleft() if left[0] > right[0] else right.popleft()
elif not left and right:
elem = right.popleft()
elif not right and left:
elem = left.popleft()
result.append(elem)
return result
LOOP_COUNT = 100
START_N = 1
END_N = 1000
def test(fun, test_data):
start = time.clock()
for _ in xrange(LOOP_COUNT):
fun(test_data)
return time.clock() - start
def run_test():
timings, elem_nums = [], []
test_data = random.sample(xrange(100000), END_N)
for i in xrange(START_N, END_N):
loop_test_data = test_data[:i]
elapsed = test(sort, loop_test_data)
timings.append(elapsed)
elem_nums.append(len(loop_test_data))
print "%f s --- %d elems" % (elapsed, len(loop_test_data))
plt.plot(elem_nums, timings)
plt.show()
run_test()
Насколько я вижу, все в порядке, и в результате я должен получить хорошую кривую N * logN. Но картина немного отличается:
Вещи, которые я пытался исследовать:
- PyPy. Кривая в порядке.
- Отключил GC с помощью модуля gc. Неправильное предположение. Вывод отладки показал, что он даже не запускается до конца теста.
- Профилирование памяти с помощью meliae - ничего особенного или подозрительного. ' У меня была другая реализация (рекурсивная, использующая ту же функцию слияния), она действует аналогичным образом. Чем больше полных циклов тестирования я создаю - тем больше "скачков" в кривой.
Итак, как это поведение можно объяснить и, мы надеемся, исправить?
UPD: изменены списки на collection.deque
UPD2: добавлен полный тестовый код
UPD3: я использую Python 2.7.1 на ОС Ubuntu 11.04, используя четырехъядерный ноутбук с частотой 2 Гц. Я пытался выключить большинство других процессов: количество пиков уменьшилось, но по крайней мере один из них все еще был.
