Довольно большое время работы с std::min()

@ZaMaZaN4iK · Регистрация: 24.06.2012

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

Здравствуйте! Имеется 2 исходника.
1:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
#include <cctype>
#include <iterator>
#include <cmath>
 
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ins insert
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pdd;
 
const ll maxn = 1000009;
 
ll n, m, i, j, k;
vector<ll> p;
int f[maxn];
 
inline void test()
{
    f[1] = 1; f[2] = 2; f[3] = 3;
    for (ll i = 1; i <= 100; ++i)
        p.pb(i*i*i);
    cin >> n;
    for (ll i = 4; i <= n; ++i)
    {
        f[i] = 1000000009;
        for (ll j = 0; j<p.size(); ++j)
        {
            if (i >= p[j] && f[i] > f[i - p[j]] + 1)
                f[i] = f[i - p[j]] + 1;
        }
    }
    cout << f[n];
    //system("pause");
}
 
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    test();
    //system("pause");
    return 0;
}

2:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
#include <cctype>
#include <iterator>
#include <cmath>
 
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ins insert
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<ld,ld> pdd;
 
const ll maxn=1000009;
 
ll n,m,i,j,k;
vector<ll> p;
ll f[maxn];
 
void test()
{
    f[1]=1;f[2]=2;f[3]=3;
    for(ll i=1;i<=100;++i)
        p.pb(i*i*i);
    cin>>n;
    for(ll i=4;i<=n;++i)
    {
        f[i]=1000000009;
        for(ll j=0;j<p.size();++j)
        {
            if(i>=p[j])
                f[i]=min(f[i],f[i-p[j]]+1);
            else
                break;
        }
    }
    cout<<f[n];
}
 
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    test();
    //system("pause");
    return 0;
}

Исходники абсолютно идентичны, за исключением одной строки : в 1-ом коде ипользовано условие

C++
1
if (i >= p[j] && f[i] > f[i - p[j]] + 1)

для замены std::min во 2-ом исходнике.

Самое интересное : при сдаче задачи в тестирующую систему программа с этим if'ом заходит с довольно большим запасом по времени, тогда как версия с std::min ловит Time Limit и по моим замерам работает в 4-5 раз дольше.

Кто может обьяснить, почему так происходит? Неужели вызов функции настолько замедляет программу каждый раз? Функция std::min элементарна же.(вариант со своим, самописным min с inline и без шаблонов я не тестил).

@Toshkarik · 05.12.2014, 09:31

ZaMaZaN4iK, как минимум, у Вас во втором случае присваивание происходит чаще.

@DrOffset · 05.12.2014, 09:39

ZaMaZaN4iK, не по теме, но с вектором у тебя беда. Сделай p.reserve(100) перед циклом:

C++
1
2
3
p.reserve(100);
for(ll i=1;i<=100;++i)
        p.pb(i*i*i);

@TheCalligrapher · 05.12.2014, 09:59

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

Исходники абсолютно идентичны,

Да что вы говорите???

Смотрим в первый

C++
1
2
3
4
5
for (ll j = 0; j<p.size(); ++j)
{
  if (i >= p[j] && f[i] > f[i - p[j]] + 1)
    f[i] = f[i - p[j]] + 1;
}

Смотрим во второй

C++
1
2
3
4
5
6
7
for(ll j=0;j<p.size();++j)
{
  if(i>=p[j])
    f[i]=min(f[i],f[i-p[j]]+1);
  else
    break;
}

Что-то я не вижу этого 'break' в первом исходнике.

@ZaMaZaN4iK · 05.12.2014, 11:33 **[ТС]**

TheCalligrapher, прошу прощения. Не тот исходник добавил. В том, про который я веду речь, этот самый break стоит.Так что тут с меня взятки гладки

DrOffset, Да, я знаю. Можно и reserve(), можно и сразу размер указать. Не суть важно. На таком размере массива(а размер всего лишь сто) произойдет всего лишь 8 перевыделений памяти. Хоть это и медленная операция, но здесь она не играет ключевую роль. А так да,конечно, Вы правы. Просто лень писать было(хоть это и глупо звучит

)

Toshkarik, ну я понимаю это. Но что, операция присваивания такая долгая что ли?

Добавлено через 4 минуты
TheCalligrapher, не туда я посмотрел. На самом деле тот код даже без break работает быстрее. И если я там этот break поставлю, то это наоборот будет только оптимизация, а не замедление кода.

Добавлено через 1 минуту
И там кстати нужно писать break с условием, иначе будет неправильный ответ

@DrOffset · 05.12.2014, 12:05

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

На таком размере массива(а размер всего лишь сто) произойдет всего лишь 8 перевыделений памяти

Ты не можешь знать сколько произойдет перевыделений на машине, где прогоняется тест. Там и компилятор и ОС и стандартная библиотека совсем не обязательно будут совпадать с твоими. Раз уж пишешь задачки на скорость, то нужно ответственно к этому относиться. В любом случае, динамическое выделение памяти - это одна из самых затратных операций в твоей программе.

@ZaMaZaN4iK · 05.12.2014, 13:04 **[ТС]**

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

Я не просто знаю, я уверен, что там будет не более 8 первыделений памяти. Так как по стандарту вектор увеличивает свой размер в 2 раза по сравнению с предыдущим. Ну и тут просто логарифм возьмем и получим, что 8-9 перевыделений. И хоть это операция долгая, я не спорю, она так мало раз выполняется, что не это ключевое место в моем коде. Версия компилятора на сайте была также указана и она совпадает с моим(также, как и флаги компиляции). А STL'овский вектор только таким способ память перевыделяет.

@Toshkarik · 05.12.2014, 13:08

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

Так как по стандарту вектор увеличивает свой размер в 2 раза по сравнению с предыдущим.

По какому, интересно, стандарту? Неправда это.

По теме: попробуйте использовать профилировщик.

@ZaMaZaN4iK · 05.12.2014, 13:12 **[ТС]**

Toshkarik, прошу прощения за может быть неправильно понятое выражение. Стандартом я имел в виду стандартную реализацию vector в STL. Вот ссылка на Хабр : тыц

@Toshkarik · 05.12.2014, 13:16

ZaMaZaN4iK, это зависит от компилятора, от конкретной реализации STL. Были компиляторы и с 1.5 и c 1.7 и с 2.5 множителями. Правда, версии сейчас не вспомню.

Добавлено через 1 минуту
Вот, что то нашел: http://alenacpp.blogspot.ru/2005/06/vector_30.html

@ZaMaZaN4iK · 05.12.2014, 13:23 **[ТС]**

Toshkarik, да, спасибо за ссылку. Тоже читал. Только что замерил свой коэффициент - 2. К сожалению, у меня используется наихудший. Из этого следует, что хуже моего варианта не будет точно

Добавлено через 1 минуту
Toshkarik, Вы не подскажете, так в чём может быть проблема всё таки ? тут явно дело не в перераспрделении памяти. Так как во первых, в двух исходниках используется один и тот же вариант, а во вторых, я уже протестил уже и с reserve(). Неужели операция присваивания так много занимает времени? Или вызов функции std::min() такой долгий?

@Toshkarik · 05.12.2014, 13:30

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

Или вызов функции std::min() такой долгий?

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

C++
1
2
3
4
if (i >= p[j] && f[i] > f[i - p[j]] + 1) {
   f[i] = f[i - p[j]] + 1;
   cnt++;
}

C++
1
2
3
4
5
if(i>=p[j]) {
   f[i]=min(f[i],f[i-p[j]]+1);
   cnt++;
} else
      break;

И сравните их.

@ZaMaZaN4iK · 05.12.2014, 13:34 **[ТС]**

Только что написал свою функцию min:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
#include <cctype>
#include <iterator>
#include <cmath>
 
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define ins insert
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<ld,ld> pdd;
 
const ll maxn=1000009;
 
ll n,m,i,j,k;
vector<ll> p;
ll f[maxn];
 
ll mini(ll a,ll b)
{
    if(a<=b)    return a;
    else    return b;
}
 
void test()
{
    f[1]=1;f[2]=2;f[3]=3;
    for(ll i=1;i<=100;++i)
        p.pb(i*i*i);
    cin>>n;
    for(ll i=4;i<=n;++i)
    {
        f[i]=1000000009;
        for(ll j=0;j<p.size();++j)
        {
            if(i>=p[j])
                f[i]=mini(f[i],f[i-p[j]]+1);
            else
                break;
        }
    }
    cout<<f[n];
}
 
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    test();
    //system("pause");
    return 0;
}

С ней задача заходит. Но эта версия работает на 0.2 секунды дольше версии с if

Добавлено через 3 минуты
Toshkarik, да,я делал это. В случае с min оно, понятное дело, больше. Это сразу понятно. Получается, что программа тормозит из-за того, что очень много раз выполняется операция присваивания... Но я никак не мог предположить, что эта операция может долго выполняться.

@Max Dark · 05.12.2014, 14:01

Как заставить компилятор C/C++ генерировать плохой код

@DrOffset · 05.12.2014, 14:25

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

Вы мне лучше помогите с тем местом, на которое я обратил Ваше внимание.

Вроде бы выше уже дали ответ. Код неэквивалентен. Операций в коде с std::min больше и выполняются они чаще. Сам по себе вызов std::min инлайнится и накладных расходов на его вызов нет. Можно переписать так, результат будет таким же:

C++
1
2
3
4
            if(i >= p[j])
            {
                f[i] = f[i] < f[i - p[j]] + 1 ? f[i] : f[i - p[j]] + 1;
            }

Поэтому решение одно: корректируй алгоритм, чтобы избежать лишних операций и будет тебе счастье. Сам по себе std::min в твоих бедах не виноват.

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

Я не просто знаю, я уверен, что там будет не более 8 первыделений памяти. Так как по стандарту вектор увеличивает свой размер в 2 раза по сравнению с предыдущим.

Вот про два раза в стандарте как раз ничего нет. Это диктуется стратегией выделения памяти, которую определяет разработчик стандартной библиотеки. Следовательно, зависит от реализации (да, в g++ увеличивается действительно в 2 раза, но это еще не значит, что это какой-либо стандарт). Но если этот вопрос вызывает такую негативную реакцию у тебя, то ладно, мне в принципе все равно.

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

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

тут явно дело не в перераспрделении памяти.

Причем я выше явно указал, что дело не в этом. Когда я сказал про распределение памяти, то указал, что это замечание к теме не относится. Но твое восприятие в штыки моих комментариев не дало этой информации усвоится

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

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

Получается, что программа тормозит из-за того, что очень много раз выполняется операция присваивания... Но я никак не мог предположить, что эта операция может долго выполняться.

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	05.12.2014, 09:31
	ZaMaZaN4iK, как минимум, у Вас во втором случае присваивание происходит чаще. 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	05.12.2014, 11:33 [ТС]
	TheCalligrapher, прошу прощения. Не тот исходник добавил. В том, про который я веду речь, этот самый break стоит.Так что тут с меня взятки гладки DrOffset, Да, я знаю. Можно и reserve(), можно и сразу размер указать. Не суть важно. На таком размере массива(а размер всего лишь сто) произойдет всего лишь 8 перевыделений памяти. Хоть это и медленная операция, но здесь она не играет ключевую роль. А так да,конечно, Вы правы. Просто лень писать было(хоть это и глупо звучит ) Toshkarik, ну я понимаю это. Но что, операция присваивания такая долгая что ли? Добавлено через 4 минуты TheCalligrapher, не туда я посмотрел. На самом деле тот код даже без break работает быстрее. И если я там этот break поставлю, то это наоборот будет только оптимизация, а не замедление кода. Добавлено через 1 минуту И там кстати нужно писать break с условием, иначе будет неправильный ответ 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	05.12.2014, 13:04 [ТС]
	DrOffset, да, я обычно память резервирую,но хочу Ваше внимание, что не это место узкое в моей программе, этот оптимайз на максимальных данных(а это повторюсь всего лишь 100), даёт выигрыш на самом большом тесте всего лишь 4 сотых секунды.Вы мне лучше помогите с тем местом, на которое я обратил Ваше внимание. Я не просто знаю, я уверен, что там будет не более 8 первыделений памяти. Так как по стандарту вектор увеличивает свой размер в 2 раза по сравнению с предыдущим. Ну и тут просто логарифм возьмем и получим, что 8-9 перевыделений. И хоть это операция долгая, я не спорю, она так мало раз выполняется, что не это ключевое место в моем коде. Версия компилятора на сайте была также указана и она совпадает с моим(также, как и флаги компиляции). А STL'овский вектор только таким способ память перевыделяет. 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	05.12.2014, 13:12 [ТС]
	Toshkarik, прошу прощения за может быть неправильно понятое выражение. Стандартом я имел в виду стандартную реализацию vector в STL. Вот ссылка на Хабр : тыц 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	05.12.2014, 13:16
	ZaMaZaN4iK, это зависит от компилятора, от конкретной реализации STL. Были компиляторы и с 1.5 и c 1.7 и с 2.5 множителями. Правда, версии сейчас не вспомню. Добавлено через 1 минуту Вот, что то нашел: http://alenacpp.blogspot.ru/2005/06/vector_30.html 1

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	05.12.2014, 13:23 [ТС]
	Toshkarik, да, спасибо за ссылку. Тоже читал. Только что замерил свой коэффициент - 2. К сожалению, у меня используется наихудший. Из этого следует, что хуже моего варианта не будет точно Добавлено через 1 минуту Toshkarik, Вы не подскажете, так в чём может быть проблема всё таки ? тут явно дело не в перераспрделении памяти. Так как во первых, в двух исходниках используется один и тот же вариант, а во вторых, я уже протестил уже и с reserve(). Неужели операция присваивания так много занимает времени? Или вызов функции std::min() такой долгий? 0

@Max Dark Диванный эксперт 2550 / 2064 / 971 Регистрация: 09.10.2013 Сообщений: 4,793 Записей в блоге: 4
	05.12.2014, 14:01
	Как заставить компилятор C/C++ генерировать плохой код 1