English version of this post here.
Как вы, возможно, знаете, наша компания проводит программу интерншипа в нескольких странах, включая и Украину. В Киеве мы проводим обучение второй год подряд, и весьма довольны результатами, которые мы получили в 2009.
Так вот, время от времени, чтобы держать студентов в форме да и просто с целью получить удовольствие, вместо запланированной лекции мы предлагаем ребятам заняться программированием. Hack hour.
В прошлую пятницу мы предложили написать программу, которая
- читает текст из stdin
- разбивает его на слова (слово определяется как непрерывная последовательность [A-Za-z0-9])
- … и выводит в stdout отсортированный по алфавиту список слов (lowercased), вместе со списком строк, на которых слово встречается
Довольно просто, не так ли? Так как я хотел быть уверен, что знаю, как решать задачу и примерно представляю, с какими трудностями можно столкнуться, перед занятием я запустил студию и набросал решение на чистом C++, без оптимизаций – просто как proof of concept. Заняло 30 минут чистого времени. В общем, мы ожидали, что студенты справятся с задачей примерно за час и у нас еще останется время, чтобы дать им материал лекции.
Как бы не так.
Как оказалось, только один человек из 10 смог решить задачу, не покидая аудитории. Да, я знаю, что программисты не умеют программировать, но, все же, мы ждали несколько лучшего результата.
Чтобы быть честным, хочу сказать, что почти решили задачу несколько человек. Почти, да не совсем. Все программы, кроме одной, упомянутой выше, не справились с большим 40 Мб файлом за разумное время (первая версия моего кода прожевала его за 22 секунды на Core i5-750). Очевидно, большинство ипользовало не те контейнеры, линейный поиск, что, на больших объемах данных привело к сложности O(n2), и мощности процессора просто не хватило.
Не буду тыкать пальцами, но все же – “знайте фундаментальные структуры данных и основные алгоритмы“. Потратьте немного времени, почитав о них, попрактикуйтесь, и болшинство задач, с которыми вам доведется столкнуться, покажутся вам гораздо менее сложными. И вы сможете потратить свое ценное время на другие, гораздо более интересные задачи и проблемы.
Это было только начало истории. Продолжение следует.
Tags: algorithms, cqg, education