Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#1 2016-12-21 19:15:07
Оптимізації при компіляція рішень
Шановне журі, можете, будь ласка, пояснити чому при компіляції рішень (як мінімум c та c++, інші мови не перевіряв) вимкнені оптимізації (компілятору не передається параметр -O2)?
Мені абсолютно не зрозуміла мотивація такого підходу.
1) Переважна більшість олімпіад збирають рішення з оптимізаціями. Включаючи всеукраїнський етап UOI (та й попередні етапи, наскільки мені відомо, у багатьох регіонах проходять на єджаджі, де оптимізації по дефолту ввімкнені і навряд чи їх хтось вимикає).
2) В поєднанні з жорсткими ТЛ-ми відсутність оптимізацій робить безглуздим використання STL (через її повільність при компіляції без оптимізацій). Таким чином, в учасників може складатися (хибне) враження, що свій велосипед завжди кращий за бібліотечне рішення. Хоча ще раз підкреслю, що це не так. Зібрана з оптимізаціями STL працює, як мінімум, не повільніше, ніж більшість реалізацій алгоритмів та структур даних від школярів. Не говорячи вже про гарантовано меншу кількість багів і більшу універсальність. До речі, до слів з цьогорічного запрошення до участі
Запрошення написав:
Однак ми настійливо запрошуємо взяти участь в олімпіаді всіх тих, хто бажає покращити свої знання з теорії алгоритмів та практиці програмування
"Практика програмування" за таких умов може бути хіба що в плані "практика з того, як робити не треба", бо в професійному програмуванні важко собі уявити гіршого програміста, ніж той, хто пише свої велосипеди при наявності готових бібліотечних рішень.
3) Як наслідок поєднання попередніх двох пунктів. Навіть не торкаючись професійного програмування. Учасники олімпіади, навчившись тут, що STL повільна потім можливо потраплять на інші олімпіади. І безглуздо витрачатимуть там купу часу, пишучи свої алгоритми і структури, замість того, щоб використати бібліотечні, які працюють не гірше. Навіть якщо напам'ять зазубрити реалізацію якогось квіксорту, чи кучі - все одно написання займе значно більше часу, ніж написання "sort(a.begin(), a.end());" чи "priority_queue<pair<int, int> > pq;". Плюс баги.
4) Це обмеження можна відносно легко обійти (див. пост-скриптум). Хоча на 4 турі в учасників, можливо, і не буде часу щоб гратися з асемблером...
5) Це ставить у нерівні умови сішників і паскалістів. Останні мають змогу писати директиви компілятору прямо в коді програми і, відповідно, можуть обійти це обмеження значно легше, ніж сішники - не треба ніяких танців з асемблером, достатньо просто написати {$OPTIMIZATION LEVEL2}.
Коротше кажучи, хотілось би отримати якийсь коментар з цього приводу від журі.
P.S. В якості підтвердження, що оптимізації дійсно вимкнені.
Є ось таке рішення MSLPRIM:
Код:
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int a[77][77];
int dp[2][77][4778] = {0};
void solve() {
int possible_sums[22] = {4,
7,
44,
47,
74,
77,
444,
447,
474,
477,
744,
747,
774,
777,
4444,
4447,
4474,
4477,
4744,
4747,
4774,
4777};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 22; ++j) {
int sum = possible_sums[j];
int reminder = sum - a[0][i];
if (reminder >= 0) {
dp[0][i][reminder] = max(dp[0][i][reminder], sum);
}
}
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int begin = j > 0 ? j - 1 : 0;
int end = j < m - 1 ? j + 1 : m - 1;
for (int k = begin; k <= end; ++k) {
for (int part_reminder = a[i][j]; part_reminder < 4778; ++part_reminder) {
int sum = dp[0][k][part_reminder];
int reminder = part_reminder - a[i][j];
if (dp[1][j][reminder] < sum) {
dp[1][j][reminder] = sum;
}
}
}
}
memcpy(dp[0], dp[1], sizeof(dp[0]));
memset(dp[1], 0, sizeof(dp[1]));
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
solve();
int result = 0;
for (int i = 0; i < m; ++i) {
if (dp[0][i][0] > result) {
result = dp[0][i][0];
}
}
if (!result) {
result = -1;
}
cout << result << endl;
}Онлайн-перевірку воно проходить ось так:
Код:
Тест Результат Час роботи 00 PASSED (+0) 0.01 с 01 PASSED (+1) 0.05 с 02 PASSED (+1) 0.04 с 03 PASSED (+1) 0.01 с 04 PASSED (+1) 0.01 с 05 PASSED (+1) 0.01 с 06 PASSED (+1) 0.02 с 07 PASSED (+1) 0.01 с 08 PASSED (+1) 0.02 с 09 PASSED (+1) 0.02 с 10 PASSED (+1) 0.02 с 11 PASSED (+1) 0.05 с 12 PASSED (+1) 0.05 с 13 PASSED (+1) 0.07 с 14 FAILED (Time Out) 0.11 с 15 PASSED (+1) 0.28 с 16 PASSED (+1) 0.02 с 17 PASSED (+1) 0.02 с 18 PASSED (+1) 0.16 с 19 PASSED (+1) 0.90 с 20 FAILED (Time Out) 0.52 с 21 PASSED (+4) 0.77 с 22 PASSED (+4) 0.54 с 23 PASSED (+4) 0.46 с 24 PASSED (+4) 0.76 с 25 PASSED (+4) 0.46 с
В той же час, якщо скомпілювати функцію solve з оптимізаціями (з ключами -O2 -fPIC) і замінити її реалізацію отриманим асемблерним кодом:
Код:
#include <iostream>
using namespace std;
asm (
"solve:\n"
" pushq %r15\n"
" pushq %r14\n"
" pushq %r13\n"
" pushq %r12\n"
" pushq %rbp\n"
" pushq %rbx\n"
" subq $136, %rsp\n"
" movq m@GOTPCREL(%rip), %rax\n"
" movl $4, 32(%rsp)\n"
" movl $7, 36(%rsp)\n"
" movl $44, 40(%rsp)\n"
" movl $47, 44(%rsp)\n"
" movl (%rax), %r14d\n"
" movl $74, 48(%rsp)\n"
" movl $77, 52(%rsp)\n"
" movl $444, 56(%rsp)\n"
" movl $447, 60(%rsp)\n"
" movl $474, 64(%rsp)\n"
" testl %r14d, %r14d\n"
" movl $477, 68(%rsp)\n"
" movl $744, 72(%rsp)\n"
" movl $747, 76(%rsp)\n"
" movl $774, 80(%rsp)\n"
" movl $777, 84(%rsp)\n"
" movl $4444, 88(%rsp)\n"
" movl $4447, 92(%rsp)\n"
" movl $4474, 96(%rsp)\n"
" movl $4477, 100(%rsp)\n"
" movl $4744, 104(%rsp)\n"
" movl $4747, 108(%rsp)\n"
" movl $4774, 112(%rsp)\n"
" movl $4777, 116(%rsp)\n"
" jle .LL7\n"
" leaq 32(%rsp), %rbx\n"
" leal -1(%r14), %r9d\n"
" movq a@GOTPCREL(%rip), %rbp\n"
" leaq dp(%rip), %r8\n"
" xorl %esi, %esi\n"
" leaq 88(%rbx), %r11\n"
" addq $1, %r9\n"
".LL8:\n"
" movslq %esi, %r10\n"
" movl 0(%rbp,%rsi,4), %edi\n"
" leaq 4(%rbx), %rdx\n"
" movl $4, %eax\n"
" imulq $4778, %r10, %r10\n"
" jmp .LL6\n"
".LL25:\n"
" movl (%rdx), %eax\n"
" addq $4, %rdx\n"
".LL6:\n"
" movl %eax, %ecx\n"
" subl %edi, %ecx\n"
" js .LL4\n"
" movslq %ecx, %rcx\n"
" addq %r10, %rcx\n"
" cmpl %eax, (%r8,%rcx,4)\n"
" cmovge (%r8,%rcx,4), %eax\n"
" movl %eax, (%r8,%rcx,4)\n"
".LL4:\n"
" cmpq %r11, %rdx\n"
" jne .LL25\n"
" addq $1, %rsi\n"
" cmpq %r9, %rsi\n"
" jne .LL8\n"
".LL7:\n"
" movq n@GOTPCREL(%rip), %rax\n"
" movl (%rax), %eax\n"
" cmpl $1, %eax\n"
" jle .LL1\n"
" subl $2, %eax\n"
" movq a@GOTPCREL(%rip), %rdx\n"
" leaq dp(%rip), %r15\n"
" imulq $308, %rax, %rax\n"
" leaq 308(%rdx), %r13\n"
" leaq 616(%rdx,%rax), %rax\n"
" movq %rax, 16(%rsp)\n"
" leal -1(%r14), %eax\n"
" movl %eax, 28(%rsp)\n"
".LL12:\n"
" testl %r14d, %r14d\n"
" jle .LL9\n"
" xorl %ebp, %ebp\n"
" movq $0, 8(%rsp)\n"
" movl $1, %ebx\n"
" xorl %r11d, %r11d\n"
" xorl %r12d, %r12d\n"
" xorl %eax, %eax\n"
".LL10:\n"
" movl 28(%rsp), %edi\n"
" movl %r12d, 24(%rsp)\n"
" cmpl %edi, %r12d\n"
" cmovl %ebx, %edi\n"
" cmpl %edi, %eax\n"
" movl %edi, %edx\n"
" jg .LL15\n"
" movslq %eax, %rsi\n"
" movl 0(%r13,%r11,4), %r8d\n"
" subl %eax, %edx\n"
" imulq $19112, %rsi, %rcx\n"
" movq 8(%rsp), %rdi\n"
" subq %r11, %rsi\n"
" leaq 1(%rsi,%rdx), %r9\n"
" movl $4777, %eax\n"
" movl $1471624, %r10d\n"
" subl %r8d, %eax\n"
" subq %rbp, %r10\n"
" movslq %r8d, %rsi\n"
" leaq 367907(%rdi,%rax), %rax\n"
" imulq $19112, %r9, %r9\n"
" addq %rbp, %rcx\n"
" leaq (%r15,%rax,4), %rdi\n"
".LL17:\n"
" cmpl $4777, %r8d\n"
" jg .LL19\n"
" leaq (%r15,%r10), %rax\n"
".LL20:\n"
" leaq (%rax,%rcx), %rdx\n"
" movl -1471624(%rdx,%rsi,4), %edx\n"
" cmpl (%rax), %edx\n"
" jle .LL18\n"
" movl %edx, (%rax)\n"
".LL18:\n"
" addq $4, %rax\n"
" cmpq %rdi, %rax\n"
" jne .LL20\n"
".LL19:\n"
" addq $19112, %rcx\n"
" cmpq %r9, %rcx\n"
" jne .LL17\n"
".LL15:\n"
" cmpl %r14d, %ebx\n"
" jge .LL9\n"
" addl $1, %r12d\n"
" addq $1, %r11\n"
" addl $1, %ebx\n"
" addq $4778, 8(%rsp)\n"
" subq $19112, %rbp\n"
" movl 24(%rsp), %eax\n"
" jmp .LL10\n"
".LL9:\n"
" leaq 1471624+dp(%rip), %rsi\n"
" movl $1471624, %edx\n"
" movq %r15, %rdi\n"
" addq $308, %r13\n"
" call memcpy@PLT\n"
" leaq 1471624+dp(%rip), %rdi\n"
" xorl %esi, %esi\n"
" movl $1471624, %edx\n"
" call memset@PLT\n"
" cmpq 16(%rsp), %r13\n"
" jne .LL12\n"
".LL1:\n"
" addq $136, %rsp\n"
" popq %rbx\n"
" popq %rbp\n"
" popq %r12\n"
" popq %r13\n"
" popq %r14\n"
" popq %r15\n"
" ret\n"
);
typedef long long ll;
int n, m;
int a[77][77];
int dp[2][77][4778] = {0};
extern "C" void solve();
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
solve();
int result = 0;
for (int i = 0; i < m; ++i) {
if (dp[0][i][0] > result) {
result = dp[0][i][0];
}
}
if (!result) {
result = -1;
}
cout << result << endl;
}результат перевірки стає таким:
Код:
Тест Результат Час роботи 00 PASSED (+0) 0.01 с 01 PASSED (+1) 0.02 с 02 PASSED (+1) 0.02 с 03 PASSED (+1) 0.01 с 04 PASSED (+1) 0.01 с 05 PASSED (+1) 0.01 с 06 PASSED (+1) 0.02 с 07 PASSED (+1) 0.01 с 08 PASSED (+1) 0.02 с 09 PASSED (+1) 0.02 с 10 PASSED (+1) 0.04 с 11 PASSED (+1) 0.06 с 12 PASSED (+1) 0.03 с 13 PASSED (+1) 0.04 с 14 PASSED (+1) 0.05 с 15 PASSED (+1) 0.09 с 16 PASSED (+1) 0.01 с 17 PASSED (+1) 0.01 с 18 PASSED (+1) 0.10 с 19 PASSED (+1) 0.22 с 20 PASSED (+1) 0.20 с 21 PASSED (+4) 0.20 с 22 PASSED (+4) 0.15 с 23 PASSED (+4) 0.14 с 24 PASSED (+4) 0.20 с 25 PASSED (+4) 0.14 с
P.P.S. Про всяк випадок. Я в курсі, що на С++ можна написати рішення, яке зайде по часу і без оптимізацій і я в курсі, що є учасники з такими рішеннями. Мова не про це.
Відредаговано Dim_ov (2016-12-21 22:41:19)
Поза форумом
#2 2016-12-27 17:46:22
- Жюри_Пасихов
- Адміністратор
- Зареєстрований: 2009-11-08
- Повідомлень: 440
Re: Оптимізації при компіляція рішень
Dim_ov написав:
Шановне журі, можете, будь ласка, пояснити чому при компіляції рішень (як мінімум c та c++, інші мови не перевіряв) вимкнені оптимізації (компілятору не передається параметр -O2)?
Мені абсолютно не зрозуміла мотивація такого підходу.
Аргументуємо:
Перевірка проводиться з використанням таких опцій:
g++ -ansi -o solution solution.cc -lm
Зміни не передбачаються.
Dim_ov написав:
1) Переважна більшість олімпіад збирають рішення з оптимізаціями. Включаючи всеукраїнський етап UOI (та й попередні етапи, наскільки мені відомо, у багатьох регіонах проходять на єджаджі, де оптимізації по дефолту ввімкнені і навряд чи їх хтось вимикає).
Це не завжди так, а якщо й так, то такий підхід має ряд як позитивів, так і суттєвих недоліків, зокрема у випадку ЗАОЧНОЇ, з ДОВГОТРИВАЛИМИ турами, олімпіади.
1. Цільова аудиторія олімпіади - не високотреновані аси "спортивного" програмування. Іх, на жаль, серед школярів України дуже небагато. Основна мета - НАВЧАЛЬНА. А в цьому випадку корисніше написати алгртм "руцями", ніж, не розуміючи до кінція як це працює, насмикати готових фіч з STL Перемагають, звичайно, "аси", але й для них теж корисно, що ви чудово продемнстрували своїм дослідженням. Місяць часу на тур...можна й поекспериментувати, якщо ти дійсно ас...Та й задачу ви обрали специфічну (там їх, до речі, було дві), для переважної більшості наших задач подібний ефект не не проявиться так яскраво. До того ж у журі завжди є розв'язок задачі на python, який вкладається у відведений час, а отже, на с++ з STL чи без нього тим більше...
У будь якому випадку всі в однакових умовах.
Поза форумом
#3 2016-12-29 04:36:09
Re: Оптимізації при компіляція рішень
Дякую за коментар.
Позиція зрозуміла, хоча і спірна 
корисніше написати алгоритм "руцями", ніж, не розуміючи до кінція як це працює, насмикати готових фіч з STL
STL я наводив просто у якості яскравого прикладу. Оптимізації можуть сильно міняти картину не тільки з бібліотечними фічами, але й з кодом написаним "руцями" теж (в тому ж MSLPRIM з мого прикладу STL не використовується). До того ж, враховуючи формат олімпіади, учасникам, які хочуть чогось "насмикати, нічого не розуміючи", нічого не завадить насмикати реалізації тих STL-них структур і алгоритмів з інтернету і так само користуватися ними, нічого не розуміючи.
ІМХО, це не дуже правильно - привчати учнів виконувати роботу компілятора "з навчальною метою". Так, уміння правильно інлайнити код вручну, переставляти місцями інструкції та розгортати цикли, щоб ефективніше використовувався кеш процесора, чи краще працювало передбачення розгалужень - це дуже корисні навички, але в основному для розробників компіляторів, а не для учнів... А крім цього модуль оптимізації компілятора більше практично нічого і не робить.
Ну але то таке...
Єдине, що хотів би ще попросити - це вказати десь у правилах опції компіляції, які ви написали вище. По перше, щоб учасники знали, що оптимізацій немає. По-друге, ось цей рядок рядок з поточних правил:
Правила написав:
режим повної сумiсностi з стандартом ANSI
формально не зовсім коректний і може когось вводити в оману. Поточний стандарт ANSI C++ (чи якщо зовсім по феншую, то ISO (куди входить і ANSI) C++) - це С++14. А ключ компіляції -ansi відповідає версії С++98 і має таку назву виключно з історичних причин.
Поза форумом
#4 2016-12-29 17:21:01
- Жюри_Пасихов
- Адміністратор
- Зареєстрований: 2009-11-08
- Повідомлень: 440
Re: Оптимізації при компіляція рішень
Dim_ov написав:
Єдине, що хотів би ще попросити - це вказати десь у правилах опції компіляції, які ви написали вище.
Ця прпозиція доречна - буде зроблено.
Поза форумом