Как и обещал, в этом посте я расскажу о первом домашнем задании, которое нам дали на курсах «повышения IT-компетенций» по «программированию». Начну с того, что нам сказали, что это классическое задание, которое выполняют все, прошедшие собеседование и принятые на работу в «Симбирсофт». На нем они понимают, какой стиль программирования использует в компании и как следует писать код, чтобы лучше влиться в коллектив и не тормозить работу компании.

А само задание чрезвычайно простое: написать на любом не веб-ориентированном языке (желательно C#, C++, Java) программу вида myprog.exe text.txt dict.txt, принимающую на входе два файла. В первом – text.txt – содержится произвольный текст; во втором – dict.txt – лежит словарь. Задача: программа должна в результате работы создать html-файл, в котором все слова текста из text.txt, которые есть в dict.txt, выделены жирным шрифтом. Словоформы обрабатывать не надо. Выделять следует только те слова, которые целиком находятся в dict.txt.

Стоит также отметить, что эта задача хороша тем, что она очень легко расширяема и тут можно постоянно придумывать разные улучшения, модифицировать её, усложнять. Например, потом нам намекнули на возможность задания типа «приделать к этой программе графический пользовательский интерфейс (GUI)» и отметили, что следует предусмотреть возможность расширения функционала. А также заикнулись, что оба файла теоретически могут весить по несколько мегабайт.

На мой взгляд, задачка любопытная и очень напоминает олимпиадную. Самое приятное, что она имеет много различных вариантов решения различной сложности. Но сначала, следует определиться с тем, как оценивать алгоритмическую сложность решений. Я предлагаю предположить худший вариант (т.е. что каждый файл имеет размер в мегабайтах). Если предположить, что в среднем одно слово имеет длину 7 знаков, то в пяти мегабайтном файле их будет около 750 000. Т.е. нам следует рассчитывать на порядок 10^6; плюс, сравнение двух слов в худшем случае будет происходить за 7 операций (равно длине слова). И пусть n – количество слов в файле text.txt, а m – в dict.txt. Теперь можно будет спокойно представить сложность алгоритма в конкретных цифрах.

А теперь перейдем к вариантам решения.

Первый, самый простой способ, который может прийти в голову – это тупой перебор. Встретилось слово в тексте – пошли искать его в словаре. Или наоборот, из словаря – в текст. Сложность здесь получается громадной – O(n!*m) в первом случае и O(n*m!) – во втором.

Второй способ – это некоторая оптимизация первого: хранить словарь в ассоциативном контейнере. Как правило, они реализуются в виде бинарного дерева. Соответственно, поиск элемента будет осуществляться за O(log m). Неприятный нюанс нас здесь будет ждать только при добавлении элемента в массив (при загрузке словаря в память) – на добавление нового элемента уходят те же (log m) операций. Итого, общая сложность задачи получится O((m+ n)*log m).

Третий способ – хранить словарь в хэш-таблице. Вы спросите, какая тут разница относительно второго способа? А разница очень простая – в данном случае время поиска элемента не будет зависеть от их количества. Только от сложности самой хэш-функции. Т.е., если сложность хэш-функции – G, то общая сложность алгоритма получится O(G*(n+m)). Из чего получается, что при достаточно простой хэш-функции, этот способ немного эффективнее по времени второго.

Еще можно предложить четвертый способ, хоть он и мало отличается по сложности от второго. Он заключается в том, что стоит отсортировать словарь по алфавиту и искать нужный элемент бинарным поиском в массиве. Сложность сортировки у нас – (m*log m), бинарного поиска – (log m). Итого, сложность задачи выходит O((m+n)*log m). Следует отметить, что quick-sort, который тут удобно использовать, на практике обычно работает эффективнее других алгоритмов с O(n*log n). Поэтому, этот способ должен быть несколько быстрее второго.

Кстати, для четвертого способа можно придумать и ряд улучшений. Например, за один прогон (O(n)) записать, с какого индекса какая буква начинается, и в дальнейшем запускать поиск только в нужном диапазоне, а не по всему массиву. Это должно в несколько раз повысить эффективность поиска.
Наверное, что-то можно придумать и для улучшения алгоритма прохода по тексту text.txt, но я не могу ничего предложить для этого.

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

PS: Сам я еще не определился, каким алгоритмом я буду решать эту задачу и как сделать решение «красивее». Как только определюсь, скорее всего, это выльется в новый пост. Надеюсь, что он будет также с комментариями преподавателя о том, «как надо было делать» с его точки зрения.