#algorithm #performance #data-structures
Вопрос:
Можете ли вы предложить наиболее эффективный алгоритм для решения приведенной ниже проблемы:
Если существует несколько IP-адресов, как бы вы классифицировали их по разным городам, которым они принадлежат. Если диапазон для Нью — Йорка составляет: 134.123.65.5-135.123.124.21. и тогда IP-адрес 134.126.232.12 не принадлежит Нью-Йорку, а IP-адрес 134.123.89.45 действительно принадлежит Нью-Йорку.
Мой подход :
- Преобразуйте каждый диапазон в следующий формат : 134*(256^3) 123*(256^2) 65*(256^1) 5*(256^0)
- Сохраните указанное значение на карте дерева с отображением — (преобразованный адрес, имя города)
- Когда вам задан запрос, преобразуйте адрес в аналогичный формат и найдите map.floorKey(запрос)
Пожалуйста, скажите мне, подходит ли подход или существует лучший подход.
Комментарии:
1. Я не уверен, что понимаю: Диапазон: 134.123.x.x — 13 5.123 .x.x. И тогда 134.126.x.x не принадлежит. Но 134.123.x.x принадлежит. Это опечатка в ДИАПАЗОНЕ? Должно ли это быть 134.x.x.x — 134.x.x.x?
2. Если ваш подход работает, то этот вопрос не по теме. Если он не работает, вам следует спросить о проблеме, с которой вы столкнулись, предоставив свой код, пример ввода, соответствующий ожидаемый результат и то, что дает ваше решение вместо этого. Если вы не знаете, сработает ли это, то, пожалуйста, приложите все усилия, чтобы попробовать это, чтобы вы попали в один из двух ранее упомянутых случаев.
Ответ №1:
Использование дерева уже достаточно эффективно, поскольку результирующая сложность поиска одного IP-адреса заключается O(log n) в том, что n-это количество диапазонов (при условии, что нет перекрытия). Общая сложность O(m log n) связана с m IP-адресами.
Поскольку диапазоны, скорее всего, не изменяются динамически, более быстрым решением является использование предварительно построенного отсортированного массива. Сортированные массивы особенно быстры для нескольких диапазонов и должны быть быстрее даже для относительно большого количества диапазонов, поскольку они непрерывны и более компактны в памяти.
Другим, вероятно, более быстрым решением является использование таблиц поиска (LUT). Действительно, доступы LUT есть O(1) (для данного IP-адреса). Вы можете создать LUT с 65536 элементами для первой половины IP ( x*256 y для x.y.z.w ). Для каждого элемента LUT вы можете сохранить идентификатор в другом массиве, хранящем информацию о структуре диапазона. Если для данного элемента LUT существует несколько диапазонов, вы можете перебирать их или использовать другой LUT, если есть большое количество городов с одинаковым IP-адресом в верхней части. Если количество городов невелико (например. Результирующая сложность должна быть примерно O(m) такой .
Если у вас много IP-адресов и городов, лучшим решением, вероятно, является сортировка городов заранее один раз (если это возможно), затем сортировка всех IP-адресов, а затем повторение IP-адресов и городов одновременно, как при слиянии. Этот алгоритм выполняется там O(n m) , где n-количество городов (или диапазонов) и m количество IP-адресов. Это решение должно быть намного быстрее, чем использование LUT для большого количества городов.