Лексика решений TopCoder
Замечательный плагин к TopCoder Arena под названием KawigiEdit сохраняет код, который я сдавал (или пытался сдать, или хотел сдать) на TopCoder с февраля 2009 года. С тех пор накопилось свыше мегабайта кода на C++, и я решил его проанализировать на предмет того, какие слова в нем встречаются чаще, а какие реже.
Однобуквенные переменные: i3584 j1515 n1237 k507 s449 c438 a426 m359 x346 p322 y317 r316 v272 l249 b205 d203 t193 N161 h106 f104 C80 g80 w71 L66 A65 B62 u61 e61 q57 K50 R50
Читать код программистов на современном Фортране тяжело не потому, что Фортран непонятный язык, а потому, что на современном Фортране пишут обычно всякие вычислительные научные программы. На вопрос о том, что такое переменная gq1, естественно следующий из чтения такого кода, как правило, следует ответ: читай соответствующий пейпер, там эта величина так обозначена. К слову, привычные для нас обозначения i и j для счетчиков циклов ведут свою родословную как раз с Фортрана, в ранних версиях которого тип переменной определялся ее первой буквой. В языке Бейсик, выросшем из Фортрана, вплоть до Visual Basic 6.0 были операторы вида DefInt I-N, который как раз включает поведение, как в Фортран IV.
На Топкодере обычно i, j, k, l - счетчики, я выделил их цветом для удобства; переменные вроде n, m, w, h, x, y - размеры или координаты чего-то. Остальные же, видимо, специфичны для решения задачи и не могут быть названы лучше, если не считать хорошим для задачи на 5 минут название count_of_foxes_from_left_side_of_current_right_binary_search_border. Другие однобуквенные слова встречались реже 50 раз :)
Знакомые переменные: result732 dp391 res358 len184 ilen121 M121 mask96 rem94 step62 num61 ni51 nj50 ok48 ndp45 pos44 idx42 ss42 bit39 jlen30 iend30 wave29 nmask29 cost28 adj27 nwave23 suffix21 prefix21 ny20 graph18 level17 dx16 width15 time14 nx14 sign14 shi14 even14 shj14 eq13 digit13 dir13 odd13 price13 di12 inside12 dj12 dy12 answer11 area10 score10 shy10 shx10 height10 finish8 up8 weight6 nmasks5 jend4
Некоторые переменные я бы назвал вновь точно так же, если бы переписывал задачу заново. К счетчикам и координатам, как правило, в нагрузку идут парные переменные, которые хранят изменения, новые значения, границу просматриваемого интервала, количество оставшихся итераций.
Ряд переменных накапливает и хранит результат разной степени готовности. Другие выдают с головой используемый прием программирования, будь то динамическое программирование, DFS, BFS, поиск по битовым маскам. Задачи на окрестности фон Неймана и Мура (соответственно 4- и 8-окрестность) настолько часты, что для них у почти каждого олимпиадника нотация работы с ними пришла к стандарту.
Часть названий являются обычными словами, настолько часто употребительными в условии или процессе решения, что называть их как-то иначе - лишь путать себя. Ну а M просто всегда равен 1000000007. Или 1000000009. Не пытайтесь это понять, если вы не в теме :)
Зарезервированные слова: for1125 if1011 return715 class308 public308 else177 const105 true103 false101 while58 break50 sizeof43 do17 static14 continue14 typedef10 unsigned9 case9 struct5 operator4 this2 template2 throw2 enum2 typename2 try1 catch1 switch1
В современном стандарте C++ 59 зарезервированных слов, не считая встроенных типов. В олимпиадах обычно используется не больше половины, и в основном это старые добрые древние инструкции управления исполнением.
А ключевые слова class и public просто всегда незримо присутствуют в каждом решении на TopCoder :) Среди всего прочего, эта схема позволяет прогонять все тесты над кодом игрока за один запуск программы, в отличие, например, от ACM, где, даже если решению хватит кванта времени на тест, а то и все тесты, все равно нужно будет выполнить, как правило, 50-100 запусков исполнимого файла.
Типы: int3407 vector834 long752 string477 double234 size_t221 bool122 pair85 char74 map48 set45 void25 iterator25 stringstream12 istringstream10 complex7 npos4 const_iterator2 priority_queue1 bitset1
В настоящее время дискуссии про языки программирования свелись к их самой скучной части - системе типов. Олимпиадные задачи почти всегда используют несколько простых встроенных типов и пару стандартных контейнеров, ничуть не теряя в сложности. Несложно догадаться, почему число вхождений слова long четное :) Попробуйте найти в этом списке один не-тип.
Методы: size371 end271 begin257 push_back193 second131 length123 first121 find56 substr51 insert45 erase23 clear20 empty19 assign15 back13 pop_back7 top6 pop5 c_str4 rend4 push2 rbegin2 reserve1 front1 append1 resize1
Не слишком широко и множество используемых методов классов стандартной библиотеки. Но ими следует владеть идеально, ничуть не смущаясь от вопроса «как и почему отличаются асимптотики list::size в реализациях STL из VS и gcc».
Прочее из STL: make_pair82 sort77 count65 swap42 numeric_limits42 accumulate26 copy20 greater20 max_element17 ostream_iterator13 unique13 istream_iterator10 reverse9 distance7 back_inserter5 upper_bound5 find_if5 next_permutation4 count_if4 min_element3 inserter1 stable_sort1 set_intersection1 lower_bound0
Алгоритмы и конструкторы типов (в том числе функторов). Действительно никто не хочет писать, пожалуй, только сортировку, а в ручной реализации остального просто нет ничего интересного; писать ли цикл для всяких count или вызов STL обычно решает левая нога. Или правая.
Вообще же полагаю, что я использую больше STL, чем средний топкодер, например, почти не встречал в чужом коде numeric_limits::max() для начального значения переменной, которая накапливает минимум - все используют магические константы вида 100500, фу. А upper_bound, увы, сильно бесполезнее, чем мог бы быть с няшными бустовскими функторами, так что если задача с бинпоиском, то придется писать бинпоиск.
Немного страшного: memset36 atoi4 __builtin_popcount3 sprintf1
Всегда хочется избежать всякой гадости из Си или специфичного gcc интринсика для подсчета числа единичных битов в числе, но уж больно он удобный.
Математика: max171 min159 abs79 sqrt21 pow18 log7 floor4 exp2 ceil2 cos1 sin1 conj1 hypot1 atan1
Вопреки распространенным опасениям, в спортивном программировании не так много математики. Ну, по крайней мере, непрерывной :)
Говорящие функции: get68 dfs49 gcd27 solve16 kuhn11 binomial10 bfs10 check8 calc8 kuhn_dfs6 calculate4 isprime4 fft4 kun3 go3 ispali2 fact2
Многие неосведомленные граждане полагают, что спортивное программирование это про вызов готовых алгоритмов, а значит, у кого заготовка больше, тот и выигрывает. На самом деле конкретных алгоритмов здесь целых два: алгоритм Куна поиска максимального паросочетания (нельзя так просто взять и называть его всегда одинаково) и БПФ (быстрое преобразование Фурье).
Некоторые математические функции, которые есть в Maple, бывает, приходится реализовывать достаточно часто, но все же недостаточно, чтобы вставлять их в шаблон KawigiEdit. Плюс вместо ручной реализации gcd для int (return b ? gcd(b, a % b) : a;) можно просто использовать __gcd, которая является вспомогательной функцией для std::rotate в gcc STL. А в MS STL нет, сволочи!
Если вы хотите поиграться со своими сырцами, но парсер/анализатор писать не хотите, вот скрипт, с помощью которого я подготовил этот пост (расширение .php новый владелец Народа uCoz запрещает).
Однобуквенные переменные: i3584 j1515 n1237 k507 s449 c438 a426 m359 x346 p322 y317 r316 v272 l249 b205 d203 t193 N161 h106 f104 C80 g80 w71 L66 A65 B62 u61 e61 q57 K50 R50
Читать код программистов на современном Фортране тяжело не потому, что Фортран непонятный язык, а потому, что на современном Фортране пишут обычно всякие вычислительные научные программы. На вопрос о том, что такое переменная gq1, естественно следующий из чтения такого кода, как правило, следует ответ: читай соответствующий пейпер, там эта величина так обозначена. К слову, привычные для нас обозначения i и j для счетчиков циклов ведут свою родословную как раз с Фортрана, в ранних версиях которого тип переменной определялся ее первой буквой. В языке Бейсик, выросшем из Фортрана, вплоть до Visual Basic 6.0 были операторы вида DefInt I-N, который как раз включает поведение, как в Фортран IV.
На Топкодере обычно i, j, k, l - счетчики, я выделил их цветом для удобства; переменные вроде n, m, w, h, x, y - размеры или координаты чего-то. Остальные же, видимо, специфичны для решения задачи и не могут быть названы лучше, если не считать хорошим для задачи на 5 минут название count_of_foxes_from_left_side_of_current_right_binary_search_border. Другие однобуквенные слова встречались реже 50 раз :)
Знакомые переменные: result732 dp391 res358 len184 ilen121 M121 mask96 rem94 step62 num61 ni51 nj50 ok48 ndp45 pos44 idx42 ss42 bit39 jlen30 iend30 wave29 nmask29 cost28 adj27 nwave23 suffix21 prefix21 ny20 graph18 level17 dx16 width15 time14 nx14 sign14 shi14 even14 shj14 eq13 digit13 dir13 odd13 price13 di12 inside12 dj12 dy12 answer11 area10 score10 shy10 shx10 height10 finish8 up8 weight6 nmasks5 jend4
Некоторые переменные я бы назвал вновь точно так же, если бы переписывал задачу заново. К счетчикам и координатам, как правило, в нагрузку идут парные переменные, которые хранят изменения, новые значения, границу просматриваемого интервала, количество оставшихся итераций.
Ряд переменных накапливает и хранит результат разной степени готовности. Другие выдают с головой используемый прием программирования, будь то динамическое программирование, DFS, BFS, поиск по битовым маскам. Задачи на окрестности фон Неймана и Мура (соответственно 4- и 8-окрестность) настолько часты, что для них у почти каждого олимпиадника нотация работы с ними пришла к стандарту.
Часть названий являются обычными словами, настолько часто употребительными в условии или процессе решения, что называть их как-то иначе - лишь путать себя. Ну а M просто всегда равен 1000000007. Или 1000000009. Не пытайтесь это понять, если вы не в теме :)
Зарезервированные слова: for1125 if1011 return715 class308 public308 else177 const105 true103 false101 while58 break50 sizeof43 do17 static14 continue14 typedef10 unsigned9 case9 struct5 operator4 this2 template2 throw2 enum2 typename2 try1 catch1 switch1
В современном стандарте C++ 59 зарезервированных слов, не считая встроенных типов. В олимпиадах обычно используется не больше половины, и в основном это старые добрые древние инструкции управления исполнением.
А ключевые слова class и public просто всегда незримо присутствуют в каждом решении на TopCoder :) Среди всего прочего, эта схема позволяет прогонять все тесты над кодом игрока за один запуск программы, в отличие, например, от ACM, где, даже если решению хватит кванта времени на тест, а то и все тесты, все равно нужно будет выполнить, как правило, 50-100 запусков исполнимого файла.
Типы: int3407 vector834 long752 string477 double234 size_t221 bool122 pair85 char74 map48 set45 void25 iterator25 stringstream12 istringstream10 complex7 npos4 const_iterator2 priority_queue1 bitset1
В настоящее время дискуссии про языки программирования свелись к их самой скучной части - системе типов. Олимпиадные задачи почти всегда используют несколько простых встроенных типов и пару стандартных контейнеров, ничуть не теряя в сложности. Несложно догадаться, почему число вхождений слова long четное :) Попробуйте найти в этом списке один не-тип.
Методы: size371 end271 begin257 push_back193 second131 length123 first121 find56 substr51 insert45 erase23 clear20 empty19 assign15 back13 pop_back7 top6 pop5 c_str4 rend4 push2 rbegin2 reserve1 front1 append1 resize1
Не слишком широко и множество используемых методов классов стандартной библиотеки. Но ими следует владеть идеально, ничуть не смущаясь от вопроса «как и почему отличаются асимптотики list::size в реализациях STL из VS и gcc».
Прочее из STL: make_pair82 sort77 count65 swap42 numeric_limits42 accumulate26 copy20 greater20 max_element17 ostream_iterator13 unique13 istream_iterator10 reverse9 distance7 back_inserter5 upper_bound5 find_if5 next_permutation4 count_if4 min_element3 inserter1 stable_sort1 set_intersection1 lower_bound0
Алгоритмы и конструкторы типов (в том числе функторов). Действительно никто не хочет писать, пожалуй, только сортировку, а в ручной реализации остального просто нет ничего интересного; писать ли цикл для всяких count или вызов STL обычно решает левая нога. Или правая.
Вообще же полагаю, что я использую больше STL, чем средний топкодер, например, почти не встречал в чужом коде numeric_limits::max() для начального значения переменной, которая накапливает минимум - все используют магические константы вида 100500, фу. А upper_bound, увы, сильно бесполезнее, чем мог бы быть с няшными бустовскими функторами, так что если задача с бинпоиском, то придется писать бинпоиск.
Немного страшного: memset36 atoi4 __builtin_popcount3 sprintf1
Всегда хочется избежать всякой гадости из Си или специфичного gcc интринсика для подсчета числа единичных битов в числе, но уж больно он удобный.
Математика: max171 min159 abs79 sqrt21 pow18 log7 floor4 exp2 ceil2 cos1 sin1 conj1 hypot1 atan1
Вопреки распространенным опасениям, в спортивном программировании не так много математики. Ну, по крайней мере, непрерывной :)
Говорящие функции: get68 dfs49 gcd27 solve16 kuhn11 binomial10 bfs10 check8 calc8 kuhn_dfs6 calculate4 isprime4 fft4 kun3 go3 ispali2 fact2
Многие неосведомленные граждане полагают, что спортивное программирование это про вызов готовых алгоритмов, а значит, у кого заготовка больше, тот и выигрывает. На самом деле конкретных алгоритмов здесь целых два: алгоритм Куна поиска максимального паросочетания (нельзя так просто взять и называть его всегда одинаково) и БПФ (быстрое преобразование Фурье).
Некоторые математические функции, которые есть в Maple, бывает, приходится реализовывать достаточно часто, но все же недостаточно, чтобы вставлять их в шаблон KawigiEdit. Плюс вместо ручной реализации gcd для int (return b ? gcd(b, a % b) : a;) можно просто использовать __gcd, которая является вспомогательной функцией для std::rotate в gcc STL. А в MS STL нет, сволочи!
Если вы хотите поиграться со своими сырцами, но парсер/анализатор писать не хотите, вот скрипт, с помощью которого я подготовил этот пост (расширение .php новый владелец Народа uCoz запрещает).