Форум программистов, компьютерный форум, киберфорум
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
Просмотров: 1794
Размер:	11.7 Кб
ID:	6683   Нажмите на изображение для увеличения
Название: 10-java.png
Просмотров: 1819
Размер:	12.3 Кб
ID:	6684   Нажмите на изображение для увеличения
Название: 10-vba.png
Просмотров: 1833
Размер:	12.4 Кб
ID:	6685  

Размещено в Без категории
Показов 13671 Комментарии 52
Всего комментариев 52
Комментарии
  1. Старый комментарий
    Аватар для K_ILYA_V
    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...что изменение в системе команд ассемблера способно изменить фундаментальные математические факты...
    вы путаете теплое с мягким. изменение набора команд позволяют применять новые алгоритмы подчиняющиеся другим математическим закономерностям, хотя в случае моего кода он уже имеет сложность равную O(n)=n*m
    и следовательно добиться ускорения путем уменьшения сложности уже не представляется возможным.

    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...нужно принять решение, что перестановка нужна. А это - ветвление (пусть и реализованное микропрограммно)...
    основное преимущество команды CMOVcc в том что она выполняет либо не выполняет действие по перемещению элемента в зависимости от флага. такое действие никак не затрагивают предсказатель переходов и не могут обрушить вычислительный конвейер. CMOVcc не является ветвлением ни по сути ни по духу.

    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...Что же до анонимных меток...
    то это дурное влияние догматов отечественного образования в частности "я начальник преподаватель ты дурак студент."

    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...Даже дискутируя с таким, как вы, можно чему-то научиться....
    гордыня

    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...Если говорить совсем грубо, то то, что вы написали, выглядит так:...
    я написал минималистический код не скованный ни какими парадигмами программирования.
    если бы скайнет существовал он был бы написан таким кодом. (гордыня)

    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    ...И самое главное, какое отношение имеет ваш код к главному вопросу: что быстрее полная сортировка или вставка в упорядоченный (задача про m максимумов)?
    доказательство того что трава зеленая а вода мокрая любимый преподавательский прием, риска ощибится никакого зато выглядит очень умно и красиво.

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



    а вообще я считаю что статья интересная и заминусили ее на хабре те студенты которые такую проблему сортировкой решают они как увидели чтото сложней библиотечной функции так у них вспыхнула лютая ненависть к тем страданиям которые они пережили будучи студентами.
    Запись от K_ILYA_V размещена 12.04.2021 в 22:40 K_ILYA_V вне форума
    Обновил(-а) K_ILYA_V 12.04.2021 в 22:45
  2. Старый комментарий
    Аватар для Catstail
    "я написал минималистический код не скованный ни какими парадигмами программирования.
    если бы скайнет существовал он был бы написан таким кодом. (гордыня)" - да я давно это понял... Гордыня есть у всех, но у вас ее размер несколько превышает установленные стандарты.

    Что же до анонимных меток, то это связано с тем, что на ассемблере я писал действительно давно. Но ассемблер любил. И даже сделал самодельный ассемблер, 16-битный, естественно. (На странице - 7-я сверху). Кстати, и вы с анонимными метками познакомились не так давно - еще в прошлом году задавали здесь на форуме вопросы, нет?

    А вот концепция "я начальник ты дурак" мне совершенно не свойственна, это вы зря.

    Если угодно, я давно делю знания и навыки на два класса: концептуальные и конкретные.

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

    Пример концептуального знания - алгоритмы сортировки, графовые алгоритмы, структуры данных и т.п. Они не обесцениваются совсем (во всяком случае на протяжении жизни).

    Поэтому я не стесняюсь, что не знаю какой-то конкретики (а кто знает ВСЁ, может, вы?)

    И - неожиданно - спасибо за оценку статьи. Но думаю, что заминусовали ее не студенты, а люди т.н. клипового мышления. Они не вникают в содержание, а реагируют на ключевые слова. В комментах я пытался "свернуть к теме", но они упорно продолжали писать свое, типа: "да не надо вставлять в массив, надо использовать кучу" и т.п. Хотя этот тезис не опровергает, а подтверждает основной посыл статьи - для получения нескольких максимумов не надо сортировать все!
    Запись от Catstail размещена 13.04.2021 в 06:46 Catstail вне форума
    Обновил(-а) Catstail 14.04.2021 в 06:46
  3. Старый комментарий
    Аватар для Curry
    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    Гордыня есть у всех, но у вас ее размер несколько превышает установленные стандарты.
    Враньё у него превышает всякие нормы. Кроме того что он соврал про отсутствие переходов в программе и кол-во команд, у него алгоритм просто более медленный чем у вас, и, даже нерабочий.
    Вы вставляете в выходной массив только когда надо и в нужную позицию упорядоченного массива.
    Он, для каждого элемента исходного массива проходит по всему выходному заменяя там элементы меньше текущего.
    Это и медленнее, и не точно, т.к если, допустим, во входном массиве только одна 9-ка, а остальные элементы меньше, то на выходе будут все 9-ки, которых во входном нет.
    Запись от Curry размещена 13.04.2021 в 08:42 Curry вне форума
  4. Старый комментарий
    Аватар для K_ILYA_V
    Цитата:
    Сообщение от Curry Просмотреть комментарий
    ...
    Они слепые вожди слепых; а если слепой ведёт слепого, то они оба упадут в яму.
    Запись от K_ILYA_V размещена 13.04.2021 в 23:02 K_ILYA_V вне форума
  5. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от Curry Просмотреть комментарий
    Он, для каждого элемента исходного массива проходит по всему выходному заменяя там элементы меньше текущего. Это и медленнее, и не точно, т.к если, допустим, во входном массиве только одна 9-ка, а остальные элементы меньше, то на выходе будут все 9-ки, которых во входном нет.
    - да, свои ошибки надо уметь признавать. Я же наблюдаю у товарища явно повышенное желание "наскочить".
    Запись от Catstail размещена 14.04.2021 в 06:37 Catstail вне форума
  6. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от K_ILYA_V Просмотреть комментарий
    Они слепые вожди слепых; а если слепой ведёт слепого, то они оба упадут в яму.
    - цитаты положено заключать в кавычки... Могу порекомендовать хороший рассказ В.Шукшина; мне кажется, что он - в тему.
    Запись от Catstail размещена 14.04.2021 в 06:44 Catstail вне форума
    Обновил(-а) Catstail 14.04.2021 в 06:45
  7. Старый комментарий
    Аватар для K_ILYA_V
    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    - да, свои ошибки надо уметь признавать. Я же наблюдаю у товарища явно повышенное желание "наскочить".
    Опишите ошибку более точно, пожалуйста. Потому что на данный момент я склонен считать что вы просто не можете разобраться в коде и как следствие пытаетесь вменить мне несуществующие ошибки вами же и придуманные.

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

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

    За что кукушка хвалит петуха, за то что хвалит он кукушку.
    Запись от K_ILYA_V размещена 14.04.2021 в 11:25 K_ILYA_V вне форума
  8. Старый комментарий
    Цитата:
    Сообщение от Catstail Просмотреть комментарий
    концептуальные и конкретные.
    Ну вы же стали стали проверять свою концепцию на конкретике, зная, что ас. сложность имеет опосредованное отношение к производительности. Не понимаю, почему тогда претензии к ассемблерному коду, который на конкретике показывает, что можно сделать вашу задачу быстрее.

    Мне, например, не нравится, что на Java вы тесты делали не через JMH и наименование ваших переменных (ii, jj), но это все придирки, не меняющие картину в целом. Также и у вас придирки к ассемблерному коду лежат в том же классе эквивалентности.

    К тому же в вашей преамбуле к задаче не совсем понятна отсылка к "умельцам-студентам", которые, обожемой, сделали задачу через сортировку, чем, видимо, заслужили не зачет. Если нужно решать задачу за отведенное асимптотическое время, то так и нужно об этом писать. И правда, немного жаль ваших студентов, хотя тему вы затрагивали интересную, на мой взгляд.
    Запись от Tavashi размещена 18.04.2021 в 14:46 Tavashi вне форума
  9. Старый комментарий
    Цитата:
    Сообщение от Tavashi Просмотреть комментарий
    Если нужно решать задачу за отведенное асимптотическое время, то так и нужно об этом писать. И правда, немного жаль ваших студентов, хотя тему вы затрагивали интересную, на мой взгляд.
    Вы невнимательно прочитали запись ТС. Он не ставил перед собой задач, которые ему пытаются здесь приписать. ТС просто поделился с нами своими мыслями и решением одной интересной ему (и не только ему) задачи.
    Запись от wer1 размещена 19.04.2021 в 07:40 wer1 вне форума
  10. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от Tavashi Просмотреть комментарий
    Если нужно решать задачу за отведенное асимптотическое время, то так и нужно об этом писать. И правда, немного жаль ваших студентов, хотя тему вы затрагивали интересную, на мой взгляд.
    Нет, так не нужно писать! Любую задачу нужно стараться решить максимально рационально. Это, по-моему, предполагается по умолчанию. Всегда. Вот обратное (если нужно хоть какое-то решение) - да, стоит обговорить. А Ваше предложение приучает к тому, что программисту все нужно "разжевать и в рот положить". Вам не кажется, что опуская планку, Вы тем самым сводите программистов к тупым кодерам?

    Я учился в физматшколе... У нас можно было за контрольную, в которой все примеры решены верно, получить трояк и подпись
    "верно, но нерационально". Это правильный подход. Поэтому не стоит жалеть моих студентов. По крайней мере по двум причинам:

    - жизнь еще их "приложит". И не раз;
    - начальники не любят исполнителей, которым все нужно разжевывать и тех, кто не любит думать сам и боится ответственности.
    От таких обычно освобождаются в первую очередь. Поэтому привычку думать самому лучше выработать с "младых ногтей".

    Ну, и под занавес: цитата из классика (В.Войнович "Жизнь и необычайные приключения солдата Ивана Чонкина"):


    "... -- Теперь допонял.-- Голос Борисова иронически завибрировал.-- А ты,
    если по малой нужде идешь, ширинку сам расстегиваешь или указания дожидаешь? "
    Запись от Catstail размещена 01.05.2021 в 11:39 Catstail вне форума
  11. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от Tavashi Просмотреть комментарий
    Также и у вас придирки к ассемблерному коду лежат в том же классе эквивалентности.
    Никаких придирок к ассемблерному коду у меня нет. Есть претензия к тому, кто его привел - он писал, что код линейный.
    Линейный (по его словам "прямой как рельс") код к сортировке не способен. А вот еще один участник дискуссии (Curry)
    нашел в этом коде алгоритмические ошибки. Пусть они останутся на совести автора этого кода.

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

    Я вообще замечаю, что люди стремительно разучились читать, и привыкли реагировать на ключевые слова. Это называется "клиповое мышление".

    Задаю вопрос: "что быстрее - сортировать или вставлять в упорядоченный массив минимальных размеров". Получаю ответы:

    - не надо вставлять в упорядоченный, надо использовать кучу (это самое умное, что написали на хабре)
    - на ассемблере еще быстрее (очень в тему).
    Запись от Catstail размещена 01.05.2021 в 11:53 Catstail вне форума
  12. Старый комментарий
    Аватар для Catstail
    Цитата:
    Сообщение от K_ILYA_V Просмотреть комментарий
    Опишите ошибку более точно, пожалуйста.
    - вы не поняли основной посыл заметки (что быстрее - сортировать полностью или вставлять в упорядоченный массив). Если бы поняли, то привели бы два кода на ассемблере - полная сортировка и вставка.
    Запись от Catstail размещена 01.05.2021 в 11:59 Catstail вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.