Задача о m максимумах

Без сортировки задача может быть решена, например, так. Создаем рабочий массив длины m и заполняем его начальными значениями. В общем случае можно в качестве такого значения выбрать минимальное значение int/integer для соответствующей среды программирования. А если известна нижняя граница значений исходного массива, то можно взять любое число, меньшее этой границы.

Итак рабочий массив заполнен одинаковыми значениями. Теперь берем элемент за элементом исходного массива и вставляем его в нужное место рабочего массива. При этом длину рабочего массива сохраняем равной m (после вставки последний элемент пропадает). Если очередной элемент меньше последнего значения рабочего массива, то он просто пропускается. Этот процесс имеет вычислительную сложность O(nm). Тогда как сортировка в лучшем случае описывается асимптотикой O(n*og(n)). Асимптотики показывают, как ведет себя функция (в данном случае - время сортировки) при стремлении параметров к бесконечности. Можно сказать, что время описанного алгоритма при стремлении n к бесконечности задается формулой t1=k1*O(n), а время сортировки t2=k2*O(n*log(n)). Здесь k1 и k2 - некие константы, зависящие от процессора, языка программирования, операционной системы и других факторов.

Я построил три системы тестов (для Питона, Java и VBA). Все тесты устроены по сути одинаково: строились массивы возрастающих размеров, заполнялись случайными числами задаваемого диапазона, сортировались с фиксацией времени и прогонялись через описанный выше алгоритм тоже с фиксацией времени. Каждый тест повторялся 10 раз и время усреднялось. В Питоне и Java использовалась встроенная сортировка, в VBA - реализация QuickSort.

Питон

Ниже показан код питоновских тестов.

import timefrom random import randint    def max_n_1(arr,n):    return sorted(arr,reverse=True)[0:n]    def max_n_2(arr,n):    res=[-1 for _ in range(n)]    for x in arr:        if x > res[n-1]:            i=n-1            j=i-1            while(j>=0 and res[j]<x):                res[i]=res[j]                i=i-1                j=j-1            res[i]=x    return res      def start():    k=10    n=10000    print("k=",k)    while(n<=500000):        print("n=",n,end=' ')        t1=0.0        for i in range(10):            arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z1=max_n_1(arr,k)            fin_time = time.time()            t1=t1+(fin_time-start_time)        print(t1/10.0,end=' ')            t2=0.0        for i in range(10):             arr=[randint(1,2000) for _ in range(n)]            start_time = time.time()            z2=max_n_2(arr,k)            fin_time = time.time()            t2=t2+(fin_time-start_time)        print(t2/10.0)            n+=10000        start()

Размеры массива менялись от 10 до 500 тыс. элементов с шагом 10 тыс. Было выполнено два прогона: определение пяти и десяти максимумов. Результат для 10 максимумов показан ниже.

Время здесь приведено в миллисекундах. Что видим? Сортировка отстает (на краю интервала - вдвое). Для пяти максимумов картина аналогична. И надо заметить, что хотя питоновская сортировка очень эффективна, простой алгоритм оказывается быстрее. Заметны резкие провалы в производительности (зубцы на графиках). Они, вероятно, объясняются влиянием внутренних процессов (типа сборки мусора). Это же замечание относится и к другим графикам.

Java

Код тестов выглядел так:

import java.util.*;class Start{   public static void main(String [] args)   {       Random random = new Random();    Scanner inp = new Scanner(System.in);    long startTime,endTime,tot1,tot2;    int i,a,b,n,m,x,ii,jj,u;    a=1;    b=3000; // диапазон случайных чисел [a,b]    m=10;        System.out.println(a+" "+b+" "+m);    for (n=50000; n<=5000000; n+=50000)    {    int arr[] = new int[n];      int ma[]  = new int[m];      tot1=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {     arr[i]=a+random.nextInt(b-a+1);      }        startTime = System.currentTimeMillis();        Arrays.sort(arr);        endTime = System.currentTimeMillis();        tot1=tot1+(endTime-startTime);      }      tot2=0;      for (u=0; u<10; u++)      {              for (i=0; i<n; i++)      {      arr[i]=a+random.nextInt(b-a+1);      }           startTime = System.currentTimeMillis();      for (i=0; i<m; i++) ma[i]=-999999;      for (i=0; i<n; i++)      {            x=arr[i];                    if (x >= ma[m-1])            {              ii=m-1;              jj=ii-1;              while(jj>=0 && ma[jj]<x)              {                ma[ii]=ma[jj];                ii--;                jj--;              }                ma[ii]=x;            }          }          endTime = System.currentTimeMillis();          tot2=tot2+(endTime-startTime);        }      System.out.println(n+" "+tot1+" "+tot2);   }  } }

Здесь размер массива тоже менялся от 10 тыс. до 500 тыс. элементов. Время - в миллисекундах. Результат оказался весьма похожим на питоновский (только сортировка Javа, увы, медленнее).

VBA

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

Private Declare Function GetTickCount Lib "kernel32" () As Long'::: Собственно сортировкаSub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)    If b > e Then Exit Sub    i& = b    j& = e    w& = A((i& + j&) / 2)    Do While (True)      Do While (A(i&) < w&)         i& = i& + 1      Loop      Do While (A(j&) > w&)         j& = j& - 1      Loop      If i& <= j& Then         Tmp& = A(i&)         A(i&) = A(j&)         A(j&) = Tmp&         i& = i& + 1         j& = j& - 1      End If      If i& > j& Then Exit Do    Loop        If j& > b Then QSort A, b, j&    If i& < e Then QSort A, i&, eEnd Sub'::: Проверка успешности сортировки Function check(X() As Long) As Boolean     n& = UBound(X)     For i& = 1 To n& - 1         If X(i& + 1) < X(i&) Then            Debug.Print "Err! i=" + CStr(i&)            check = False            Exit Function         End If     Next i&     check = TrueEnd Function'::: Вставка в упорядоченный массивSub ins_in_arr(X As Long, A() As Long, n As Integer)    If X < A(n) Then Exit Sub    For i% = 1 To n        If X > A(i%) Then           For j% = n To i% + 1 Step -1               A(j%) = A(j% - 1)           Next j%           A(i%) = X           Exit Sub        End If    Next i%End Sub'::: Собственно тестSub test()Const sz = 500Dim X() As LongDim Ma(1 To sz) As Long    Randomize    ooo& = 1    For n& = 10000 To 500000 Step 10000                t1# = 0        For nc% = 1 To 10                                ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            For i& = 1 To sz                Ma(i&) = -2147483647            Next i&            For i& = 1 To n&                ins_in_arr X(i&), Ma, 10            Next i&            s2& = GetTickCount            t1# = t1# + s2& - s1&                Next nc%                        Cells(ooo&, 1).Value = n&        Cells(ooo&, 2).Value = t1# / 10                        t2# = 0                For nc% = 1 To 10                    ReDim X(1 To n&) As Long            For i& = 1 To n&                X(i&) = Rnd() * 5000            Next i&            s1& = GetTickCount            QSort X, 1, n&            s2& = GetTickCount            If Not check(X) Then               MsgBox "Ошибка при сортировке!"               Exit Sub            End If            t2# = t2# + s2& - s1&        Next nc%        Cells(ooo&, 3).Value = t2# / 10        ooo& = ooo& + 1            Next n&End Sub

На каждом витке цикла корректность сортировки проверяется. Время проверки, естественно, не включается в общий хронометраж. Набор исходных данных тот же - от 10 до 500 тыс. целых чисел. Получает, в общем, похожая картина:

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

Самым невыгодным случаем будет являться, как ни странно, входной массив, уже упорядоченный по возрастанию. В этом случае количество сравнений при вставке достигнет максимума и будет равно n*m. Массив, упорядоченный по убыванию, напротив, весьма выгоден. Число сравнений здесь будет ~ m+n.

Описанный в самом начале статьи алгоритм, можно ускорить, если вместо простого упорядоченного массива использовать древовидную или пирамидальную структуру. Именно так и реализована в Питоне в модуле heapq функция nsmallest.

Для небольших массивов (несколько тысяч элементов и менее) разница в подходах представляется несущественной. И если нужно быстро написать код, то сортировка - вполне приемлемое решение. Для больших массивов выгоднее от сортировки отказаться.

Вот и все, что я хотел рассказать об этой задаче. Спасибо, что дочитали до конца. С наступившим 2021-м годом!