Неожиданная кривая производительности от сортировки слиянием CPython

Question

Я реализовал простой алгоритм сортировки слиянием в 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. Но картина немного отличается:

http://s8.postimage.org/o8ysrafat/deque_long_run_2.png

Вещи, которые я пытался исследовать:

1. PyPy. Кривая в порядке.
2. Отключил GC с помощью модуля gc. Неправильное предположение. Вывод отладки показал, что он даже не запускается до конца теста.
3. Профилирование памяти с помощью meliae - ничего особенного или подозрительного. ` У меня была другая реализация (рекурсивная, использующая ту же функцию слияния), она действует аналогичным образом. Чем больше полных циклов тестирования я создаю - тем больше «скачков» в кривой.

Так, как это поведение можно объяснить и - мы надеемся - исправить?

UPD: изменены списки на collection.deque

UPD2: добавлен полный тестовый код

UPD3: я использую Python 2.7.1 на ОС Ubuntu 11.04, используя четырехъядерный ноутбук с частотой 2 Гц. Я пытался выключить большинство других процессов: количество пиков уменьшилось, но по крайней мере один из них все еще был.

Answer 1

Вы просто замечаете влияние других процессов на вашем компьютере.

Вы запускаете функцию сортировки 100 раз для размера ввода 1 и записываете общее время, потраченное на это. Затем вы запускаете его 100 раз для размера ввода 2 и записываете общее время, потраченное. Вы продолжаете делать это, пока не достигнете размера ввода 1000.

Допустим, время от времени ваша ОС (или вы сами) начинаете делать что-то интенсивное использование процессора. Допустим, этот «всплеск» длится столько, сколько вам потребуется, чтобы запустить функцию сортировки 5000 раз. Это означает, что время выполнения будет выглядеть медленным при 5000/100 = 50 последовательных входных размеров. Некоторое время спустя происходит новый всплеск, и другой диапазон размеров ввода выглядит медленным. Это именно то, что вы видите на графике.

Я могу придумать, как избежать этой проблемы. Запустите функцию сортировки только один раз для каждого размера ввода: 1, 2, 3, ..., 1000. Повторите этот процесс 100 раз, используя те же 1000 входов (это важно, см. Пояснение в конце). Теперь возьмите минимум времени, потраченного на каждый входной размер, в качестве конечной точки данных для диаграммы.

Таким образом, ваши пики должны влиять только на каждый входной размер только несколько раз из 100 прогонов; и поскольку вы берете минимум, они, скорее всего, никак не повлияют на окончательный график.

Если ваши всплески действительно очень длинные и частые, вам, конечно, может потребоваться увеличить количество повторений сверх текущих 100 на входной размер.

Глядя на ваши всплески, я замечаю, что выполнение замедляется ровно в 3 раза во время всплеска. Я предполагаю, что ОС дает вашему процессу Python один слот из трех во время высокой нагрузки. Правильно ли мое предположение или нет, рекомендованный мной подход должен решить эту проблему.

EDIT:

Я понял, что не уточнил ни одного момента в моем предложенном решении вашей проблемы.

Следует ли использовать один и тот же вход в каждом из ваших 100 прогонов для заданного размера ввода? Или следует использовать 100 различных (случайных) входов?

Поскольку я рекомендовал взять минимальное время выполнения, входные данные должны быть одинаковыми (в противном случае вы получите неправильный вывод, поскольку вы будете измерять сложность алгоритма в лучшем случае вместо средней сложности!).

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

Таким образом, лучшим решением является решение проблемы загрузки системы, не создавая проблему только одного ввода на размер ввода (это, очевидно, псевдокод):

seed = 'choose whatever you like'
repeats = 4
inputs_per_size = 25
runtimes = defaultdict(lambda : float('inf'))
for r in range(repeats):
  random.seed(seed)
  for i in range(inputs_per_size):
    for n in range(1000):
      input = generate_random_input(size = n)
      execution_time = get_execution_time(input)
      if runtimes[(n, i)] > execution_time:
        runtimes[(n,i)] = execution_time
for n in range(1000):
  runtimes[n] = sum(runtimes[(n,i)] for i in range(inputs_per_size))/inputs_per_size

Теперь вы можете использовать runtimes [n] для построения своего графика.

Конечно, в зависимости от того, является ли ваша система очень шумной, вы можете изменить (repeats, inputs_per_size) с (4,25) на (10,10) или даже (25,4).

Answer 2

Я могу воспроизвести шипы, используя ваш код:

Вы должны выбрать соответствующую функцию синхронизации (time.time() против time.clock() - from timeit import default_timer),количество повторений в тесте (сколько времени занимает каждый тест) и количество тестов, из которых можно выбрать минимальное время.Это дает вам большую точность и меньше внешнего влияния на результаты.Прочитайте примечание из timeit.Timer.repeat() документов:

Заманчиво рассчитать среднее и стандартное отклонение от вектора результатов и сообщить о них.Однако это не очень полезно.В типичном случае самое низкое значение дает нижнюю границу для того, насколько быстро ваша машина может выполнить данный фрагмент кода;более высокие значения в векторе результатов, как правило, вызваны не изменчивостью скорости Python, а другими процессами, влияющими на точность синхронизации.Так что min () результата, вероятно, единственное число, которое вас должно заинтересовать. После этого вы должны смотреть на весь вектор и применять здравый смысл, а не статистику.

*Модуль 1021 *timeit может выбрать для вас подходящие параметры:

$ python -mtimeit -s 'from m import testdata, sort; a = testdata[:500]' 'sort(a)'

---

Вот кривая производительности на основе timeit:

На рисунке показано, что поведение sort() соответствует O(n*log(n)):

|------------------------------+-------------------|
| Fitting polynom              | Function          |
|------------------------------+-------------------|
| 1.00  log2(N)   +  1.25e-015 | N                 |
| 2.00  log2(N)   +  5.31e-018 | N*N               |
| 1.19  log2(N)   +      1.116 | N*log2(N)         |
| 1.37  log2(N)   +      2.232 | N*log2(N)*log2(N) |

. Для создания фигуры я использовал make-figures.py:

$ python make-figures.py --nsublists 1 --maxn=0x100000 -s vkazanov.msort -s vkazanov.msort_builtin 

где:

# adapt sorting functions for make-figures.py
def msort(lists):
    assert len(lists) == 1
    return sort(lists[0]) # `sort()` from the question

def msort_builtin(lists):
    assert len(lists) == 1
    return sorted(lists[0]) # builtin

Описаны входные списки здесь (примечание: вход отсортирован так, что встроенная функция sorted() показывает ожидаемую O(N) производительность).