26.04.2016 07:06
augur 20 2300 Источник

Здравствуй, Хабр! Вот небольшой пост о проходящем 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 ) &&
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)

Спасибо за внимание! Очень интересно будет узнать ваши мнения по теме.

Комментарии (20)


  1. ServPonomarev
    26.04.2016 11:51
    #8869869
    +1

    Конечно, правила не запрещают участвовать в Формуле-1 на самосвалах. Но все почему-то используют болиды.

    Если нормально реализованные с алгоритмической точки зрения решения работают на грани тайм-аута — разумно увеличить тайм-аут. А игры со сложностью не нужны — слишком сложно их реализовать — что приведёт к обидам и непониманию участников.


    1. GarryC
      26.04.2016 11:55
      #8869879
      +1

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


    1. augur
      26.04.2016 12:26
      #8869935

      Согласен, что тесты, оценивающие сложность подобным образом, реализовать в целом труднее. Но если не принимать во внимание затраты на их реализацию, разве не была бы такая система оценки качества решений более точной и достоверной?
      А участникам будет даже полезно прийти к осознанию, что масштабируемые проблемы в принципе не будут решаться наращиванием железа и ассемблерными вставками, если в основе лежит алгоритм с O(n2)+ сложностью.


  1. GarryC
    26.04.2016 11:59
    #8869889
    +1

    А по поводу собственно проблемы — Вы не думаете, что создание булевого массива и простая проверка в нем на наличие символа была бы намного быстрее, чем использование хэша? Задача то совсем хэша не требует.


    1. augur
      26.04.2016 12:14
      #8869913

      Простите, не очень понял. Вы предлагаете оперировать кодом символа, как числовым индексом, чтобы присваивать True соответствующим ячейкам, а потом один раз посчитать количество True в массиве?
      Я, кстати, пробовал запускать решение на Ruby без работы с хешем (то есть, второй результат переставал подсчитываться). Скорость выполнения улучшилась с 1400ms до 1100ms, что по-прежнему слишком далеко от C++.


      1. GarryC
        26.04.2016 12:37
        #8869961

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


  1. romagjan
    26.04.2016 12:57
    #8870007

    Если для проверки есть ли символ в коде использовать словарь, то проверка каждого набора кода за линейное время решается.


    1. augur
      26.04.2016 13:00
      #8870015

      Верно! Есть ли способ решить быстрее? Мы ведь, если не ошибаюсь, нахождением пересечения множеств занимается тут.


  1. AterCattus
    26.04.2016 16:05
    #8870738
    +1

    Что-то мне кажется, что языки типа Ruby и PHP в этом конкурсе разве что просто до кучи, чтобы дать поучаствовать кому-то просто интереса ради, не соревнуясь.


    1. MiXei4
      26.04.2016 17:29
      #8870982
      +2

      Я участвовал ради интереса на PHP. В первый раз даже футболку получил.
      А вот во второй раз я не смог сдать ни одной задачи — был и TL и, кажется, какая-то проблема с чтением строк, которой раньше не было.
      В этот раз на первой задаче я опять получил TL.
      Очень неинтересно участвовать, когда у тебя сплошные TL :) Особенно когда ты знаешь, что на другом языке это решение пройдёт с запасом даже на слабом компе…


  1. StopKran
    27.04.2016 17:01
    #8873222
    +1

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

    Мысль номер один, если компания например внутри больше пишет на c++/java и например хантит таких разработчиков, то компании не выгодно ориентироваться при разработке задач пишущих на более медленных языках.

    Далее, действительно разработчики задач, периодически сталкиваются с такой проблемой, то что решение за квадрат на c++ работает например почти как решение за n log n на python. Да, обычно удается решить эти проблемы, небольшой корректировкой условия задачи, и придумыванием качественных тестов. Но не всегда.

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

    Так же обычно на более медленных языках, все же можно соптимизировать задачу, до такой степени что она не будет получать TL. Но тут надо понимать, что творится под капотом у самого языка взамен того, что бы реализовывать что-либо самому на более низкоуровневых языках.

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


    1. MiXei4
      27.04.2016 17:25
      #8873272
      +1

      Хорошая олимпиадная задачка не должна сильно зависеть от языка программирования. Если на одном языке она решается в 3 строки, а на другом приходится выдумывать собственные структуры данных и лезть под капот, то с этим надо что-то делать. Иногда для какого-то конкретного языка увеличивают ограничение по времени, например. В случае с простой задачей можно просто снизить общие ограничения в тестах и тд.

      Решение олимпиадных задач и «хороший разработчик» — это разные вещи.


    1. augur
      27.04.2016 17:30
      #8873280

      Спасибо за развернутый ответ!
      Согласен, что, скорей всего, можно укладываться в Time Limit и на "медленных" языках. Но тут встает дилемма — тратить дополнительное время на упреждающую сверх-оптимизацию, или сдавать обычное (не наивное, адекватное) решение с риском получить штрафное время за превышение. Лично для себя я сделал вывод, что олимпиады придётся писать на "быстрых" языках.


      Что касается, оценки сложности, вот простейшая методика, которая мне видится жизнеспособной:


      • Допустим у нас три теста, входных данных в каждом из них n1=100, n2=1000, n3=10000
      • Решение прошло три теста за времена t1, t2, t3
      • И если t3/ t2 >> t2/t1 значит ресурсоемкость решения неудовлетворительная

      P.S. Возможно, найду время и напишу прототип, чтобы проверить методику на практике.


  1. horo
    27.04.2016 17:30
    #8873282
    +1

    Пожалуйста, скажите мне, что название статьи случайно, и не содержит в себе скрытых намёков…


    1. kylt_lichnosti
      27.04.2016 19:22
      #8873574

      Практически прямым текстом написано. Какие уж тут намеки.


  1. daeto
    28.04.2016 15:26
    #8875058
    +2

    Я не участвовал в этом разогревочном раунде, не знаю Ruby, но, может, мои пять копеек будут полезны.


    Ну, по порядку.


    1. Вполне реально сдать эту задачу на Ruby или другом скриптовом языке из представленных так, чтобы она уложилась по времени. 2 секунды! Это же очень много для тупого линейного алгоритма (а как минимум прочитать придётся все данные, так что быстрее линейного в этой задаче ничего нет).
    2. Все языки равны, но некоторые — равнее. Там, где в C++ можно написать не слишком оптимальный ввод-вывод или ещё что-то подобное, и это скомпенсируется скоростью работы, на Ruby (Java, PHP, Python) нужно быть более аккуратным, например.
    3. В вашем решении вы считываете вход целиком в массив. Зачем? Это ведь очевидно ухудшает скорость и не даёт никаких преимуществ по сравнению с чтением и выводом результата построчно.
    4. Вы итерируетесь по символам в строке. Однако, раз вы пишете на Ruby, то должны знать, что char и byte в нём — совершенно разные вещи (кодировка, внутренне представление, вот это всё). И итерироваться по byte быстрее. В пределах задачи даже не очень понятно, зачем использовать char.
    5. Использовать для проверки вхождения символа в строку массив, а не хеш — ну, просто здесь не обязателен хеш (по факту, мало влияет на скорость)
    6. В обоих ваших решениях на Github есть ошибка. Вы неправильно обрабатываете концы строк. И, видимо, вы сами сгенерировали "правильный" ответ к 17 тесту, поскольку он не правильный. Понять это просто, если, например, посмотреть на последнюю строку output.txt. Там стоит "36 0", но в секретном коде только 35 символов.
    7. В архиве, предоставленном жюри, есть и корректные тесты с правильными ответами, и чекер для проверки — почему вы не используете их?

    Итак, поменяв чуть-чуть в соответствии с вышеуказанным ваше решение, я получил на своей машине результат ~0.45 сек. на 17 тесте вместо 1.2-1.4 сек. Это очень близко к вашему результату на C++ (хотя, конечно, его точно так же можно улучшить). Но это уже достаточно большой отрыв от указанного TL, чтобы можно было легко сдать.


    Все изменения прислал вам в виде pull request. Ещё туда добавил оригинальные файлы и фикс решения на C++ (без улучшений, просто чтобы проходили оригинальные тесты).


    Это всё можно считать упреждающей оптимизацией, да. Но по факту — это базовые вещи, касающиеся любого инструмента и культуры программирования. Да, даже олимпиадное программирование требует владения инструментом на некотором уровне. И да, там даже есть свои трюки на тему скорости, которые иногда стоит применять. И да, писать на C++ или хотя бы Java такое проще (но, опять же, народ не из топа спокойно и на других языках сдаёт — и ничего, норм).


    1. augur
      28.04.2016 17:07
      #8875296

      Вы совершенно правы!


      Как я уже писал выше, использование хешей в составленном тогда мною решении хоть и не оптимально, но не существенно — полное исключение работы с ним уменьшило время выполнения всего на 0.3с.
      Полагаю, столь большое ускорение (с 1.4с -> до 0.4с) Вашего решения на Ruby, с фактическим приближением по скорости решения на C++, связано главным образом с оптимизацией работы с STDIN. (Ну и работа с байтами вместо символов, хотя привычнее рассуждать, раз строки, значит юникод, значит оперируем символами) В моём решении существовало два этапа — преобразование сырых данных из STDIN с сохранением в промежуточные переменные, и, непосредственно, работа с ними.


      Ваше решение вселяет в меня надежду, что Ruby может потягаться в таких ситуациях с Си =)


      P.S. чуть подправил compare.sh, а то не собирался


      1. daeto
        28.04.2016 17:52
        #8875396
        +1

        Больше всего влияет на скорость исполнения замена работы с char на byte.


        Улучшения по работе с IO дают прирост 0.2-0.3 сек на данном тесте. Но, к слову, если бы было более жёсткое ограничение по памяти, то аккуратная работа с IO имеет ещё больше смысла, далеко не во всех задачах получится прочитать весь вход в массив.


        Проверить очень просто:


        Если вернуть итерацию по char и сравнивать ch == code[i], то получаем время ~1.0 сек. Это связано с тем, что code[i] создаёт новую строку каждый раз + индексация Unicode-строки работает медленнее, чем индексация честного массива.


        Если вернуть итерацию по char, но все символы из code заранее положить в массив code_chars, соответственно, сравнивать ch == code_chars[i], то получаем время ~0.75 сек. Тут мы избавились от создания новых строк каждый раз, но сравнение строк всё равно осталось, вероятно, оно работает медленнее, чем сравнение чисел.


        (Все рассуждения — довольно общие, я действительно не знаю, как работает Ruby, просто посмотрел доки только что).


        То есть, решая более общую задачу (для произвольных строк Unicode-символов стоит использовать char и Hash, конечно), вы получите и большее время работы. Это вполне логично. Но в исходной задаче есть ограничения на входные данные, на символы, из которых состоят строки. Грамотно воспользовавшись этими ограничениями, вы получите достаточно быстрый алгоритм. Ну и логично, что решение большей части олимпиадных задач так или иначе предусматривает работу с ограничениями (одно дело посчитать 10!, и совсем другое — 10000!).


        P.S. Да, точно, ту строку в compare.sh добавил в самом конце и не проверил — очепятался, спасибо.


        1. augur
          28.04.2016 19:16
          #8875500

          По правде говоря, я впервые со школьных времён принял участие в подобном мероприятии. Пришлось заново открывать для себя влияние стресса от столь экстремально сжатых сроков разработки на образ мышления. В обычных условиях, я всё это время потрачу только на вдумчивое чтение условий :)


          Кстати, забавная вещь, только что выяснил, #rstrip работает немного быстрее #chomp, хотя для работы с STDIN рекомендуется второй вариант, как более каноничный. И что еще забавнее, вариант t.rstrip!.each_byte.with_index do… работает аж на 5%~ быстрее, чем t.rstrip.each_byte.with_index do ..., хотя казалось бы, второй вариант это более правильный method chaining и вообще Ruby way… Вероятно это объясняется, что при #rstrip! не копируется новая строка в памяти, а уменьшается счетчик длины текущей. Полезно наверное знать и помнить такие частности, но иногда излишнее заглядывание под капот отвлекает. Нужны менее дырявые абстракции :)


          Кстати, сейчас поразмыслил, Ваш вариант хоть и проходит все указанные тесты, но имеет некоторую слабину: игнорируется передаваемое общее число комбинаций-попыток, и значит STDIN будет читаться до победного конца. Достаточно добавить одну лишнюю строчку в конце входных данных, не увеличивая передаваемое число комбинаций-попыток, и проверка провалится.


          1. daeto
            28.04.2016 19:20
            #8875504

            Ну, в олимпиадных задачах мы полагаемся на корректность входных данных и их формата, поэтому так написал.
            Но, конечно, можно и счётчик строк с выходом из цикла по достижении tries_count добавить, временной сложности это особо не добавит :)