Еще в 2011 году, когда мне наскучила моя работа, я начал искать новые варианты. Во время моих поисков моя подруга Даниэль (с которой я построил Novlet и Bitlet годами ранее) переслал мне ссылку на страницу карьеры компании, в которой он работал в то время, IT Software .
В то время как Google находился в процессе приобретения программного обеспечения ITA, у ITA все еще было несколько открытых вакансий, на которые они хотели нанять. Однако, в отличие от Google, они требовали, чтобы кандидаты решали задачу программирования , прежде чем претендовать на инженерные должности.
Проблемы, которые требовалось решить, были на удивление разнообразными, начиная от чисто алгоритмических задач и заканчивая более широкими проблемами, которые все еще требовали некоторого глубокого технического понимания. Просматривая варианты, я остановился на проблеме, которая меня заинтриговала, потому что я подумал, что она похожа на проблему, которую я, возможно, однажды захочу решить в реальном мире, и, казалось, пытался проверить широту своих знаний (это требовало хороших навыков полного стека), а также моего понимания глубоких технических деталей.
У меня сохранились хорошие воспоминания о том времени, которое я потратил на изучение этой проблемы и поиск решения. Когда я закончил, я узнал о новом классе структур данных (деревьях суффиксов), получил более глубокое понимание внутренних функций Java. Год спустя я получил предложение о работе отчасти из-за этой головоломки.
Постановка задачи
Краткое изложение задачи заключалось в следующем:
Мгновенный поиск
Напишите веб-приложение Java, которое обеспечивает “мгновенный поиск” по объектам, перечисленным в Национальном реестре исторических мест. Вместо того, чтобы ждать, пока пользователь нажмет кнопку отправки, ваше приложение будет динамически обновлять результаты поиска по мере ввода входных данных. Мы предоставляем файл nrhp.xml.gz , который содержит выбранную информацию из базы данных регистра.
База данных Ключевым компонентом вашего серверного приложения является эффективная структура данных в памяти для поиска свойств (написанная на чистом Java). Загрузка хорошего решения может занять несколько минут, но на современном ПК оно может ответить на запрос менее чем за 0,1 мс. (Обратите внимание, что последовательный поиск по всем свойствам, вероятно, слишком медленный!) Входные данные соответствуют свойству, если оно находится в любой позиции в пределах названий, адреса или города+штата этого свойства. Совпадения не чувствительны к регистру и учитывают только символы A-Z и 0-9, например, ввод “mainst” соответствует “200 S Main St”, а “red” соответствует “Lakeshore Dr.” Обратите внимание, что JVM сервера будет настроен с максимальным объемом кучи 1024M. Пожалуйста, соответствуйте интерфейсам, указанным в nrhp.jar при создании вашей базы данных.
Сервлет Ваш сервлет должен принимать входную строку в качестве параметра запроса к запросу GET. Результаты должны включать информацию для предварительно настроенного количества свойств (например, 10), общее количество совпадений, существующих в базе данных, и время, затраченное вашим алгоритмом поиска. Ваш сервлет должен быть без состояния, т.Е. не зависит от какой-либо информации о сеансе для каждого пользователя. Разбивайте свои дополнительные результаты на страницы в качестве бонуса!
Клиент Ваша веб-страница должна получить доступ к сервлету с помощью объекта XMLHttpRequest JavaScript. По мере ввода пользователем текста ваш интерфейс должен многократно уточнять список результатов поиска без обновления страницы. Ваш графический интерфейс не должен быть сложным, но должен быть отполирован и хорошо выглядеть.
Пожалуйста, отправьте файл WAR, инструкции по настройке, ваш исходный код и любые комментарии по вашему подходу. Ваше приложение будет протестировано с помощью Tomcat на 64-разрядной версии J2SE от Sun и последней версии Firefox.
Клиент
Я начал создавать это с самого низа пользовательского интерфейса. В кратком описании головоломки упоминается использование XMLHttpRequest , поэтому я избегал использования каких-либо клиентских библиотек (функциональность, которую меня попросили создать на клиенте, была, в конце концов, довольно простой). Скриншот, прилагаемый к краткому описанию головоломки, включал только текстовое поле для поискового запроса и список результатов.
Я написал функцию для прослушивания нажатий клавиш, отправки асинхронного вызова на сервер и отображения ответа, как только он вернется. К 2011 году я уже некоторое время занимался программированием веб-приложений и смог реализовать эту функциональность менее чем за час работы.
Код веб-приложения и сервлета
Уровень сервлета также был довольно простым, поскольку все, что ему нужно было, – это обрабатывать входящий XML-запрос и отправлять его в то, что в кратком описании называлось database . Опять же, здесь меньше часа работы.
На этом уровне я также написал код для анализа базы данных строк для индексации из XML-файла, содержащего данные из Национального реестра исторических мест. Сервер Tomcat запускал этот код при загрузке моего веб-приложения и использовал полученные данные для построения структуры данных, которую можно было использовать в качестве индекса для обеспечения функции быстрого поиска, необходимой для создания. Мне нужно было разобраться с этим дальше.
Поиск подходящей структуры данных
Неудивительно, что это самая сложная часть головоломки, на которой я сосредоточил свои усилия больше всего. Как указано в описании проблемы, последовательный цикл по списку ориентиров не будет работать (это займет намного больше времени, чем целевой порог в 0,1 мс). Мне нужно было найти структуру данных с хорошей сложностью во время выполнения, связанную с операциями поиска.
Я потратил некоторое время на размышления о том, как бы я реализовал структуру данных, позволяющую сократить время поиска, необходимое в этом случае. Наиболее распространенный вариант быстрого поиска, с которым я был знаком, хэш-таблица , не сработал бы сразу с этой проблемой, потому что он ожидал бы, что операция поиска будет содержать полную строку ключа. Однако в этой задаче я хотел иметь возможность искать записи в моем индексе, даже если задана неполная подстрока, что потребовало бы от меня сохранения всех возможных подстрок в качестве ключей в таблице.
Сделав несколько набросков на бумаге, казалось разумным ожидать, что tries будет работать здесь лучше.
Деревья суффиксов
Когда я исследовал структуры данных, обеспечивающие быстрые операции поиска по частичным строкам, я наткнулся на ряд статей, ссылающихся на деревья суффиксов, обычно используемые в вычислительной биологии и обработке текста, предлагающие операции поиска с линейным временем выполнения относительно длины строки для поиска для (в отличие от длины строки для поиска внутри ).
Простые деревья суффиксов, однако, предназначены для поиска совпадений заданной последовательности строк-кандидатов в пределах одной более длинной строки, в то время как эта головоломка вращалась вокруг немного другого варианта использования: вместо того, чтобы иметь одну длинную строку для поиска совпадений, мне нужно было иметь возможность находить совпадения в нескольких строках. К счастью, я прочитал еще немного и нашел большое количество статей, документирующих структуры данных, называемые обобщенными деревьями суффиксов , которые делают именно это.
Основываясь на том, что я узнал до сих пор, я был убежден, что этот тип дерева может соответствовать моим требованиям но мне предстояло преодолеть две вероятные проблемы:
- Деревья суффиксов, как правило, занимают гораздо больше места, чем строки, которые они индексируют, и, основываясь на постановке задачи, “JVM сервера будет настроен с максимальным объемом кучи 1024 М”, и это необходимо для размещения сервера Tomcat, всего моего веб-приложения и дерева, которое я хотел построить.
- Большая часть сложности работы с деревом суффиксов заключается в построении самих деревьев. В то время как в кратком описании головоломки прямо говорилось, что загрузка моего решения может занять “несколько минут”, я не хотел, чтобы рецензенту моего решения пришлось ждать несколько часов, прежде чем он сможет протестировать мою заявку.
Алгоритм Укконена для построения линейного дерева времени выполнения
К счастью, я нашел популярный алгоритм генерации деревьев суффиксов за линейное время (линейный по общей длине индексируемых строк), описанный Укконеном в статье, опубликованной в 1995 году ( Онлайн–построение деревьев суффиксов ).
Мне потребовалась пара дней прерывистой работы (помните: я работал над этим по ночам и выходным – тогда у меня была другая дневная работа), чтобы заставить мое дерево суффиксов работать так, как ожидалось.
Интересно, что некоторые проблемы на этом этапе были связаны с совершенно неожиданной темой: статья Укконена включает полный алгоритм, написанный в псевдокоде, и хорошую прозу с подробным описанием основных шагов. Однако тот же самый псевдокод написан на таком высоком уровне абстракции, что потребовалась некоторая работа, чтобы преобразовать его в быстрый и эффективный Java-код.
Кроме того, алгоритм псевдокода написан в предположении, что мы работаем с одной строкой, представленной в виде массива символов, поэтому многие из описанных там операций имеют дело с индексами внутри этого большого массива ( например k и i в описанной выше процедуре).
Вместо этого в моей реализации Java я хотел как можно больше работать с объектами String . Мной двигало несколько разных причин:
- Java реализует интернирование строк по умолчанию – представление подстрок путем ручного манипулирования индексами внутри массива символов, представляющих содержащую строку, не дает преимуществ в памяти. JVM уже делает это прозрачно для нас.
- Работа со ссылками
Stringпривела к созданию кода, который был для меня гораздо более разборчивым. - Я знал, что моим следующим шагом будет обобщение алгоритма для обработки построения индекса на нескольких строках, и это было бы намного сложнее, если бы мне пришлось иметь дело с низкоуровневыми спецификациями того, какой массив символов представляет ту или иную входную строку.
Обобщенные Деревья Суффиксов
Это последнее соображение оказалось критическим: обобщение дерева суффиксов, которое у меня было до этого момента, для работы с несколькими входными строками было довольно простым. Все, что мне нужно было сделать, это убедиться, что узлы в моем дереве могут нести некоторую полезную нагрузку , обозначающую, какая из строк в индексе будет соответствовать заданной строке запроса. Этот этап занял пару часов работы, но только потому, что у меня были хорошие модульные тесты.
На данный момент все выглядело великолепно. Я потратил, может быть, пару дней на чтение статей о деревьях суффиксов и еще пару дней на написание всего кода, который у меня был до сих пор. Я был готов попробовать запустить свое приложение с входными данными, предоставленными в кратком описании головоломки: весь Национальный реестр исторических мест, XML-канал общим объемом в несколько сотен мегабайт.
Испытание огнем: ошибка OutOfMemoryError
Первый запуск моего приложения был разочаровывающим. Я запустил Tomcat и развернул архив своего веб-приложения, который запустил синтаксический анализ базы данных XML, предоставленной в качестве входных данных, и начал создавать обобщенное дерево суффиксов для использования в качестве индекса для быстрого поиска. Не прошло и двух минут после построения дерева суффиксов, как сервер вышел из строя с ошибкой OutOfMemoryError .
1024 мегабайт, которые у меня были, было недостаточно.
К счастью, пару лет назад я работал с клиентом, которому было трудно поддерживать работу своего сайта электронной коммерции в разгар сезона праздничных покупок. Их серверы постоянно выходили из строя, потому что у них заканчивалась память. Это, в свою очередь, привело меня к тому, чтобы научиться читать и понимать дампы памяти JVM.
Я никогда не думал, что буду использовать этот навык для своих личных проектов, но эта головоломка доказала, что я ошибался. Я запустил visualvm и начал искать наибольший вклад в потребление памяти.
Не потребовалось много времени, чтобы обнаружить, что существует несколько неэффективных шаблонов распределения памяти. Многие из этих элементов вряд ли были бы проблемой для обычного приложения, но все они в конечном итоге изменили ситуацию в данном случае из-за огромного размера создаваемой древовидной структуры данных.
Микро-память- оптимизация
Анализ нескольких дампов кучи подсказал мне ряд возможных изменений, которые привели бы к экономии памяти, обычно за счет дополнительной сложности или перехода от реализации структуры данных общего назначения (например, карт) к эквиваленту специального назначения, адаптированному к этому варианту использования и его ограничениям.
Я оценил возможные оптимизации по их ожидаемой отдаче от инвестиций (т.Е. сравнил значение экономии памяти с дополнительной сложностью реализации, более медленным временем выполнения и другими факторами) и реализовал несколько пунктов в верхней части списка.
Наиболее значимые изменения касались оптимизации объема памяти дерева суффиксов узлов : учитывая, что мое приложение требовало построения очень большого графика (с десятками тысяч узлов), любая предельная экономия, получаемая за счет более эффективного представления узлов, в конечном итоге имела бы существенное значение.
Свойство узлов дерева суффиксов заключается в том, что никакие исходящие ребра не могут быть помечены строками, разделяющими префикс. На практике это означает, что структура данных, реализующая узел, должна содержать ссылку на набор исходящих ребер, обозначенных первым символом на метке.
Первая версия моего решения использовала HashMap<Символ, ребро> для представления этого. Как только я посмотрел на дамп кучи, я заметил, что это представление было крайне неэффективным для моего варианта использования.
Hashmap в Java инициализируются с коэффициентом загрузки 0,75 (это означает, что они обычно резервируют память как минимум на 25% больше пар ключ | значение, чем они содержат в любой заданной точке) и, что более важно, с достаточной начальной емкостью для хранения 16 элементов.
Последний пункт особенно плохо подходил для моего варианта использования: поскольку я индексировал строки с использованием английского алфавита (26 различных символов), карта размером 16 была бы достаточно большой, чтобы вместить более половины возможных символов, и часто была бы расточительной.
Я мог бы смягчить эту проблему, настроив параметры размера и коэффициента нагрузки но я подумал, что смогу сэкономить еще больше памяти, переключившись на специализированный тип коллекции. Реализации карты по умолчанию, включенные в стандартную библиотеку, требуют, чтобы типы ключей и значений были ссылочными типами, а не собственными типами (т.Е. карта имеет ключ Character вместо char ), а ссылочные типы, как правило, намного менее эффективны с точки зрения памяти (поскольку их представление более сложное).
Я написал реализацию карты специального назначения под названием Edge Bag , в которой было несколько настроек:
- сохраненные ключи и значения и два параллельных массива,
- массивы начинались бы с малого и постепенно увеличивались, если бы при необходимости занимали больше места,
- полагался на линейное сканирование для операции поиска, если пакет содержал небольшое количество элементов, и переключался на использование двоичного поиска по отсортированному набору ключей, если пакет содержал более нескольких единиц,
- использованный
байт [](вместосимвол []) для представления символов в ключах. 16-разрядный тип Javacharзанимает в два раза больше места, чемbyte. Я знал, что все мои ключи были символами ASCII, поэтому я мог бы отказаться от поддержки Unicode здесь и мог бы сэкономить еще немного, перейдя к более узкому диапазону значений.
Некоторые более подробные сведения об этом и других изменениях, направленных на сокращение объема памяти моей реализации дерева суффиксов, приведены в разделе Оптимизация для конкретных задач страницы проекта дерева суффиксов.
Вывод
Когда я протестировал свою программу после оптимизации памяти, я был рад увидеть, что она соответствует требованиям проблемы: поиск был молниеносным, менее 0,1 мс с использованием машины, которая у меня была тогда (на базе процессора Intel Q6600 с частотой 2,4 ГГц), и модульные тесты, которые я написал, дали мне хорошую уверенность в том, что программа работает так, как требуется.
Я упаковал решение в виде военного архива, написал краткий файл README с изложением конструктивных соображений и инструкций по его запуску (просто разверните на голом сервере Tomcat 6) и отправил его по электронной почте. Почти год спустя я собирал чемоданы и переезжал в Амстердам, чтобы присоединиться к Google (которая к тому времени приобрела программное обеспечение ITA).
Я в немалой степени обязан этим тому удовольствию, которое я получил от этой головоломки с кодированием.
Когда я думаю о том, как мне понравилось время, потраченное на создание мгновенного поиска, я думаю, что это должно быть потому, что для этого требовалась как широта (для разработки приложения с полным стеком, хотя и простого), так и глубина (для исследования наилучшей структуры данных для работы и последующей оптимизации по мере необходимости). Это позволило мне объединить мое образование специалиста широкого профиля с моим интересом к теоретическим основам информатики.
Тщательный выбор определения ограничений как памяти, так и времени выполнения в качестве части требований к задаче сделал задачу намного более увлекательной. Когда первая версия, которую я закодировал, не сработала, я смог повторно использовать свой опыт работы с инструментами профилирования памяти, чтобы определить, какие оптимизации следует выполнить. В то же время я получил более глубокое понимание внутренних функций Java и узнал гораздо больше о деталях реализации, которые до тех пор просто воспринимались как должное.
Когда ОН вышел на пенсию, мгновенный поиск (и другие головоломки программирования 1 ), я решил выпустить Обобщенное дерево суффиксов Java с открытым исходным кодом для использования другими. Несмотря на множество оптимизаций, связанных с конкретными проблемами, которые я в итоге сделал, он достаточно универсален и использовался в нескольких других приложениях с тех пор, как я его создал, что дает мне еще одну вещь, за которую я должен быть благодарен.
Я пишу о программировании, разработке программного обеспечения и техническом лидерстве. Вы можете подписаться на меня в твиттере для получения дополнительных сообщений, подобных этому.
Этот пост был первоначально опубликован на Этот пост был первоначально опубликован на 30 сентября 2019 года
В то время как исходная страница больше не подключена к Сети, у машины обратной связи все еще есть снимок исходной страницы с исходным выбором прошлых головоломок программирования . Они по-прежнему являются отличным способом проверить свои навыки программирования. ↩
Оригинал: “https://dev.to/abahgat/the-programming-puzzle-that-landed-me-a-job-at-google-1pc0”