dado un archivo plano de rangos de IP y asignaciones, encontramos una ciudad dada una IP

Question

Esta es la pregunta:

Dado un archivo de texto plano que contiene un rango de direcciones IP que el mapa a una ubicación (por ejemplo, 192.168.0.0-192.168.0.255 = Boston, MA), proponen un algoritmo que encontrará una ciudad para una dirección IP específica si existe una asignación.

Mi única idea es analizar el archivo, y gire los rangos de IP en sólo enteros (multiplicando por 10/100 si no se encuentra dígitos) y colocarlos en una lista, a la vez que poner el inferior de los rangos en una hash como la clave con la ubicación como un valor. Ordene la lista y realice una búsqueda binaria ligeramente modificada. Si el índice es impar, -1 y mira en el hash. Si es parejo, solo mira en el hash.

¿Alguna falla en mis planes o mejores soluciones?

Answer 1

En su ejemplo, 192.168.0.0-192.168.0.255 = Boston, MA.

¿Los primeros tres octetos (192.168.0) serán los mismos para las dos direcciones IP de la entrada? Además, ¿los primeros tres octetos serán únicos para una ciudad?

Si es así, este problema puede resolverse más fácilmente

Answer 2

Su enfoque parece perfectamente razonable.

Si está interesado en investigar un poco/codificación adicional, hay algoritmos que superan de manera asintótica la técnica de búsqueda binaria estándar que se basa en el hecho de que sus direcciones IP pueden interpretarse como enteros en el rango de 0 a 2 - 1. Por ejemplo, las estructuras de datos van Emde Boas tree y y-Fast Trie pueden implementar la operación de búsqueda predecesora que está viendo en el tiempo O (log log U), donde U es la dirección IP máxima posible, en oposición a Enfoque O (log N) que utiliza la búsqueda binaria. Sin embargo, los factores constantes son más altos, lo que significa que no hay garantía de que este enfoque sea más rápido. Sin embargo, podría valer la pena explorarlo como otro enfoque que podría ser aún más rápido.

Espero que esto ayude!

Answer 3

El problema huele a rangos, y una de las buenas estructuras de datos para este problema sería un árbol de segmentos. Someresources para ayudarlo a comenzar.

La raíz del árbol del segmento puede representar las direcciones (0.0.0.0 - 255.255.255.255). El subárbol izquierdo representaría las direcciones (0.0.0.0 - 127.255.255.255) y el subárbol derecho representaría el rango (128.0.0.0 - 255.255.255.255), y así sucesivamente. Esto continuará hasta que alcancemos rangos que no pueden subdividirse más. Digamos, si tenemos el rango 32.0.0.0 - 63.255.255.255, mapeado a alguna ciudad arbitraria, será un nodo hoja, no subdividiremos ese rango cuando lleguemos allí, y lo etiquetaremos a la ciudad específica.

Para buscar una asignación específica, seguimos el árbol, tal como lo hacemos en un árbol de búsqueda binaria. Si su IP se encuentra en el rango del subárbol de la izquierda, muévase al subárbol de la izquierda, de lo contrario, muévase al subárbol de la derecha.

Las buenas partes:

1. no es necesario tener todos los sub-árboles, sólo se suman los sub-árboles que se requieren.Por ejemplo, si en sus datos, no hay una ciudad mapeada para el rango (0.0.0.0 - 127.255.255.255), no construiremos ese subárbol.
2. Somos eficientes en el uso del espacio. Si todo el rango está asignado a una ciudad, ¡crearemos solo el nodo raíz!
3. Esta es una estructura de datos dinámica. Puede agregar más ciudades, rangos de división más adelante, etc.
4. Realizará un número constante de operaciones, ya que la profundidad máxima del árbol sería 4 x log2 (256) = 32. Para este problema en particular, resulta que Segment Trees sería tan rápido como van-Emde Boas árboles, y requieren menos espacio (O (N)).
5. Esta es una estructura de datos simple, pero no trivial, que es mejor que ordenar, porque es dinámico y más fácil de explicar a su entrevistador que los árboles de van-Emde Boas.
6. Esta es una de las más sencillas estructuras de datos no triviales para codificar :)

Tenga en cuenta que en algunos tutoriales árbol segmento, que utilizan matrices para representar el árbol. Esto probablemente no es lo que quieres, ya que no estaríamos poblando todo el árbol, por lo que asignar nodos dinámicamente, como lo hacemos en un árbol binario estándar, es lo mejor.

Answer 4

Mi única idea es analizar el archivo, y gire los rangos de IP en sólo enteros (multiplicando por 10/100 dígitos si no se encuentra) ...

Si después de este enfoque, es probable que desea multiplicar por 256^3, 256^2, 256 y 1 respectivamente para A, B, C y D en una dirección ABCD Eso efectivamente recrea la dirección IP como un número sin firmar de 32 bits.

... y colóquelos en una lista, al mismo tiempo que coloca los valores más bajos en el hash como la clave con la ubicación. Ordene la lista y realice una búsqueda binaria ligeramente modificada. Si el índice es impar, -1 y mira en el hash. Si es parejo, solo mira en el hash.

que sugeriría la creación de una matriz contigua (a std::vector) que contiene estructuras con las gamas inferior y superior (y nombre de la ubicación - discute más adelante). Luego, como dices, puedes buscar binariamente un rango que incluya un valor específico, sin molestias impares o pares.

Usar el extremo inferior del rango como clave en un hash es una forma de evitar tener espacio para los nombres de ubicación en el conjunto, pero dado el número promedio de caracteres en el nombre de una ciudad, el tamaño probable de los punteros, una elección entre una tabla hash escasamente poblada y largas listas de desplazamiento para buscar en segmentos alternativos sucesivos o más direccionamiento indirecto a contenedores de longitud arbitraria; necesitaría estar bastante desesperado para molestarse en intentarlo. En primer lugar, almacenar la ubicación en struct junto con el rango de valores de IP parece bueno.

Alternativamente, podría crear un árbol basado en p. los valores IP de 0-255 individuales: cada nivel en el árbol podría ser una matriz de 256 valores para indexación directa o una matriz ordenada de valores poblados. Eso puede reducir el número de comparaciones de valores de IP que probablemente deba realizar (O (log2N) a O (1)).