Quicksort не становится быстрее

Недавно я узнал, как много люди работали, чтобы сделать quicksort быстрее. От случайного выбора элемента pivot до переключения на сортировку вставки для небольших массивов и даже работы с равными ключами с 3-полосным разделением. Мне было любопытно, как все работает для случайно сгенерированных данных, и я подумал о профилировании некоторого кода python. Я прилагаю сценарий(ы) ниже. Проблема в том, что сценарии в конечном итоге занимают одинаковое количество времени! И когда я использую %prun, это выглядит как количество раз quicksort называется также довольно похожим. Итак, все улучшения, которые мы делаем, полезны только тогда, когда наши данные соответствуют худшему случаю (очень сильно отсортированы в неправильном направлении?) 

def hoare_partition(a, lo, hi):

    if lo >= hi or (lo + 1) == len(a) - 1:
        return None
    pivot = a[lo]
    left = lo + 1
    right = hi


    while left <= right and right < len(a):
        while left < len(a) and a[left] < pivot:
            left += 1
        while a[right] > pivot:
            right -= 1
        if left <= right and right < len(a):
            a[left], a[right] = a[right], a[left]
            left += 1
            right -= 1
    a[lo], a[right] = a[right], a[lo]
    return right

def hoare_quicksort(a, lo, hi):
    ''' this is a vanilla implementation of quick sort. this will call the partition method that uses first element as pivot '''

    if lo < hi:
        p = hoare_partition(a, lo, hi)
        if p:
            #print 'calling for ', lo, p - 1
            hoare_quicksort(a, lo, p - 1)  

            #print 'calling for ', p + 1, hi
            hoare_quicksort(a, p + 1, hi)

Это была реализация vanilla, где мы выбираем сам первый элемент в качестве pivot. Затем я изменил, чтобы выбрать среднюю точку.

Итак, одна строка изменяется 

mid = lo + (hi - lo)//2

a[lo], a[mid] = a[mid], a[lo]
pivot = a[lo]

А затем я также произвольно выбираю разворот, например: 

pos = random.randint(lo, hi + 1)


a[lo], a[pos] = a[pos], a[lo]
pivot = a[lo]

Теперь я называю их использование 

%prun hoare_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun mid_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun random_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)

Все они занимают почти столько же времени (5.22, 5.27, 5.61 МС). Когда я звоню им с помощью %prun и вижу, сколько раз вызывается quicksort, я снова получаю очень похожие номера. Так что же случилось?

3 2
python sorting quicksort

3 ответа:

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

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

Вы проверили свои быстрые срезы на случайных данных. Это очень мило это самый лучший сценарий для быстрой смерти. Что делать, если данные поступают из ключей dict, и используемый хэш заставляет их выходить в основном отсортированном порядке?

>>> data = dict.fromkeys(random.sample(xrange(10000), 9000)).keys()
>>> timeit.timeit('rand_quicksort(data[:], 0, len(data)-1)', 'from __main__ impo
rt rand_quicksort, data', number=1)
0.06688880239187256
>>> timeit.timeit('hoare_quicksort(data[:], 0, len(data)-1)', 'from __main__ imp
ort hoare_quicksort, data', number=1)
  # about 1000 lines omitted
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 9, in hoare_quicksort
  File "<stdin>", line 4, in hoare_quicksort
RuntimeError: maximum recursion depth exceeded
Ну, мы получаем переполнение стека, и это ужасно. Даже если бы мы этого не сделали, это заняло бы чертовски много времени.

(Если вы хотите воспроизвести этот результат, обратите внимание, что у вас есть несколько ошибок в коде. if p должно быть if p is not None, а random.randint(lo, hi + 1) должно быть random.randint(lo, hi) или random.randrange(lo, hi + 1). Я должен был исправить их, чтобы получить правильные результаты тестов.)

1

Ваш бенчмарк сломан.

  1. Вы оцениваете 1000 итераций random.randint, а не ваши виды.
  2. вы запускаете каждую сортировку только один раз, поэтому вы оцениваете задержки переключения потоков и процессов в вашей ОС.

Попробуйте предварительно создать исходный массив и выполнить каждую сортировку thouthands, даже миллионы раз.

3

Случайный выбор пивота не делает quicksort быстрее: это полезно только для того, чтобы избежать того, что наш алгоритм выполняет худший вариант. Предположим, что мы сортируем уже отсортированный вектор, и мы решаем выбрать pivot в качестве правого элемента каждого подмассива: он содержит максимум этого подмассива, поэтому quicksort разбивает подмассив на 2 части самым несбалансированным образом. это можно предотвратить путем рандомизации. если мы уверены, что избежим худшего случая, то можем сказать, что алгоритм принимает аналогичную сумму времени до тех пор, пока каждый уровень рекурсии не создаст разбиение приблизительно постоянного баланса, поэтому мы можем доказать, что глубина дерева рекурсии постоянна

0