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

Запись от Catstail размещена 06.01.2021 в 13:15
Обновил(-а) Catstail 28.12.2022 в 08:06

Выкладываю мою статью на хабре "Задача о m максимумах". Ее там заминусовали, но, возможно, она кому-то покажется интересной...

Старая-старая школьно-студенческая задача... Дан массив целых чисел. Требуется найти m его максимальных (или минимальных) элементов. Когда я задаю эту задачу учащимся, то почти в каждой группе находятся "умельцы", решающие ее с помощью сортировки. В самом деле, это ведь так просто: сортируем массив по убыванию (вручную или подходящей библиотечной функцией) и просто берем m первых элементов. Конечно, иначе как алгоритмическим варварством такой подход не назовешь - найти 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.

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

Python

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=n+10000
    
start()

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

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

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

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;
    m=10;
    
    System.out.println(a+" "+b+" "+m);
    
    for (n=10000; n<=500000; n+=10000)
    {
    
        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а, увы, медленнее; Правда JDK в моих тестах - 8-й версии, а Питон - 3.7).

VBA

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

Visual Basic

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-м годом!

ссылка на статью

Размещено в Без категории

Показов 15669 Комментарии 53

« Цена естественности или как обогнать QuickSort Главная страница Мемоизация в Лиспе »

Всего комментариев 53

Комментарии

1 из 3

	А можно ссылочку на хабре ?
	Запись от Почтальон размещена 06.01.2021 в 13:17

	Она в самом конце статьи
	Запись от Catstail размещена 06.01.2021 в 14:24

	мне это напомнило один интересный алгоритм нахождения скользящего среднего. Как ни странно, для его реализации требуется не массив из N усредняемых значений, а всего лишь две переменные.
	Запись от vantfiles размещена 07.01.2021 в 12:47

Catstail, вот бы ещё посмотреть вариант на haskell, на списках.

Цитата:

Сообщение от vantfiles

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

Цифровой рекурсивный ФНЧ первого порядка. Переменные: текущее и предыдущее выходное значения.

Запись от Curry размещена 07.01.2021 в 13:10 Curry вне форума

Обновил(-а) Curry 07.01.2021 в 13:35

Уважаемый Catstail,
задача конечно интересная, но она решается вами в предположении, что если массив содержит более m равных максимальных элементов, то они не различаются друг от друга. Иными словами, если все элементы массива равны, то какие m элементов следует выбирать?

примечание
прошу меня извинить, как математик я не могу пройти мимо некорректно заданной задачи.

Запись от wer1 размещена 09.01.2021 в 13:37 wer1 вне форума

Цитата:

Сообщение от wer1

Уважаемый Catstail,
прошу меня извинить, как математик я не могу пройти мимо некорректно заданной задачи.

- если все элементы массива одинаковы, то мои реализации и выдадут m одинаковых значений. Тривиальный и, по-моему, не интересный случай. Главный "пафос" заметки - борьба с тупым использованием стандартных методов.

Запись от Catstail размещена 10.01.2021 в 19:53 Catstail вне форума

Обновил(-а) Catstail 25.01.2021 в 17:41

	Цитата: Цифровой рекурсивный ФНЧ первого порядка. Переменные: текущее и предыдущее выходное значения. Это не N последних значений.
	Запись от vantfiles размещена 11.01.2021 в 15:21

Цитата:

Это не N последних значений.

Нет. Скользящие средние разные бывают. То что вы имеете ввиду называется простое скользящее среднее, и я не знаю как его пересчитывать, при поступлении очередного отсчёта, имея только две переменные.
Покажите, пожалуйста. На любом языке возникшем после 60-ых. )

Запись от Curry размещена 11.01.2021 в 15:45 Curry вне форума

	Уважаемый Curry, что вы имеете в виду говоря о скользящем среднем? Это случайно не вычисление медианы? Её тоже можно вычислить сортировкой массива. Но об использовании двух переменных я не слыхал.
	Запись от wer1 размещена 12.01.2021 в 09:15

Цитата:

что вы имеете в виду говоря о скользящем среднем?

https://ru.wikipedia.org/wiki/... 1%8F%D1%8F

Допустим, что то периодически замеряется (ток, напряжение, или стоимость акции, не важно). В обсуждаемую функцию поступает новое замеренное значение и предыдущее состояние. Функция возвращает изменённое состояние для использования в последующем и выходное значение. Если в терминах ООП, то состояние в объекте, а мы обращаемся к методу, передаём очередное значение и получаем выходное, при этом меняя состояние объекта. Обрабатывать последующие значения мы не можем - их просто ещё не существует.
И, вот, как в таких условиях, сделать так, чтобы на выходе выдавалось каждый раз среднее значение последних N отсчётов?
Сохраняя последние N отчётов в состоянии (объекта), это сделать тривиально. А как это сделать имея состояние из двух переменных (очевидно, не массивов), не знаю.

Запись от Curry размещена 12.01.2021 в 17:38 Curry вне форума

Уважаемый Curry,
предложенная вами задача неразрешима. Дело в том, чтобы вычислять каждый раз новое среднее значение из N чисел, необходимо удалить одно самое старое (самое первое) значение. И потом производить вычисления с новым числом. А это означает, что вам придётся всё время хранить массив из N чисел (который будет меняться естественно)

Если бы среднее значение вычислялось по всем числам, то да можно обойтись всего двумя переменными.
Вот как к примеру вычисляется среднее арифметическое. Пусть SA - среднее арифметическое от N элементов
и пусть А - новый (N + 1)-ый элемент. Новое значение среднего арифметического будет таким
SA = (SA * N + A) / (N + 1)

Стоит отметить, что некоторые простые попытки поместить несколько чисел в одну переменную всё-же имели успех.
1. например два целых числа A и B можно записать как дробное A,B (100 и 55 => 100,55)
2. цифры также можно записать в виде одного длинного целого числа
3. двузначные числа можно записать парами в одно число

Запись от wer1 размещена 13.01.2021 в 09:30 wer1 вне форума

Обновил(-а) wer1 13.01.2021 в 09:31

Цитата:

Сообщение от Curry

...А как это сделать имея состояние из двух переменных (очевидно, не массивов), не знаю.

при таких условиях задача не имеет решения.

но можно упростить задание и добиться подобия результата с некой трудно измеряемой погрешностью, добавив третье число (константу) которая будет содержать в себе количество измерений N

пусть сумма ранее измеренных значений определяется по формуле:
M = m1 + m2 + ... + m(n-1) + mn

тогда новое средние, при поступление нового значения m(n+1) определяется по формуле:
M1 = M0 - M0 / N + m(n+1)

Запись от K_ILYA_V размещена 21.01.2021 в 00:10 K_ILYA_V вне форума

Цитата:

Сообщение от K_ILYA_V

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

Угу. Я тоже так думаю. Если к примеру все значения массива ограничены сверху и снизу, то погрешность будет равна среднему арифметическому этих крайних значений. Если и далее новые значения не будут выходить за вычисленные нами границы, то действительно новое значение среднего арифметического можно вычислить вычтя из общей суммы всех элементов старое среднее арифметическое и добавив новое слагаемое. А потом разделив на общее число элеменов (ведь оно осталось неизменным). А погрешность тоже вещь постоянная, будучи вычисленная один раз, она не изменится до тех пор, пока новый элемент не выйдет за заданные границы.

Запись от wer1 размещена 21.01.2021 в 10:09 wer1 вне форума

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

Assembler

.686
.model flat, stdcall
option casemap :none
 
.data
indata  dd  1,2,3,4,5,6,7,8, \
            1,2,3,4,5,6,7,8, \
            1,2,3,4,5,6,7,8, \
            1,2,3,4,5,6,7,8, \
            1,2,3,4,5,6,7,8, \
            1,2,3,4,5,6,7,8
sizedt  dd  (sizedt - indata) / dword
N = 30h
maxN    dd  N
outdata dd  N dup (0)
 
.code
start:
; симуляция вызова процедуры
    push    offset indata           ; 8
    push    sizedt                  ; 7
    push    maxN                    ; 6
    push    offset outdata          ; 5
    call    not_sort                ; 4
    ret     10h
    
; инициализация процедуры
not_sort:
    push    esi                     ; 3
    push    edi                     ; 2
    push    ebp                     ; 1
    push    ebx                     ; 0
    
    mov     edi,[esp + dword * 5]
    mov     ecx,[esp + dword * 6]
    mov     ebp,[esp + dword * 7]
    mov     esi,[esp + dword * 8]
        
    xor     eax, eax
    rep stosd
    mov     ecx,[esp + dword * 6]
    mov     edi,[esp + dword * 5]
 
; решение поставленной задачи
next:
    lodsd
    
@@: 
    cmp     eax,[edi]
    cmovnb  edx,[edi]
    cmovb   eax,[edi]
    stosd
    cmovb   edx,[esi - dword]
    mov     eax, edx
    dec     ecx
    jnz @b
    
    mov     ecx,[esp + dword * 6]
    mov     edi,[esp + dword * 5]
    dec     ebp
    jnz next
    
; завершение процедуры
    pop     ebx
    pop     ebp
    pop     edi
    pop     esi
    ret 
end start

Этот код прямой как рельса, не имеет ветвлений и несомненно самый быстрый из предложенных.

Запись от K_ILYA_V размещена 21.01.2021 в 23:23 K_ILYA_V вне форума

Обновил(-а) K_ILYA_V 21.01.2021 в 23:31

Цитата:

Сообщение от K_ILYA_V

...
Этот код прямой как рельса, не имеет ветвлений и несомненно самый быстрый из предложенных.
...

О, да! А jnz @b и jnz next - это, как я понимаю - комментарий? И какое отношение все это имеет к теме заметки (что быстрее - сортировать или вставлять в отсортированный массив)? А если нужно было бы сортировать записи по сложным ключам, вам бы тоже хватило 13 команд?

Запись от Catstail размещена 09.04.2021 в 15:15 Catstail вне форума

Цитата:

Сообщение от Catstail

.. А если нужно было бы сортировать записи по сложным ключам, вам бы тоже хватило 13 команд?

если бы мне нужно было бы сортировать по сложным ключам я бы придумал как сортировать по сложным ключам с минимальным количеством команд.

предлагайте условия.

Запись от K_ILYA_V размещена 09.04.2021 в 17:01 K_ILYA_V вне форума

Обновил(-а) K_ILYA_V 09.04.2021 в 17:13

	Цитата: Сообщение от K_ILYA_V Ваша задача может быть решена посредством 13 ассемблерных инструкций Вы не включили в эти 13 инструкций инициализации регистров и предварительное обнуление области результата.
	Запись от Curry размещена 09.04.2021 в 17:16 Обновил(-а) Curry 09.04.2021 в 17:20

	Цитата: Сообщение от K_ILYA_V предлагайте условия. Перепишите эту программу так что бы работала на всех микроконтроллерах фирмы microchip, например.
	Запись от Curry размещена 09.04.2021 в 17:18

Цитата:

Сообщение от Curry

Вы не включили в эти 13 инструкций инициализации регистров и обнуления области результата.

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

Запись от K_ILYA_V размещена 09.04.2021 в 17:20 K_ILYA_V вне форума

	Цитата: Сообщение от Curry Перепишите эту программу так что бы работала на всех микроконтроллерах фирмы microchip, например. сколько платите?
	Запись от K_ILYA_V размещена 09.04.2021 в 17:26 Обновил(-а) K_ILYA_V 09.04.2021 в 17:28

1 из 3

Сообщение форума

Отменить изменения

Архив
< Ноябрь 2024
Вс	Пн	Вт	Ср	Чт	Пт	Сб
20	21	22	23	24	25	26
27	28	29	30	31	1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30