Учитывая плоский файл IP-адресов и отображений, найдите город с IP-адресом

Question

Это вопрос:

Учитывая плоский текстовый файл, который содержит диапазон IP-адресов, которые отображаются в местоположение (например, 192.168.0.0-192.168.0.255 = Бостон, Массачусетс), придумайте алгоритм, который найдет город для определенного IP-адреса, если сопоставление существует.

Моя единственная идея - проанализировать файл и превратить диапазоны IP-адресов в просто целые числа (умножить на 10/100, если в нем отсутствуют цифры) и поместить их в список, а также поместить нижний из диапазонов в хеш, как ключ с местоположением в качестве значения. Сортируйте список и выполните слегка измененный двоичный поиск. Если индекс нечетный, -1 и посмотрите в хэш. Если это даже, просто посмотрите в хэш.

Какие-нибудь ошибки в моих планах или лучшие решения?

Answer 1

Ваш подход кажется вполне разумным.

Если вы заинтересованы в небольшом исследовании / дополнительном кодировании, есть алгоритмы, которые будут асимптотически превосходить стандартную технику двоичного поиска, основанную на том факте, что ваши IP-адреса могут интерпретироваться как целые числа в диапазоне от 0 до 2 ³¹ - 1. Например, в структурах данных и y-Fast Trie *1005* Ван-Эмде можно реализовать операцию поиска предшественника, которую вы просматриваете в время O (log log U), где U - максимально возможный IP-адрес, в отличие от подхода O (log N), который использует бинарный поиск. Постоянные факторы выше, однако, это означает, что нет никакой гарантии, что этот подход будет быстрее. Тем не менее, возможно, стоит изучить другой подход, который потенциально может быть еще быстрее.

Надеюсь, это поможет!

Answer 2

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

Корень дерева сегментов может представлять адреса (0.0.0.0 - 255.255.255.255).Левое поддерево будет представлять адреса (0.0.0.0 - 127.255.255.255), а правое поддерево - диапазон (128.0.0.0 - 255.255.255.255) и т. Д.Это будет продолжаться до тех пор, пока мы не достигнем диапазонов, которые не могут быть разделены далее.Скажем, если у нас есть диапазон 32.0.0.0 - 63.255.255.255, сопоставленный с каким-либо произвольным городом, это будет конечный узел, мы не будем далее подразделять этот диапазон, когда прибудем туда, и отметим его для конкретного города.

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

Хорошие части:

1. Вам не нужно иметь все поддеревья, только добавить необходимые поддеревья.Например, если в ваших данных нет города, отображенного для диапазона (0.0.0.0 - 127.255.255.255), мы не будем строить это поддерево.
2. Мы занимаем мало места.Если весь диапазон сопоставлен с одним городом, мы создадим только корневой узел!
3. Это динамическая структура данных.Вы можете добавить больше городов, разделить диапазоны позже и т. Д.
4. Вы будете выполнять постоянное количество операций, поскольку максимальная глубина дерева будет 4 x log2 (256) = 32. Для этогоВ частности, выясняется, что деревья сегментов будут такими же быстрыми, как деревья Ван-Эмде Боаса , и потребуют меньше места (O (N)).
5. Это просто, но нетривиальная структура данных, которая лучше, чем сортировка, потому что она динамическая, и ее легче объяснить вашему интервьюеру, чем деревья Ван-Эмде Боаса.
6. Это одна из самых простых нетривиальных структур данных для кода:)

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

Answer 3

Моя единственная идея - разобрать файл и превратить диапазоны IP-адресов в просто целые числа (умножить на 10/100, если в нем отсутствуют цифры) ...

Если следовать этому подходу, вы, вероятно, захотите умножить на 256 ^ 3, 256 ^ 2, 256 и 1 соответственно для A, B, C и D в адресе A.B.C.D. Это эффективно воссоздает IP-адрес как 32-разрядное число без знака.

... и поместите их в список, а также поместите нижний из диапазонов в хеш в качестве ключа со значением местоположения в качестве значения. Сортируйте список и выполните слегка измененный двоичный поиск. Если индекс нечетный, -1 и посмотрите в хэш. Если это даже, просто посмотрите в хэш.

Я бы предложил создать непрерывный массив (std::vector), содержащий структуры с нижним и верхним диапазоном (и названием местоположения - обсуждается ниже). Тогда, как вы говорите, вы можете выполнить двоичный поиск диапазона, включающего определенное значение, без каких-либо нечетных / четных хлопот.

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

Кроме того, вы можете создать дерево, например, на основе отдельные значения IP 0-255: каждый уровень в дереве может быть либо массивом из 256 значений для прямой индексации, либо отсортированным массивом заполненных значений. Это может уменьшить количество сравнений значений IP, которые вам, вероятно, понадобятся (от O (log2N) до O (1)).

Answer 4

В вашем примере 192.168.0.0-192.168.0.255 = Бостон, Массачусетс.

Будут ли первые три октета (192.168.0) одинаковыми для обоих IP-адресов в записи? Кроме того, первые три октета будут уникальными для города?

Если это так, то эту проблему можно решить легче