Здравствуй, Хабр! Вот небольшой пост о проходящем Russian Code Cup 2016, а точнее, мои соображения, на которые меня натолкнула одна из задач разогревочного раунда.
Технические правила проведения раунда подробно описаны здесь. Не буду их все копипастить, выделю только два момента:
- Присылать решения можно на разных языках (Java, Python, C/C++/C++11, C#, Perl, PHP, Ruby, D)
- Все задачи имеют лимит по времени исполнения решений
Речь пойдёт о задаче "A" Секретный код (прямая ссылка):
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт
Описание
Сейчас Марти находится в прошлом и хочет вернуться домой в 1985 год. Он уже влюбил своих родителей друг в друга и нашёл плутоний. Всё, что осталось сделать, — это включить машину времени и отправиться в путь. Здесь Марти ждёт ещё одно испытание. Чтобы включить машину времени, нужно ввести секретный код. Секретный код знает только Док. Марти известно, что все символы, из которых состоит код, различны, а также он знает количество символов. Пока Марти ждёт приезда Дока, он пытается угадать код и вводит различные комбинации символов.
Ваша задача — написать программу, которая для каждого запроса Марти выдает два числа — количество верных символов, которые стоят на своих позициях, и количество символов, которые встречаются в коде, но стоят на неверных позициях.
Формат входных данных
В первой строке находится строка s — секретный код. Код состоит из латинских заглавных букв и цифр, все символы в коде различные.
Во второй строке содержится натуральное число n (1 ≤ n ≤ 105) — количество попыток Марти.
В каждой из следующих n строк содержится очередная комбинация, которую вводит Марти. Комбинации также состоят из латинских заглавных букв и цифр. Символы в каждой комбинации различны. Длина каждой комбинации совпадает с длиной секретного кода.
Формат выходных данных
Для каждого запроса Марти выведите два числа a и b, где a — количество верных, b — количество символов, которые встречаются в коде, но стоят на неверных позициях.
Пример
Входные данные:
BACKTO1985
3
BACKTO1958
BACKON1985
TOYEAR1985
Выходные данные:
8 2
8 1
4 3
Решение
Задачка не из сложных. Практически никаких ухищрений для решения не требуется.
Перебираем комбинации, сравнивая каждую с секретным кодом посимвольно. Очередная пара символов совпала — увеличиваем a, иначе смотрим, присутствует ли данный символ в секретном коде (ищем за условно логарифмическое время, предварительно разложив секретный код на ассоциативный массив с ключами-символами). Если присутствует, увеличиваем b.
Вот простое решение на Ruby, (код именно тот, что я отправил во время раунда):
input = STDIN.read.split("\n") code = input[0] tries_count = (input[1]).to_i tries = input[2,tries_count] #puts code #puts tries_count #puts tries code_a = code.split(//) code_h = Hash[code_a.map {|x| [x, 1]}] #puts code_h tries.each do |t| total_right = 0 missed_right = 0 t.each_char.with_index do |c, i| if c == code[i] total_right += 1 else missed_right += 1 if code_h.has_key?(c) end end puts "#{total_right} #{missed_right}" end
Каково же было моё неудовольствие, когда я получил в ответ Time Limit Exceeded. Притом, самое забавное, что потом, под конец раунда, я решил для интереса ещё раз отправить точно такой же код. И он прошёл проверку! То есть, скорей всего, исполнялся на грани лимита времени. Я решил разобраться.
Написал идентичное (насколько это возможно) решение на C++:
#include <iostream> #include <map> int main() { std::string code; std::getline(std::cin, code); std::string s_tries_count; std::getline(std::cin, s_tries_count); int tries_count = std::stoi(s_tries_count); std::string tries[tries_count]; for(int i = 0; i < tries_count; i++) { std::getline(std::cin, tries[i]); }; std::map<std::string, int> code_h; for (char& c : code) { std::string s(c, 1); code_h.insert(std::make_pair(s, 1)); } for (std::string t : tries) { int total_right = 0; int missed_right = 0; for (int i = 0; i < t.length(); i++) { if (t[i] == code[i]) { total_right++; } else { std::string s(t[i], 1); if (code_h.count(s)) { missed_right++; } } } std::cout << total_right << " " << missed_right << std::endl; } return 0; }
Да, код скверен, не в последнюю очередь из-за этих преобразований из char в string, но я ставил цель максимально повторить решение на Ruby.
<КапитанОчевидность>
Так вот, код на C++ исполнялся значительно быстрее, чем на Ruby!
</КапитанОчевидность>
Вскоре после окончания раунда стали доступны наборы тестовых входных данных, и я скачал тест №17, на котором получил в первый раз Time Limit Exceeded, в нём было кодовое слово OPYB4R7JNHVGEKC3I6285TU90ASMFXLZW1D и 94432 комбинации.
Замеры производительности
C++ собирал на g++ 4.8.4
Скрипт:
g++ -x c++ -std=c++0x -O2 -o ./solution1.a solutions/solution1.cpp && echo "solution1.cpp (with diff):" && time diff <( cat data/output.txt ) <( ./solution1.a < data/input.txt ) && echo "solution1.cpp (> dev/null):" && time ./solution1.a < data/input.txt > /dev/null
Вывод:
solution1.cpp (with diff): real 0m0.411s user 0m0.341s sys 0m0.171s solution1.cpp (> dev/null): real 0m0.347s user 0m0.319s sys 0m0.028s
Версия Ruby 1.9.3
Скрипт:
echo "Ruby base solution (with diff):" && time diff <( cat data/output.txt ) <( ruby solutions/solution1.rb < data/input.txt ) && > /dev/null echo "Ruby base solution (> dev/null):" && time ruby solutions/solution1.rb < data/input.txt > /dev/null
Вывод:
Ruby base solution (with diff): real 0m1.422s user 0m1.416s sys 0m0.009s Ruby base solution (> dev/null): real 0m1.413s user 0m1.404s sys 0m0.008s
Как видите, более чем трёхкратная разница по времени работы, при, в целом, аналогичном алгоритме.
Весь набор (входные/выходные данные по тесту №17, исходники cpp и rb, скрипты для сборки и замера производительности (только *nix)) запилил сюда на гитхаб.
Можно подумать, что я еще не закрыл тег КапитанОчевидность, но вот выводы, которые я выношу на обсуждение:
- Ситуация совершенно справедливая для реального мира, где каждому языку — свои задачи
- Однако, в олимпиадном программировании, я считаю эту ситуацию несколько несправедливой
- В чемпионате, перед нами словно раскладывают инструменты на выбор, мол, бери любой, дело вкуса; на деле, одни из инструментов заметно эффективнее других
- Да, безусловно, у Ruby есть выигрыш в скорости и простоте написания непосредственно кода, когда решение в голове уже найдено
- Но, бьюсь об заклад, если посадить рядом одинаково компетентных специалистов по Ruby и C++, первый, если и напишет код быстрее, то только в рамках статистической погрешности
- Устанавливая жесткие рамки на время исполнения кода решения, организаторы, фактически, делают одни языки "равнее" других, хотя, казалось бы, цели олимпиады немного другие
- Что бы я предложил со своей колокольни? Оценивать вычислительную сложность решений (Big O)! Смотреть, как изменяется скорость исполнения кода при росте количества входных данных n. И, например, если время исполнения растет ощутимее быстрее линеарифмического
O(n log(n)) , решение отбраковывать - И да, нужна будет защита от хитрых товарищей с решениями в константные O(100500)
Спасибо за внимание! Очень интересно будет узнать ваши мнения по теме.
ссылка на оригинал статьи https://habrahabr.ru/post/282431/
Добавить комментарий