Упражнение 24: Быстрый маршрут URL

Исходник: Упражнение 24: Быстрый поиск URL

Переводчик: Фэйлон

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Мы завершаем раздел о данных структурах и алгоритмах, и будем использовать эти структуры для решения реальных задач. Я написал несколько веб-серверов, и одной постоянной проблемой является сопоставление пути URL со "событиями". Вы встретите эту проблему во всех веб-фреймворках, веб-серверах и любом другом, которое должно маршрутизировать информацию на основе иерархических ключей. Когда ваш веб-сервер получает URL /do/this/stuff/, он должен определить, какие части могут быть связаны с какими действиями или конфигурациями. Если вы настроили веб-приложение на /do/, то что должен сделать ваш сервер с /this/stuff/: считать это ошибкой, передать его веб-приложению? А если существует директория в /do/this/? Как быстро распознать неправильные URL, чтобы вы не должны были обрабатывать огромные запросы, которые не существуют?

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

Часто задаваемые вопросыСначала убедитесь, что вы понимаете, что такое URL и как ими работать. Если нет, я рекомендую потратить время на создание небольшого приложения Flask с некоторыми сложными маршрутами. Вот маршруты, которые вы будете реализовывать.

Далее вам следует выполнить следующие шаги:

• Создайте простой базовый класс URLRouter, от которого будут производиться все реализации. Вы должны иметь возможность выполнять следующие операции с этим URLRouter:

  • Добавление нового URL с связанной им объектом.
  • Получение полного совпадения URL. Поиск /DO/THIS/STUFF/ вернёт только точно совпадающее значение.
  • Получение лучшего совпадения URL. Поиск /DO/THIS/STUFF/ будет совпадать с /DO/, если это единственное совпадение.
  • Получение всех объектов, начинающихся с данного URL.
  • Получение самого короткого совпадающего объекта URL. Поиск /DO/THIS/STUFF/ вернёт /DO/, а не /DO/THIS/.
  • Получение самого длинного совпадающего объекта URL. Поиск /DO/THIS/STUFF/ вернёт /DO/THIS/, а не /DO/.

• Используйте TSTree для создания подкласса URLRouter, так как это самый простой способ. Убедитесь, что вы протестировали следующее:

  • Случайные URL различных длин и пути в TSTREE и то, что вы ищете.
  • Поиск части пути в разных ситуациях.
  • Полностью отсутствующий путь.+ Присутствие и отсутствие очень длинных путей.

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

• Затем попробуйте использовать DoubleLinkedList, BSTree, Dictionary и Python's dict для реализации. Убедитесь, что ваш универсальный тест применим ко всем этим.

• После завершения начните анализировать производительность этих реализаций при выполнении различных операций. Цель — сравнить скорость работы TSTree с другими структурами данных. Он может победить большинство других структур, но возможно, что Python dict будет быстрее в большинстве случаев, так как он оптимизирован для использования в Python. Вы можете даже сделать прогнозы относительно того, какая структура данных обеспечивает наилучшую производительность для каждого действия.## Исследовательское обучение

• Я пропустил SuffixArray, потому что он похож на TSTree, но для его использования вам потребуется добавить те же операции. Реализуйте его и посмотрите, как он сравнивается.

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

Глубокое изучение

Если вы хотите углубиться в алгоритмы и структуры данных, я настоятельно рекомендую книгу «Руководство по проектированию алгоритмов» Стивена С. Скиены. Книга написана на C, поэтому вам может понадобиться прочитать «Прощай, глупый способ учиться C», чтобы иметь возможность её использовать. Кроме того, это отличная книга, поскольку она охватывает как теорию, так и практическую реализацию анализа производительности алгоритмов и структур данных.