Найти минимум в массиве используя наиболее оптимальный алгоритм

@_Ivana · Регистрация: 01.03.2013

Студворк — интернет-сервис помощи студентам

Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически.

IGPIGP · 07.08.2016, 03:25

HenryDukart, жаль днём никак не получается. Но хорошая новость в том, что находясь уже почти в нехорошем месте, мне удалось несколько продвинуться вперёд. Сравни:

C++
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
150
151
152
153
#include <iostream>
using namespace std;
 
size_t comparison_count(0);
template<typename T>
void biselectional_sort_henry(T ar[], size_t len)
{
    comparison_count = 0;
 
    size_t  left_ind = 0, right_ind = len - 1,
            max_val_ind, min_val_ind;
    T temp_val;
    comparison_count++;//это тоже сравнение
    bool is_even = (len % 2 == 1 ? false : true);   //четная ли длина массива
 
    if (len <= 1)
        return;
 
    do
    {
        comparison_count++;//и это
        if (!is_even)
            min_val_ind = max_val_ind = left_ind;
        else
        {
            ++comparison_count;
            if (ar[left_ind] < ar[left_ind + 1])
            {
                min_val_ind = left_ind;
                max_val_ind = left_ind + 1;
            }
            else
            {
                min_val_ind = left_ind + 1;
                max_val_ind = left_ind;
            }
        }
 
        for (size_t i = left_ind + 1 + is_even; i < right_ind; i += 2)
        {
            ++comparison_count;
            if (ar[i] > ar[i + 1])
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i])
                    max_val_ind = i;
 
                ++comparison_count;
                if (ar[min_val_ind] > ar[i + 1])
                    min_val_ind = i + 1;
            }
            else
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i + 1])
                    max_val_ind = i + 1;
                
                ++comparison_count;
                if (ar[min_val_ind] > ar[i])
                    min_val_ind = i;
            }
        }
 ++comparison_count;
        if (max_val_ind == left_ind)
            max_val_ind = min_val_ind;
 
        temp_val = ar[left_ind];
        ar[left_ind++] = ar[min_val_ind];
        ar[min_val_ind] = temp_val;
 
 
        temp_val = ar[right_ind];
        ar[right_ind--] = ar[max_val_ind];
        ar[max_val_ind] = temp_val;
 
    } while (left_ind < right_ind);
}
 
template<typename T>
void biselectional_sort(T* ar, size_t len)
{
    int left_ind = 0, right_ind = len - 1;
    int  min_val_ind=left_ind, max_val_ind=right_ind;
    comparison_count = 0;
 
    T temp_int;
 
    if (len>1)
        do
        {
max_val_ind=right_ind;
min_val_ind=left_ind;  
comparison_count++;
            if(ar[max_val_ind]<ar[min_val_ind])
            {
            temp_int = ar[max_val_ind];
            ar[max_val_ind] = ar[min_val_ind];
            ar[min_val_ind] = temp_int;   
            }
            
            for (int i = left_ind + 1; i < right_ind; ++i)
            {
                comparison_count++;
                if (ar[max_val_ind]<ar[i])
                {
                    max_val_ind = i;                   
                }
                else
                comparison_count++;
                if (ar[min_val_ind]>ar[i])
                {   
                    min_val_ind = i;                    
                }
            } 
            temp_int = ar[left_ind];
            ar[left_ind++] = ar[min_val_ind];
            ar[min_val_ind] = temp_int;
 
            temp_int = ar[right_ind];
            ar[right_ind--] = ar[max_val_ind];
            ar[max_val_ind] = temp_int;
        } while (left_ind<right_ind);//
}
 
int main(int argc, char* argv[])
{
    int ar[] =      
    {
        //1,0,2,3,4,5,6//,0
        //5,4,3,2,1,0
      // 0,0//,
      2, 1,1,1,2,3,3,2, 5, 3, 7, 4, 8, 11, 90, 9,1
    };
    int ar_copy[] =
    {
        //1,0,2,3,4,5,6//,0
        //5,4,3,2,1,0
       //0,0//,
      2, 1,1,1,2,3,3,2, 5, 3, 7, 4, 8, 11, 90, 9,1
    };
    size_t len = sizeof(ar) / sizeof(ar[0]);
     biselectional_sort_henry(ar, len);
    cout << "The array with size of " << len << " was sorted with " << comparison_count << " comparisons\n";
    for (size_t i = 0; i<len; ++i)cout << ar[i] << " ";
    cout << endl;
 
    biselectional_sort(ar_copy, len);
    cout << "The array with size of " << len << " was sorted with " << comparison_count << " comparisons\n";
    for (size_t i = 0; i<len; ++i)cout << ar_copy[i] << " ";
    cout << endl;
    system("pause"); 
    return 0;
}

Сдавайся!

ValeryS · 07.08.2016, 08:21

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

bool is_even = (len % 2 == 1 ? false : true); * //четная ли длина массива

вот здесь есть маленькая засада
стоит поменять %на & и будет работать неправильно

Да и всю конструкцию можно упростить

C
1
bool is_even = !(len &1);

не будет ветвления

Добавлено через 4 минуты
ну или вот так

C++
1
bool is_even = !(len % 2 == 1 );

@_Ivana · 07.08.2016, 08:38 **[ТС]**

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

ну или вот так
bool is_even = !(len % 2 == 1 );

А что так жестко то?

ValeryS · 07.08.2016, 09:01

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

А что так жестко то?

нук

шоб понятней было

а так можно и

C
1
bool is_even = !(len % 2);

они все приведут к одному результату

C
1
2
3
4
5
6
bool is_even = !(len &1); 
bool is_even = !((len &1)==1); 
bool is_even = !(len % 2);
bool is_even = !(len % 2 == 1 );
bool is_even = len % 2 == 0 ;
bool is_even = (len &1)==0;

как говаривал В.В. Маяковский "Выбирай на вкус"

IGPIGP · 07.08.2016, 09:52

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

не будет ветвления

ValeryS, твоя правда, - спасибо)
Эта функция в заготовке написана мной (и очень глючно), а данная редакция принадлежит HenryDukart. Он написал классно. Всё работает, причём, гораздо быстрее чем та, что он принял как исходную. Так что твоё замечание к нам обоим.
Скажи, а твоё изменение скажется на исполняемом коде?
И ещё вопрос. Вот такая конструкция будет считаться сравнением (для наивного учёта производительности подсчётом количества сравнений) :

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

C++
1
bool is_even = !(len % 2 == 1 );

Байт · 07.08.2016, 09:52

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

А как это реализовать программно?

Я вот вижу симпатичную реализацию с помощью классов QGraphicsScene, QGraphicsItem.
Но это вовсе не значит, что я собираюсь это реализовывать.

ValeryS · 07.08.2016, 10:05

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

Скажи, а твоё изменение скажется на исполняемом коде?

а кто его знает

если оптимизатор у компилятора умный,то сам это сделает

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

Вот такая конструкция будет считаться сравнением

сравнение будет, а вот ветвления нет

сравнение выполняться за один такт
самое страшное это ветвление
представь едешь на машине,разогнался, и тут тебе говорят "Стоп! Поворачивай направо(налево)", приходится тормозить
поворачивать и опять разгонятся
То же и с процессором
но как я уже писал в 102 посте, у современных процессоров (начиная с P6) есть команды условного исполнения
инструкция CMOV (http://www.rcollins.org/p6/opcodes/CMOV.html)
т.е если условие "истина" то исполняется, если "ложь" то пропускается( вместо нее исполняется команда nop)

IGPIGP · 07.08.2016, 10:20

Сообщение от Байт

Я вот вижу симпатичную реализацию с помощью классов QGraphicsScene, QGraphicsItem.

Да! На сцене, под действием минимум трёх динамических источников света, стоит комп за которым сидит кодер. Кодер пишет реализацию. Тут всего делов, -: AI программера, а комп и рендеринг уже где-то реализованы. Библиотеки это наше всё.
Шутки шутками, но в технике срисовывание паттернов внешнего мира называется БИОНИКА. Существует множество технических решений, дублирующих механизмы внешнего мира (созданные без человека). Тот жанр, который мы тут создали (если он не создан ещё), можно назвать infonica. Хотя по факту оно уже есть. Известно например, что один сообразительный древний человек, увидев дикорастущие здание и мост сразу решил назвать соответствующие паттерны проектирования, соответствующими названиями, - фасад и мост. Есть мнение, что их было аж четыре чувака.

Так что Ваша идея с арбузами, Байт, плодотворна. Интересная идея не бывает пустой. Бывает дефицит воображения у того, кто её оценивает. Это не оффтоп, а к теме о темах. То есть, про башмак, небесные тела и тех кто их наблюдает.

Добавлено через 6 минут

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

самое страшное это ветвление

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

,

@HenryDukart · 07.08.2016, 11:44

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

C++
1
2
3
4
5
6
7
8
9
10
11
comparison_count++; 
if (ar[max_val_ind]<ar[i]) 
{ 
max_val_ind = i; 
} 
else 
comparison_count++; 
if (ar[min_val_ind]>ar[i]) 
{ 
min_val_ind = i; 
}

Вот это вы явно в 3 часа ночи писали.

Добавлено через 6 минут
IGPIGP, раз вы так

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

C++
1
2
comparison_count++;//и это 
if (!is_even)

то я так:

C++
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include <iostream>
using namespace std;
 
size_t comparison_count(0);
 
 
template<typename T>
void biselectional_sort_henry(T ar[], size_t len)
{
    if (len <= 1)
        return;
 
    comparison_count = 0;
    comparison_count++;                         //это тоже сравнение
    if ((len & 1) == 1)
        biselectional_sort_odd(ar, len);
    else
        biselectional_sort_even(ar, len);
}
 
template<typename T>
void biselectional_sort_even(T ar[], size_t len)
{
    size_t  left_ind = 0, right_ind = len - 1,
        max_val_ind, min_val_ind;
    T temp_val;
 
 
    do
    {
        ++comparison_count;
        if (ar[left_ind] < ar[left_ind + 1])
        {
            min_val_ind = left_ind;
            max_val_ind = left_ind + 1;
        }
        else
        {
            min_val_ind = left_ind + 1;
            max_val_ind = left_ind;
        }
 
        for (size_t i = left_ind + 2; i < right_ind; i += 2)
        {
            ++comparison_count;
            if (ar[i] > ar[i + 1])
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i])
                    max_val_ind = i;
 
                ++comparison_count;
                if (ar[min_val_ind] > ar[i + 1])
                    min_val_ind = i + 1;
            }
            else
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i + 1])
                    max_val_ind = i + 1;
 
                ++comparison_count;
                if (ar[min_val_ind] > ar[i])
                    min_val_ind = i;
            }
        }
        ++comparison_count;
        if (max_val_ind == left_ind)
            max_val_ind = min_val_ind;
 
        temp_val = ar[left_ind];
        ar[left_ind++] = ar[min_val_ind];
        ar[min_val_ind] = temp_val;
 
 
        temp_val = ar[right_ind];
        ar[right_ind--] = ar[max_val_ind];
        ar[max_val_ind] = temp_val;
 
    } while (left_ind < right_ind);
}
 
template<typename T>
void biselectional_sort_odd(T ar[], size_t len)
{
    size_t  left_ind = 0, right_ind = len - 1,
        max_val_ind, min_val_ind;
    T temp_val;
 
    do
    {
        min_val_ind = max_val_ind = left_ind;
 
        for (size_t i = left_ind + 1; i < right_ind; i += 2)
        {
            ++comparison_count;
            if (ar[i] > ar[i + 1])
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i])
                    max_val_ind = i;
 
                ++comparison_count;
                if (ar[min_val_ind] > ar[i + 1])
                    min_val_ind = i + 1;
            }
            else
            {
                ++comparison_count;
                if (ar[max_val_ind] < ar[i + 1])
                    max_val_ind = i + 1;
 
                ++comparison_count;
                if (ar[min_val_ind] > ar[i])
                    min_val_ind = i;
            }
        }
        ++comparison_count;
        if (max_val_ind == left_ind)
            max_val_ind = min_val_ind;
 
        temp_val = ar[left_ind];
        ar[left_ind++] = ar[min_val_ind];
        ar[min_val_ind] = temp_val;
 
 
        temp_val = ar[right_ind];
        ar[right_ind--] = ar[max_val_ind];
        ar[max_val_ind] = temp_val;
 
    } while (left_ind < right_ind);
}
 
template<typename T>
void biselectional_sort(T* ar, size_t len)
{
    int left_ind = 0, right_ind = len - 1;
    int  min_val_ind = left_ind, max_val_ind = right_ind;
    comparison_count = 0;
 
    T temp_int;
 
    if (len>1)
        do
        {
            max_val_ind = right_ind;
            min_val_ind = left_ind;
            comparison_count++;
            if (ar[max_val_ind]<ar[min_val_ind])
            {
                temp_int = ar[max_val_ind];
                ar[max_val_ind] = ar[min_val_ind];
                ar[min_val_ind] = temp_int;
            }
 
            for (int i = left_ind + 1; i < right_ind; ++i)
            {
                comparison_count++;
                if (ar[max_val_ind]<ar[i])
                {
                    max_val_ind = i;
                }
                else
                    comparison_count++;
                if (ar[min_val_ind]>ar[i])
                {
                    min_val_ind = i;
                }
            }
            temp_int = ar[left_ind];
            ar[left_ind++] = ar[min_val_ind];
            ar[min_val_ind] = temp_int;
 
            temp_int = ar[right_ind];
            ar[right_ind--] = ar[max_val_ind];
            ar[max_val_ind] = temp_int;
        } while (left_ind<right_ind);//
}
 
int main(int argc, char* argv[])
{
    int ar[] =
    {
        //1,0,2,3,4,5,6//,0
        //5,4,3,2,1,0
        // 0,0//,
        2, 1,1,1,2,3,3,2, 5, 3, 7, 4, 8, 11, 90, 9,1
    };
    int ar_copy[] =
    {
        //1,0,2,3,4,5,6//,0
        //5,4,3,2,1,0
        //0,0//,
        2, 1,1,1,2,3,3,2, 5, 3, 7, 4, 8, 11, 90, 9,1
    };
    size_t len = sizeof(ar) / sizeof(ar[0]);
    biselectional_sort_henry(ar, len);
    cout << "The array with size of " << len << " was sorted with " << comparison_count << " comparisons\n";
    for (size_t i = 0; i<len; ++i)cout << ar[i] << " ";
    cout << endl;
 
    biselectional_sort(ar_copy, len);
    cout << "The array with size of " << len << " was sorted with " << comparison_count << " comparisons\n";
    for (size_t i = 0; i<len; ++i)cout << ar_copy[i] << " ";
    cout << endl;
    system("pause");
    return 0;
}

А вообще, думаю, что надо считать сравнения только между элементами массива. Ведь вместо чисел так могут быть указатели на файл или сокеты, или еще что-нибудь. В общем все, что при сравнении занимает довольно много времени.

IGPIGP · 07.08.2016, 11:59

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

Вот это вы явно в 3 часа ночи писали.

я сразу увидел но не сразу исправил. Сейчас скобки у else стоят от греха. Самое забавное, что и с ними и без них результаты одинаковы

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

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

то я так:

Спасибо! Вечером посмотрю.

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

А вообще, думаю, что надо считать сравнения только между элементами массива.

Принято. Тогда мне трудно выиграть, но игра есть игра. Сдаваться рано, - посмотрим.

@HenryDukart · 07.08.2016, 12:00

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

Самое забавное, что и с ними и без них результаты одинаковы

Это понятно почему. Считаете вы правильно, а вот если изменится максимум, то сравнение с минимумов все равно делаете, но счетчик не увеличиваете, потому что он в else.

IGPIGP · 07.08.2016, 12:03

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

но счетчик не увеличиваете, потому что он в else.

ValeryS · 07.08.2016, 13:06

накидал вот такого монстра в Qt

C++
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <time.h>
 
int Min1(int* arr,size_t sz)
{
    int min=arr[0];
    for(size_t i=1;i<sz;i++)
     if(arr[i]<min)
       min=arr[i];
return min;
}
int Min2(int* arr,size_t sz)
{
    int b=(sz/2)*2;
 
    int min=arr[0];
    int i;
    for(i=0;i<b;i+=2)
    {
     if(arr[i]<min)
       min=arr[i];
     if(arr[i+1]<min)
       min=arr[i+1];
 
    }
    for(;i<(int)sz;i++)
    {
     if(arr[i]<min)
       min=arr[i];
 
    }
 
 
return min;
}
int Min4(int* arr,size_t sz)
{
    int b=(sz/8)*8;
 
    int min=arr[0];
    int i;
    for(i=0;i<b;i+=8)
    {
     if(arr[i]<min)
       min=arr[i];
     if(arr[i+1]<min)
       min=arr[i+1];
     if(arr[i+2]<min)
       min=arr[i+2];
     if(arr[i+3]<min)
       min=arr[i+3];
     if(arr[i+4]<min)
       min=arr[i+4];
     if(arr[i+5]<min)
       min=arr[i+1+4];
     if(arr[i+2+4]<min)
       min=arr[i+2+4];
     if(arr[i+3+4]<min)
       min=arr[i+3+4];
    }
    for(;i<(int)sz;i++)
    {
     if(arr[i]<min)
       min=arr[i];
 
    }
 
 
return min;
}
int Min3(int* arr,size_t sz)
{
    int b=(sz/4)*4;
 
    int min=arr[0];
    int i;
    for(i=0;i<b;i+=4)
    {
     if(arr[i]<min)
       min=arr[i];
     if(arr[i+1]<min)
       min=arr[i+1];
     if(arr[i+2]<min)
       min=arr[i+2];
     if(arr[i+3]<min)
       min=arr[i+3];
 
    }
    for(;i<(int)sz;i++)
    {
     if(arr[i]<min)
       min=arr[i];
 
    }
 
 
return min;
}
 
 
 
 
 
 
int Min5(int* arr,size_t sz)
{
 
        int min=arr[0];
     unsigned int is_min;
        for(size_t i=1;i<sz;i++)
        {
         is_min=(arr[i]<min)-1;
           min=(arr[i]&(~is_min))+(min&(is_min));
       }
 
 
return min;
}
 
int Min6(int* arr,size_t sz)
{
 
        int min=arr[0];
    bool is_min;
        for(size_t i=1;i<sz;i++)
        {
         is_min=(arr[i]<min);
           min=(arr[i]*is_min)+(min*(!is_min));
       }
 
 
return min;
}
 
 
int main()
{
  // const unsigned int long long v=10000000000;// для Realise
      const unsigned int long long v=10000000;// для Debug
int arr[]={0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
          0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
          0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,-3,9,
            0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
            0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
            0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
            0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9,
          0,10,5,7,6,9,3,2,1,6,3,5,7,8,9,255,1,2,3,4,5,6,-2,7,8,9};
std::cout<<"Start"<<std::endl;
double fTimeStart = clock()/(double)CLOCKS_PER_SEC;
double fTimeStop;
for(unsigned int long long i=0;i<v;i++)
    Min1(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min1(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
fTimeStart = clock()/(double)CLOCKS_PER_SEC;
for(unsigned int long long i=0;i<v;i++)
    Min2(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min2(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
fTimeStart = clock()/(double)CLOCKS_PER_SEC;
for(unsigned int long long  i=0;i<v;i++)
    Min3(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min3(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
 
fTimeStart = clock()/(double)CLOCKS_PER_SEC;
for(unsigned int long long i=0;i<v;i++)
    Min4(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min4(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
fTimeStart = clock()/(double)CLOCKS_PER_SEC;
for(unsigned int long long  i=0;i<v;i++)
    Min5(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min5(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
 
fTimeStart = clock()/(double)CLOCKS_PER_SEC;
for(unsigned int long long  i=0;i<v;i++)
    Min6(arr,sizeof(arr)/sizeof(arr[0]));
fTimeStop=clock()/(double)CLOCKS_PER_SEC;
std::cout<<Min6(arr,sizeof(arr)/sizeof(arr[0]))<<"  Time ="<<fTimeStop-fTimeStart<<std::endl;
std::cout<<"Stop"<<std::endl;
}

поиск минимума
"классический"
развертка цикла на 2
развертка цикла на 4
развертка цикла на 8
замена ветвления арифметическими функциями
замена ветвления бинарными операциями
вот что получилось в Debug

Start
-3 Time =9.861
-3 Time =7.276
-3 Time =5.693
-3 Time =5.226
-3 Time =19.915
-3 Time =24.435
Stop

Realise

Start
-3 Time =11.437
-3 Time =11.365
-3 Time =11.313
-3 Time =11.344
-3 Time =11.433
-3 Time =11.352
Stop

видно что самый быстрые в Debug развертка цикла на 8, но на 4 не намного уступает а памяти меньше
а в Realise практически все одинаковые
видать оптимизатор поработал
"А если нет разницы, зачем платить больше"

@LVV · 07.08.2016, 13:51

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

Наиболее оптимальный способ нахождения особого элемента массива это применение алгоритма быстрой сортировки.

Как можно найти наименьший элемент массива быстрее, чем примитивное:

C++
1
2
3
for (int i=1; i<size; i++)
if (arr[i]<min)
min=arr[i];

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

Добавлено через 5 минут
........................................ ..........

@Ferrari F1 · 07.08.2016, 13:51

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

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

Наиболее оптимальный способ нахождения особого элемента массива это применение алгоритма быстрой сортировки.

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

он просто пришел сюда в надежде сорвать все покровы, но, увы, не вышло, ведь человек из раздела паскаля

@LVV · 07.08.2016, 13:52

Сообщение от Ferrari F1

он просто пришел сюда в надежде сорвать все покровы, но, увы, не вышло, ведь человек из раздела паскаля

Это обо мне?

@Ferrari F1 · 07.08.2016, 13:54

Не по теме:

LVV, нет

ValeryS · 07.08.2016, 13:55

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

Приведите пример, убеждающий в том, что я не прав.

я уже привел (Пост 133)-развертка цикла
Ускорение почти в два раза.

@LVV · 07.08.2016, 14:11

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

я уже привел (Пост 133)
развертка цикла, ускорение почти в два раз

Извините маня за тупизну. Но можно на пальцах.
Например, дан массив: arr[]={5, 4, 3, 2, 1}
Нужно найти минимальный элемент.
Классика работает так:
присваиваем значение min=arr[0] (одна операция присвоения)
for(int i=1; i<5; i++) (одна операция присвоения плюс четыре операции инкремента (присвоения) плюс пять операций сравнения)
if (arr[i]<min) (четыре операции сравнения)
min=arr[i] (четыре операции присвоения)
Итого: 10 операций присвоения плюс 9 операций сравнения

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

ValeryS · 07.08.2016, 14:20

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

А в быстрой сортировке как?

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

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32

	Найти минимум в массиве используя наиболее оптимальный алгоритм 03.08.2016, 22:30. Показов 15402. Ответов 186 Метки нет (Все метки) Дан массив чисел, надо найти минимум. Препод сказал - дополнительное задание: предложить наиболее оптимальный алгоритм, написать код, реализующий его идею, и обосновать его теоретически. 4

@Ferrari F1
	07.08.2016, 13:54
	Не по теме: LVV, нет 0