До питання про «втрачений час»

Нам випала чудова можливість провести невеличке, але вкрай повчальне тактичне заняття.
Питання оптимізації програм, які виробляють значну кількість обчислень, на жаль, недостатньо добре висвітлені в літературі і, як правило, зводяться до деяким загальним принципам, вірність яких зовсім не очевидна ні до прочитання аргументів автора, навіть не після. Оскільки у згаданому пості (шукайте за закавыченным словами) була запропонована не-безынтересная обчислювальна задача, яка дозволяє продемонструвати ці принципи і конкретні прийоми оптимізації в дії, і був створений справжній піст, який, хоч і дещо відхиляється від напрямку, улюбленого автором (я цілком собі бачу рішення даної задачі на МК класу М3 і навіть Ардуїнов, спробуйте, але все таки мікроконтролери призначені кілька для інших цілей), але тим не менш вписується в концепцію курсу з програмування МК.
Отже, ми починаємо.
Нагадаю завдання — потрібно знайти п'ять цілих невід'ємних чисел, таких, що сума п'яте ступенів перших чотирьох з них дорівнює п'ятій ступеня останнього. Формулювання не цілком коректна і буде в подальшому уточнюватися, але для початку зійде. Природний алгоритм вирішення цього завдання буде полягати в переборі можливих наборів чисел та перевірці виконання для них цієї умови. Одразу ж уточнимо умова — чисел, що не перевищують певної межі, інакше перебір може ніколи не закінчиться, якщо такого набору взагалі не існує (ми ж не сподіваємося серйозно перевірити ВСІ набори по п'ять з цілих невід'ємних чисел, не знаю, як читачі, я то точно не доживу до закінчення перебору). Напишемо це природне рішення, щоб відразу відзначити одну важливу рису сучасного програмування, і ось воно.
Відразу домовимося, що ми запускаємо всі свої програми на компіляторі MinGW версії 6.2 на х86 машині i3-2120 3.3 ГГц, що ці цифри не позначали. Якщо у вас параметри системи відрізняються від моїх, і абсолютні значення часових показників будуть дещо іншими, хоча відносний час роботи різних варіантів має бути близько.
Що ми бачимо — серед наборів чисел, менших 100, набору, що відповідає заданій умові, не знайдено ( насправді знайдено і їх багато, але вони нас не влаштовують, оскільки числа повинні бути різними і не рівними нулю… я про це раніше не сказав? — ще один аргумент на користь акуратного формулювання ТЗ) і в процесі перебору ми перевірили 1е10 комбінацій. При цьому час роботи програми склало 63 с.

Ми вже зрозуміли, що програма невірна чинності неповного формування умов, але, перш ніж ми почнемо її модифікувати, поговоримо про можливе прискорення обчислень при незмінному алгоритмі. У мій час були книги, в яких давалися рекомендації по машинно-незалежної оптимізації виконання за часом, і для даного алгоритму підійшли б наступні рекомендації:
— винести частину обчислень з внутрішнього циклу і сформувати проміжну суму перших трьох чисел;
— організувати внутрішній цикл по зменшенню індексу, а не зростання;
— організувати внутрішній цикл у вигляді do {} while, а не for;
— зробити індексний змінну реєстрової;
— оптимізувати обчислення п'ятого ступеня, що скоротить число множень з 4 до 3,
— перемежовувати обчислення ступенів, щоб не блокувати конвеєр і так далі…
і спочатку я збирався всі ці зміни провести і показати їх вплив на швидкодію і продемонструвати, як десятки відсотків перетворюються в рази збільшення швидкодії, але потім від цієї ідеї відмовився.

Справа в тому, що ці рекомендації дещо застаріли і в даний час єдине, що від програміста потрібно, так це дозволити компілятору провести оптимізацію на рівні 3. Так, потрібно знати, як це зробити, в моєму випадку управління оптимізацією ховається в розділі Project/Settingы...-Compile/Optimization, але це все, що необхідно знати для проведення такої оптимізації. Постійні читачі моїх постів (лещу себе надією, що такі є) вже звикли бачити в моїх опусах стогони з приводу занепаду моралі і недостатньо зеленої трави в сучасній електроніці порівняно з часами мого входу в професію, але зараз я, анітрохи не відмовляючись від висловлених раніше думок, повинен з усією певністю заявити — сучасні компілятори набагато краще від своїх попередників і майже ідеальні з точки зору породжуваного коду, якщо їм дозволити оптимізацію.

Настільки сильне твердження потребує доведення і ось воно — компілюємо нашу програму з включеною оптимізацією і на тому ж самому процесорі бачимо час виконання 20 секунд, тобто зростання швидкодії в 3 рази (в основному за рахунок першої рекомендації, хоча інші теж дали свій внесок до п'ятої частини прискорення) і без найменших зусиль з нашого боку — приголомшливо. Бажаючі можуть спробувати провести всі перераховані мною способи збільшення швидкодії і подивитися на результат, але я настійно рекомендую просто подивитися на продукується асемблерний код і зрозуміти, що поліпшити його практично неможливо. Приєднуючись до автора вихідного посту, можу настійно рекомендувати сайт gcc.godbolt.org, який дає можливість подивитись код, породжуваний компілятором gcc для різних архітектур і для різних режимів оптимізації.

Збільшення швидкодії істотне, тема алгоритмо-незалежної оптимізації вичерпана, але пост на цьому не закінчується — невже є ще що зробити. Так, є чим і як поліпшити програму (підвищити її швидкодію) і тут компілятор нам вже не помічник, оскільки він не розуміє суті виробляються в коді дій і не може запропонувати необхідних змін, це може зробити тільки програміст. На мій погляд, це удача, раз навіть сучасні засоби розробки програм залишають місце для творчості, хоча мій молодий колега знайшов певні незручності в просунутості сучасних компіляторів, заявивши ;«Вам було простіше, Ви знали, що компілятор нічого оптимізувати не буде, на нього не сподівалися і все робили вручну, а нам доводиться вирішувати, з якого моменту починається наша частина роботи». Ну що сказати — якщо Ви зробите ручками всі необхідні оптимізації, то гірше точно не буде (краще теж не стане, оскільки робота буде задублирована), так що Вам ніщо не заважає йти до кінця, я всього лише підказав більш коротку дорогу.

Повертаємося до нашої програми і шукаємо способи прискорити її. Вірніше, перш ніж шукати такі способи, необхідно упевнитися в необхідності цієї дії. Перевіряємо час виконання при різних значеннях кордону і виявляємо, що для значень 60 і 70 часи відрізняються більш, ніж в 2 рази, що підтверджує нашу гіпотезу щодо часу роботи алгоритму як про(N**5): 70/60=1.17**5=2.2 рази. Скористаємося отриманою формулою для оцінки часу виконання нашої програми для кордону 1000 і отримаємо 553 години, що кілька перевершує наші очікування, для великих чисел менше точно не буде — є сенс оптимізувати.
Далі перед абзацами будуть вказані принципи вирішення інженерних завдань системи ТРВЗ, як я її пам'ятаю.

ПРИНЦИП ВИКЛЮЧЕННЯ, АБО ПРИБИРАЄМО ПОВТОРНУ РОБОТУ.
Поки ми не бачимо можливість змінити отриману оцінку часу виконання алгоритму, але можна зменшити коефіцієнт при визначальному члені. Видно, що ми перебираємо всі перестановки заданої множини натуральних чисел, якщо врахувати можливість їх ранжувати та незалежність результату від порядку операндів, то приходимо до висновку, що нам необхідно розглядати поєднання елементів заданої множини. Перебір поєднань легко реалізується зміною початкового значення змінної циклу для чергового елемента, що ми і робимо і швидкість роботи програми зростає разюче, на два порядки. Ну так і має бути, ми розраховував на приріст у 5! раз, а це саме 120.

Невеликий відступ — в оригінальному пості автор приходить до подібної ідеї після виписування на листочку різних комбінацій індексів і розгляду одержаних результатів, оскільки чесно зізнається, що в комбінаториці не сильний. Віддаючи данину поваги його зусиллям, повинен заявити, що комбінаторика і елементи теорії ймовірностей (саме елементи, оскільки ТерВер у всій його красі і могутності не назвеш простим) — це та частина математики, без якої займатися аналізом алгоритмів контрпродуктивно. Я, звичайно, радий, що автору вдалося відтворити метод генерації поєднань, але його просто треба знати і все, як таблицю множення. Це я з приводу періодично виникаючих суперечок на тему, чи потрібна програмісту математика, але це моя особиста думка, виражена в приватній бесіді, і воно може бути помилковим.

Повертаючись до основної теми — це саме та оптимізація, яку не зробить компілятор, оскільки тут потрібно розуміти суть завдання і реалізує її рішення алгоритму, а він на це поки що не здатний (компілятор з двома командами все ще залишається нереалізованим ідеалом, хоча хто знає, що буде далі). І ще одна важлива особливість — зазвичай вигода від такої оптимізації багаторазово перевищує будь-яку можливу вигоду від оптимізації, здійснюваної компілятором, що і підтверджується в даному випадку, оскільки 120>>5. Зведемо отримані результати і спробуємо екстраполювати їх до деяких великих значень, отримуємо
Межа__Без оптимізації____Компілятор______Наша________Обидві
10_________0.00 _____________0.00__________0.00________0.00
50_________2.32______________0.66__________0.02________0.01
100________62.91_____________19.93_________0.49________0.16 ( 1.43)
150_______476.20____________150.67_________3.80________1.21 (10.99)
1000_______1800 год*____________553 год*_________14 год*_______ 5 ч*(35 год*)
(в дужках дано час обчислень для типу результату long long).
Бачимо, що якщо початковий варіант був практично неприйнятний при значеннях кордону вище 200, то останній варіант застосуємо до значення 1000. І ми навіть знайшли рішення, причому цілих два, правда, одне з них хибне через переповнення, але про це трохи пізніше, а поки спробуємо ще поліпшити швидкодію.

ПРИНЦИП ПОПЕРЕДНЬОГО ВИКОНАННЯ.
Очевидне рішення — обчислити значення ступенів заздалегідь і вибирати його з таблиці, безсумнівно, дало результат, але, чесно кажучи, трохи менший, ніж я сподівався, мабуть, з реалізацією множення у х86 все добре, а от з вибором з масиву гірше. Але все одно, приріст майже в 8 разів – дуже приємно. (Чому то для варіанту з типом результату int приросту продуктивності взагалі немає). Чисто теоретично, я можу собі уявити компілятор, який подібну оптимізацію проведе, але поки що я такого не бачив. Звернемо увагу на те, що в даному випадку нам довелося за швидкодію заплатити додатковою пам'яттю, що характерно, оскільки два напрямки оптимізації по часу і по пам'яті, як правило, суперечать один одному.
#include "time.h"
#include "stdio.h"
#define LOOP(n,m) for (int n=m+1; n<=MAX; n++) 
#define REZ(i) (Pow5[i])
typedef long long int rez_t;
int main(void) {
rez_t Pow5[1001];
for (int i=0; i < =1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i;

for (int MAX=50; MAX<=500; MAX=50) {
clock_t t = clock();

unsigned long long v=0;
int r=0;
LOOP(i1,0)
LOOP(i2,i1) 
LOOP(i3,i2) {
rez_t Sum = REZ(i1)+REZ(i2)+REZ(i3);
LOOP(i4,i3) 
LOOP(i5,i4) 
{
v++;
if (Sum+REZ(i4)==REZ(i5)) {
r++;
printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5);
};
}; 
};
t = clock() - t;
printf ("MAX=%d time is %f seconds.\n",
MAX, ((double)t)/CLOCKS_PER_SEC);
printf(" %llu %d\n",v,r);
};
return 1;
};

ПРИНЦИП ОБМЕЖЕННЯ, АБО ВИКЛЮЧАЄМО НЕВІДПОВІДНІ ВАРІАНТИ.
Йдемо далі і шукаємо додаткові шляхи, для чого кілька переформулюємо завдання — нам потрібно знайти число, п'ята ступінь якого дорівнює деякому конкретному числу (представляє собою суму п'яте ступенів чотирьох інших чисел, але це неважливо). Дана формулювання дозволяє нам зосередитися на слові «знайти» і відразу ж наштовхує на думку про напрямок оптимізації — прискорення пошуку, у нас він був лінійний шляхом перебору всіх можливих значень, а це не найкращий спосіб для впорядкованого набору даних. Перша думка — бінарний пошук і такий напрямок могло б дати істотний приріст продуктивності, але ми підемо іншим шляхом — для початку перестанемо переглядати варіанти, які свідомо не можуть бути рішенням, оскільки ми перебираємо значення в порядку зростання і шукане значення вже перевищено. Можна очікувати приросту швидкості в два рази, точна аналітична оцінка навряд чи можлива і ми дійсно отримуємо прискорення майже в 5 разів.

Невелике зауваження — для того, щоб перейти до цього методу нам довелося змінити тип результату на подвійне ціле. Справа в тому, що запропонований метод потребує впорядкованості п'яте ступенів чисел-кандидатів, а з рівності n>m, на мій превеликий жаль, не слід n%k > m%k, якщо будь-який із n або m перевершує k. Ви запитаєте, звідки тут взялося k, адже ми просто працюємо з цілими числами, але справа в тому, що в будь-практично реалізується архітектурі цілі числа (якщо швидкість виконання арифметичних операція з ними розумна) мають обмежену розрядність і, відповідно, передбачають взяття результату кожної операції по модулю максимально представимого числа. Якщо у нас результат 32 розрядний, то це число складе (2**32)-1 ~ 2**32 = (2**2)*(2**30) = 4*((2**10)**3) ~ 4*((10**3)**3) = 4*(10**9) = 0.4*(10**10) і корінь п'ятого ступеня з цього числа складе число, близьке до 100 (точне значення 84). тоді для 64 біт результату отримаємо найбільше значення межі 7130, а для 128 розрядного ~ 50е6.
#include "time.h"
#include "stdio.h"
#define LOOP(n,m) for (int n=m+1; n<=MAX; n++) 
#define REZ(i) (Pow5[i])
typedef long long rez_t;
int main(void) {
rez_t Pow5[1001];
for (int i=0; i < =1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i;

for (int MAX=50; MAX<=500; MAX=50) {
clock_t t = clock();

unsigned long long v=0;
int r=0;
LOOP(i1,0)
LOOP(i2,i1) 
LOOP(i3,i2) {
rez_t Sum3 = REZ(i1)+REZ(i2)+REZ(i3);
int i4=i3+1; 
do {
rez_t Sum4 = Sum3 + REZ(i4);
int i5=i4+1;
do {
v++;
if (Sum4==REZ(i5)) {
r++;
printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5);
};
i5++; } while ((Sum4>=REZ(i5)) && (i5<=MAX));
i4++; } while (i4<=MAX); 
};
t = clock() - t;
printf ("MAX=%d time is %f seconds.\n",
MAX, ((double)t)/CLOCKS_PER_SEC);
printf(" %llu %d\n",v,r);
};
return 1;
};


ПРИНЦИП ОЦІНОК, АБО ВИКОРИСТОВУЄМО ПОПЕРЕДНІ РЕЗУЛЬТАТИ (ГУСЕНИЦЯ).
Непогано, хоча для бінарного пошуку повинно бути набагато краще, але ми враховуємо ще одне міркування, яке робить такий спосіб краще — ми можемо істотно скоротити час пошуку, якщо не будемо переглядати числа, менші знайденого в попередньому циклі, адже саме вони були менше попередньої суми, то гарантовано будуть менше поточної, яка перевершує попередню. Виходить, що ми можемо працювати за принципом гусениці («Caterpillar method») для четвертого і п'ятого числа, а при застосуванні даного методу гарантовану кількість ітерацій не може перевершити значення 2*n, де n — довжина інтервалу та порівняно з попереднім необхідною кількістю ітерацій n*(n-1)/2 виграємо в (n-1)/4 разів, що вельми і вельми значно для великих чисел. При цьому кількість ітерацій навіть краще, ніж для бінарного пошуку, яке складе n*log2(n) і перевершить наше значення вже при n>2**2=4.
#include "time.h"
#include "stdio.h"
#define LOOP(n,m) for (int n=m+1; n<=MAX; n++) 
#define REZ(i) (Pow5[i])
typedef long long rez_t;
int main(void) {
rez_t Pow5[1001];
for (int i=0; i < =1000; i++) Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i;

for (int MAX=50; MAX<=500; MAX=50) {
clock_t t = clock();

unsigned long long v=0;
int r=0;
LOOP(i1,0)
LOOP(i2,i1) 
LOOP(i3,i2) {
rez_t Sum3 = REZ(i1)+REZ(i2)+REZ(i3);
int i4=i3+1; 
int i5=i4+1;
do {
rez_t Sum4 = Sum3 + REZ(i4);
if (Sum4 >= REZ(i5)) do {
v++;
if (Sum4==REZ(i5)) {
r++;
printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5);
};
i5++; } while ((Sum4>=REZ(i5)) && (i5<=MAX));
i4++; } while ((i4<=MAX) && (i5<MAX)); 
};
t = clock() - t;
printf ("MAX=%d time is %f seconds.\n",
MAX, ((double)t)/CLOCKS_PER_SEC);
printf(" %llu %d\n",v,r);
};
return 1;
};

Чудовий факт — нам вперше вдалося знизити коефіцієнт не перед визначальним членом, а порядок його, що призводить до вельми істотного прискорення роботи для великих значень меж розглянутих чисел. Зведемо ще раз результати в таблицю і порадіємо отриманих значень
Межа__Таблиця ступенів___Обмеження 5__Метод гусениці__Метод інверсії
100________0.3_________________0.1__________0.02____________0.04
150________1.8_________________0.6__________0.14____________0.28
200________6.6_________________2.3__________0.49____________0.36
300_______50.4________________16.1__________2.14____________2.26
1000_______6 год*________________1.5 год*_______210.0____________880*
5000_______2 г*________________0.5 г*________36 год*
Подальші розрахунки показують, що ми можемо очікувати на отримання результату для кордони 10 тисяч протягом 24 днів, що практично прийнятно, хоча цього ми робити не будемо.

Подальший розгляд теми планувалося з урахуванням чудового властивості п'ятого ступеня, а саме невеликого числа залишків за модулем 11, але ця тема непогано розкрита в черговому пості на тему гіпотези Ейлера і повторюватися не буду, зазначу лише, що простого способу використання даного властивості запропоновано не було (і я його не бачу) а непрості вимагають прямо таки непристойного кількості пам'яті.

МЕТОД ІНВЕРСІЇ.
Тому розгляд питання продовжимо з іншого боку — переформулюємо завдання наступним чином — знайти чотири натуральні числа, сума п'яте ступенів яких складе п'яту ступінь натурального числа. На перший погляд, нічого особливого не сталося, але ми можемо почати завдання з кінця — задаємося шуканої сумою і намагаємося її скласти. Такий підхід відразу дозволяє нам сформулювати деякі обмеження на відповідні числа. Наприклад, для найбільшого з чотирьох чисел ми знаємо, що воно не може перевершувати шуканого числа (це тривіально) і його п'ята ступінь не може бути менше однієї четвертої п'ятого ступеня шуканого числа (а ось це не настільки тривіально, але очевидно), що звужує область допустимих кандидатів з n 1 до n*(1-корінь п'ятого ступеня з 4=1.32), тобто в три рази. Далі, взявши кандидата на роль четвертого числа, ми можемо відразу визначити, що залишилася різниця і вибирати кандидата на роль третього числа з урахуванням аналогічних міркувань по відношенню до неї. Оцінити результат подібної оптимізації аналітично особисто я не беруся, тому просто пишемо програму і дивимося на результат.
#include "time.h"
#include "stdio.h"
#define LOOP(n,m) for (int n=m+1; n<=MAX; n++) 
#define REZ(i) (Pow5[i])
typedef long long rez_t;
int main(void) {
rez_t Pow5[1001];
for (int i=0; i < =1000; i++) {
Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i;
};
for (int MAX=100; MAX<=1000; MAX=50) {
clock_t t = clock();

unsigned long long v=0;
int r=0;
int i5=MAX; do {
int i4=i5-1; 
do {
rez_t Ost1=REZ(i5)-REZ(i4);
int i3=i4-1;
if (REZ(i4)*4 > Ost1) 
do {
rez_t Ost2 = Ost1-REZ(i3);
int i2=i3-1; 
if ((REZ(i3)*3 > Ost2) && (Ost2>0)) 
do {
rez_t Ost3=Ost2-REZ(i2);
int i1=i2-1;
if ((REZ(i2)*2 > Ost3) && (Ost3>0)) 
do {
v++;
if (Ost3==REZ(i1)) {
r++;
printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5);
};
i1--; } while (i1>0);
i2--; } while (i2>0);
i3--; } while (i3>0);
i4--; } while (i4>0); 
i5--;} while (i5>0);

t = clock() - t;
printf ("MAX=%d time is %f seconds.\n",
MAX, ((double)t)/CLOCKS_PER_SEC);
printf(" %llu %d\n",v,r);
};
return 1;
};

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

І тут приходить осяяння – ми можемо почати за новим методом, істотно скоротивши перебір двох старших доданків, а два молодших будемо шукати методом гусениці, оскільки ми вже знаємо їх суму!!! (Кількість знаків оклику цілком відповідає потужності ідеї). Тобто ми візьмемо молодше число рівним одиниці, наступне – максимально можливого з урахуванням старших і будемо рухати нижню або верхню межу інтервалу залежно від результату.
#include "time.h"
#include "stdio.h"
#define LOOP(n,m) for (int n=m+1; n<=MAX; n++) 
#define REZ(i) (Pow5[i])
typedef long long rez_t;
int main(void) {
rez_t Pow5[1001];
for (int i=0; i < =1000; i++) {
Pow5[i]=(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i*(rez_t)i;
};
for (int MAX=100; MAX<=1000; MAX=50) {
clock_t t = clock();

unsigned long long v=0;
int r=0;
int i5=MAX; do {
int i4=i5-1; 
do {
rez_t Ost1=REZ(i5)-REZ(i4);
int i3=i4-1;
if (REZ(i4)*4 > Ost1) 
do {
rez_t Ost2 = Ost1-REZ(i3);
int i2=i3-1;
int i1=1;
if ((REZ(i3)*3 > Ost2) && (Ost2>0)) 
do {
v++;
rez_t Sum2=REZ(i1)+REZ(i2);
if (Ost2==Sum2) {
r++;
printf("%4d %4d %4d %4d %4d \n",i1,i2,i3,i4,i5);
};
if (Sum2>=Ost2) i2--; else i1++;
} while (i1<=i2); 
i3--; } while (i3>0);
i4--; } while (i4>0); 
i5--;} while (i5>0);

t = clock() - t;
printf ("MAX=%d time is %f seconds.\n",
MAX, ((double)t)/CLOCKS_PER_SEC);
printf(" %llu %d\n",v,r);
};
return 1;
};

Ось програма, а ось і результат – для значень до тисячі ми вважаємо лише 21.7 секунди – в 10 разів швидше попередньої версії, а вже з початкової і порівнювати не будемо. З такою програмою можна вже замахуватися і на значення порядку тисяч, залишаю це на частку допитливого читача.

Всіх з Новим роком.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.