Форум программистов, компьютерный форум, киберфорум
Catstail
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 2.

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

Запись от Catstail размещена 06.01.2021 в 13:15

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


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

Намекну - интуиция меня в целом не подвела.

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

Итак рабочий массив заполнен одинаковыми значениями. Теперь берем элемент за элементом исходного массива и вставляем его в нужное место рабочего массива. При этом длину рабочего массива сохраняем равной m. Если очередной элемент меньше последнего значения рабочего массива, то он просто пропускается. Этот процесс имеет вычислительную сложность O(n*m).

Итак рабочий массив заполнен одинаковыми значениями. Теперь берем элемент за элементом исходного массива и вставляем его в нужное место рабочего массива. При этом длину рабочего массива сохраняем равной 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
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
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-м годом!

ссылка на статью
Миниатюры
Нажмите на изображение для увеличения
Название: 10-python.png
Просмотров: 1705
Размер:	11.7 Кб
ID:	6683   Нажмите на изображение для увеличения
Название: 10-java.png
Просмотров: 1747
Размер:	12.3 Кб
ID:	6684   Нажмите на изображение для увеличения
Название: 10-vba.png
Просмотров: 1765
Размер:	12.4 Кб
ID:	6685  

Размещено в Без категории
Просмотров 2368 Комментарии 14
Всего комментариев 14
Комментарии
  1. Старый комментарий
    Аватар для Почтальон
    А можно ссылочку на хабре ?
    Запись от Почтальон размещена 06.01.2021 в 13:17 Почтальон вне форума
  2. Старый комментарий
    Аватар для Catstail
    Она в самом конце статьи
    Запись от Catstail размещена 06.01.2021 в 14:24 Catstail вне форума
  3. Старый комментарий
    Аватар для vantfiles
    мне это напомнило один интересный алгоритм нахождения скользящего среднего. Как ни странно, для его реализации требуется не массив из N усредняемых значений, а всего лишь две переменные.
    Запись от vantfiles размещена 07.01.2021 в 12:47 vantfiles вне форума
  4. Старый комментарий
    Аватар для Curry
    Catstail, вот бы ещё посмотреть вариант на haskell, на списках.

    Цитата:
    Сообщение от vantfiles Просмотреть комментарий
    мне это напомнило один интересный алгоритм нахождения скользящего среднего. Как ни странно, для его реализации требуется не массив из N усредняемых значений, а всего лишь две переменные.
    Цифровой рекурсивный ФНЧ первого порядка. Переменные: текущее и предыдущее выходное значения.
    Запись от Curry размещена 07.01.2021 в 13:10 Curry вне форума
    Обновил(-а) Curry 07.01.2021 в 13:35
  5. Старый комментарий
    Уважаемый Catstail,
    задача конечно интересная, но она решается вами в предположении, что если массив содержит более m равных максимальных элементов, то они не различаются друг от друга. Иными словами, если все элементы массива равны, то какие m элементов следует выбирать?

    примечание
    прошу меня извинить, как математик я не могу пройти мимо некорректно заданной задачи.
    Запись от wer1 размещена 09.01.2021 в 13:37 wer1 вне форума
  6. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от wer1 Просмотреть комментарий
    Уважаемый Catstail,
    прошу меня извинить, как математик я не могу пройти мимо некорректно заданной задачи.
    - если все элементы массива одинаковы, то мои реализации и выдадут m одинаковых значений. Тривиальный и, по-моему, не интересный случай. Главный "пафос" заметки - борьба с тупым использованием стандартных методов.
    Запись от Catstail размещена 10.01.2021 в 19:53 Catstail вне форума
    Обновил(-а) Catstail 25.01.2021 в 17:41
  7. Старый комментарий
    Аватар для vantfiles
    Цитата:
    Цифровой рекурсивный ФНЧ первого порядка. Переменные: текущее и предыдущее выходное значения.
    Это не N последних значений.
    Запись от vantfiles размещена 11.01.2021 в 15:21 vantfiles вне форума
  8. Старый комментарий
    Аватар для Curry
    Цитата:
    Это не N последних значений.
    Нет. Скользящие средние разные бывают. То что вы имеете ввиду называется простое скользящее среднее, и я не знаю как его пересчитывать, при поступлении очередного отсчёта, имея только две переменные.
    Покажите, пожалуйста. На любом языке возникшем после 60-ых. )
    Запись от Curry размещена 11.01.2021 в 15:45 Curry вне форума
  9. Старый комментарий
    Уважаемый Curry,
    что вы имеете в виду говоря о скользящем среднем? Это случайно не вычисление медианы? Её тоже можно вычислить сортировкой массива. Но об использовании двух переменных я не слыхал.
    Запись от wer1 размещена 12.01.2021 в 09:15 wer1 вне форума
  10. Старый комментарий
    Аватар для Curry
    Цитата:
    что вы имеете в виду говоря о скользящем среднем?
    https://ru.wikipedia.org/wiki/... 1%8F%D1%8F

    Допустим, что то периодически замеряется (ток, напряжение, или стоимость акции, не важно). В обсуждаемую функцию поступает новое замеренное значение и предыдущее состояние. Функция возвращает изменённое состояние для использования в последующем и выходное значение. Если в терминах ООП, то состояние в объекте, а мы обращаемся к методу, передаём очередное значение и получаем выходное, при этом меняя состояние объекта. Обрабатывать последующие значения мы не можем - их просто ещё не существует.
    И, вот, как в таких условиях, сделать так, чтобы на выходе выдавалось каждый раз среднее значение последних N отсчётов?
    Сохраняя последние N отчётов в состоянии (объекта), это сделать тривиально. А как это сделать имея состояние из двух переменных (очевидно, не массивов), не знаю.
    Запись от Curry размещена 12.01.2021 в 17:38 Curry вне форума
  11. Старый комментарий
    Уважаемый 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
  12. Старый комментарий
    Аватар для K_ILYA_V
    Цитата:
    Сообщение от 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 вне форума
  13. Старый комментарий
    Цитата:
    Сообщение от K_ILYA_V Просмотреть комментарий
    но можно упростить задание и добиться подобия результата с некой трудно измеряемой погрешностью, добавив третье число (константу)
    Угу. Я тоже так думаю. Если к примеру все значения массива ограничены сверху и снизу, то погрешность будет равна среднему арифметическому этих крайних значений. Если и далее новые значения не будут выходить за вычисленные нами границы, то действительно новое значение среднего арифметического можно вычислить вычтя из общей суммы всех элементов старое среднее арифметическое и добавив новое слагаемое. А потом разделив на общее число элеменов (ведь оно осталось неизменным). А погрешность тоже вещь постоянная, будучи вычисленная один раз, она не изменится до тех пор, пока новый элемент не выйдет за заданные границы.
    Запись от wer1 размещена 21.01.2021 в 10:09 wer1 вне форума
  14. Старый комментарий
    Аватар для K_ILYA_V
    Ваша задача может быть решена посредством 13 ассемблерных инструкций, вот код который решает вашу задачу за минимально возможное время.

    Assembler
    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    
    .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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.