Самый быстрый алгоритм сортировки массива (20.01.2017).

2017 - Январь

20.01.2017 14:14

← Интернет-компромат на каждого (19.01.2017).		Спасти правую руку от разрушения (21.01.2017). →

В жизни бывают разные, совершенно парадоксальные ситуации. В данном случае: за 17 лет программирования, начиная с лабораторных в 9-м классе школы, ни разу не пригодилась сортировка быстрее пузырьковой (самого медленного и простого алгоритма сортировки). Что в личном программировании, что в коммерческом - все решалось либо встроенными в среду функциями сортировки вида Sort, либо самописной пузырьковой. Но вот настал момент, когда встроенных функций не было, а пузырьковая сортировка работала от 15 минут за 1 проход (от 262000 дробных чисел).

Анализ помог найти сводную таблицу, где анализировалось время, затраченное на сортировку 10000 целых чисел. Для самой медленной, пузырьковой, получилось 0.23с; для самой быстрой, поразрядной - 0.02с; для сортировки выбором было значение 0.03с (субъективно самая простая в реализации). Однако усомнился в данных: у сортировки пузырьком и выбором одинаковая сложность O(n²), а также попадались разные данные об улучшении быстродействия. В случае с таблицей это в 7.7 раза, в случае ответов живых программистов - "от 1 до 3 раз".

Вместо того, чтобы проводить самостоятельное тестирование всех существующих методов сортировки, решил остановиться на не представленном в таблице методе Шелла (модернизированный метод вставками). Сломал себе мозг, но написал функцию на VB6; а результат просто ошеломил.

Сортируемый массив:
- одномерный;
- double;
- дробные числа с 14 знаками после запятой;
- рэндомные номиналы;
- 2¹⁶ чисел (65536) и, для подтверждения, 2¹⁸ чисел (262144).

Условия тестирования: без дебаггера (отдельный EXE-файл), процессу полностью отдано свободное ядро процессора, программная индикация времени запуска и окончания сортировки, отключен DoEvents, приоритет реального времени.

Для 65536 чисел. Пузырьковая: упорядочить рэндомный массив - 92с, инвертировать (позиции элементов) упорядоченный массив - 127с. Шелла: упорядочить рэндомный массив - менее 1с, инвертировать упорядоченный массив - менее 1с. Стократное увеличение скорости.

Для 262114 чисел. Пузырьковая: упорядочить рэндомный массив - 1460c, инвертировать упорядоченный массив - 2046c. Шелла: упорядочить рэндомный массив - 3с, инвертировать упорядоченный массив - менее 1с. Сто-тысячекратное увеличение скорости. Можно использовать метод Шелла для инверсии больших упорядоченных массивов без циклического перебора элементов.

То есть, чем больше массив по размерности, тем больше преимущества в скорости сортировки Шелла над пузырьковой.

Кто хочет - пусть поэкспериментирует над поразрядной и быстрой сортировками. Они - конкуренты сортировки Шелла. Но последней мне надолго теперь хватит.

Исходный код (с DoEvents, все как положено). Он же находится теперь в архиве полезных исходников.

Стандартная сортировка Шелла была доработана так, что реализует:
- быструю сортировку по Шеллу, оптимизация скорости выполнения;
- возможность ускоряться или работать без зависания ПО и возвращая время сортировки;
- сортировать любую часть массива, а не только массив целиком;
- сортировать синхронно два массива сразу.

Private Function lSort_Array(ByRef dArray() As Double, bDirection As Boolean, ByRef dWith_Array() As Double, Optional sMessage As String, Optional bReturn_Time As Boolean, Optional bWith_Array As Boolean, Optional lBegin_Element As Long, Optional lEnd_Element As Double) As Long
'Сортировка методом Шелла - самая быстрая из сортировок рэндома. Возвращает затраченное время сортировки массива в секундах.
'dArray() - Основной массив (указатель), bDirection - направление соритровки (True - по возрастанию), dWith_Array() - дополнительный массив (указатель, сортируется вместе с основным),
'sMessage - сообщение пользователю (индикатор независания ПО), bReturn_Time - ускорение сортировки или вывод sMessage и возврат времени выполнения в секундах,
'bWith_Array - так как массив нельзя указать Optional, флаг используется как наличие dWith_Array() (заглушка - dArray, False),
'lBegin_Element - начальный элемент для сортировки части массива (с нуля), lEnd_Element - конечный элемент для сортировки части массива (с нуля).
1 On Error GoTo ErrorHandler

2 Dim dStep As Double 'Текущий шаг для сортировки вставкой.
3 Dim dTemp As Double, dTemp2 As Double 'Временные переменные для хранения значения вставки.
4 Dim i As Double, j As Double, k As Double 'Переменные для циклов сортировки методом Шелла.
5 Dim dateBegin_Time As Date 'Для вычисления времени работы в секундах.

6 If bReturn_Time Then dateBegin_Time = Time 'Если важна скорость - не тратить ресурсы на вычисление времени и индикацию выполнения.
7 If lEnd_Element = 0 And lBegin_Element >= 0 Then lEnd_Element = UBound(dArray) 'Коррекция входных параметров Optional.

8 dStep = Int((lEnd_Element - lBegin_Element) / 2) 'Работает и в случае нечетной размерности массива.

9 If bWith_Array Then 'Задвоение кода из-за нескольких строк приводит к увеличению скорости на 30%.
10     While dStep >= 1
11         If g_bCancel Then Exit Function 'Прерывание сортировки.

12         If bReturn_Time Then
13             DoEvents
14             If sMessage <> "" Then Label_Process.Caption = sMessage & UBound(dArray) - dStep & " / " & UBound(dArray) + 1
15         End If

16         For i = lBegin_Element To dStep + lBegin_Element
17             For j = i + dStep To lEnd_Element Step dStep
18                 dTemp = dArray(j)
19                 dTemp2 = dWith_Array(j)

20                 For k = j - dStep To lBegin_Element Step -dStep
21                     If bDirection Xor (dTemp < dArray(k)) Then Exit For
22                     dArray(k + dStep) = dArray(k)
23                     dWith_Array(k + dStep) = dWith_Array(k)
24                 Next k

25                 dArray(k + dStep) = dTemp
26                 dWith_Array(k + dStep) = dTemp2
27             Next j
28         Next i

29         dStep = Int(dStep / 2)
30     Wend
31 Else
32     While dStep >= 1
33         If g_bCancel Then Exit Function 'Прерывание сортировки.

34         If bReturn_Time Then
35             DoEvents
36             If sMessage <> "" Then Label_Process.Caption = sMessage & UBound(dArray) - dStep & " / " & UBound(dArray) + 1
37         End If

38         For i = lBegin_Element To dStep + lBegin_Element
39            For j = i + dStep To lEnd_Element Step dStep
40                dTemp = dArray(j)

41                For k = j - dStep To lBegin_Element Step -dStep
42                    If bDirection Xor (dTemp < dArray(k)) Then Exit For
43                    dArray(k + dStep) = dArray(k)
44                Next k

45                dArray(k + dStep) = dTemp
46            Next j
47        Next i

48        dStep = Int(dStep / 2)
49    Wend
50 End If

51 If bReturn_Time Then lSort_Array = DateDiff("s", dateBegin_Time, Time)

1000000 Exit Function
ErrorHandler:
1000001 If Err.Number <> 364 And Err.Number <> 0 Then MsgBox ("Ошибка функции lSort_Array №" & Err.Number & ", '" & Err.Description & "', строка " & Erl())
End Function

(добавлено 21.01.2017) Есть теория еще большего ускорения алгоритма:
14                If (dTemp > dArray(k) And bDirection = True) Or (dTemp < dArray(k) And bDirection
заменить на
14                If bDirection Xor (dTemp < dArray(k))

Это не равнозначные строки, т.к. вставляется равенство ">=" в If (dTemp > dArray(k). Равенство уменьшает скорость работы алгоритма, не оказывая влияние на результаты сортировки. Xor, по заявлениям программистов, работает быстрее - но при другом использовании.

(добавлено 22.01.2017) Xor быстрее оказался. Для трех массивов с 16 миллионами значений получены результаты:
- без Xor: 9:56, 1:05, 1:07;
- с Xor (несмотря на возвращение ">=" в строку сравнения): 6:49, 48, 49.

Так же обнаружилась разница в скорости выполнения между If bDirection и If bDirection = True. Несмотря на абсурдность ситуации, значения такие:
- без True: 6:58, 46, 47;
- с True: 7:19, 48, 48.

Разница в скорости Not и = False дала противоположный результат: 8:00, 1:18, 49 - против 7:29, 1:11, 47. Скорее всего, это связано с самой логикой кода: Not - инвертирует, а потом сравнивает с True; = False же - просто сравнивает с False.

(добавлено 07.02.2017) Допилил окончательно.

(добавлено 08.02.2017) Данная сортировка пригодилась даже при тестировании скорости ядер процессоров. Время, затрачиваемое на сортировку одного и того же массива одним ядром, на разных процессорах различно. Оказалась подтверждена теория, что 2 ядра по 4ГГц лучше, чем 4 ядра по 2ГГц. Пока еще не все программы научились работать с несколькими (всеми) ядрами процессора.

Теги:

Обновлено ( 31.12.2022 23:15 )