Задача о 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 time from 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&, e  End 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 = True End 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 = 500 Dim X() As Long Dim 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-м годом!