给定IP范围和映射的平面文件,找到给定IP的城市

Question

这是个问题:

给定一个包含映射到某个位置的IP地址范围的平面文本文件(例如192.168.0.0-192.168.0.255 =波士顿,马萨诸塞州),提出一种算法,如果映射,将找到特定IP地址的城市存在.

我唯一的想法是解析文件,并将IP范围转换为整数(如果缺少数字则乘以10/100)并将它们放在列表中,同时还将较低的范围放入哈希作为密钥与作为价值的位置.对列表进行排序并执行略微修改的二进制搜索.如果索引是奇数,则-1并查看散列.如果它是偶数,只需查看哈希.

我计划中的任何错误,或更好的解决方案？

Answer 1

你的方法看起来非常合理.

如果您对进行一些研究/额外编码感兴趣,那么算法将渐近地优于标准二进制搜索技术,该技术依赖于您的IP地址可以被解释为0到2之间的整数³¹ - 1例如,van Emde Boas树和y-Fast Trie数据结构可以实现您在时间O(log log U)中查看的前任搜索操作,其中U是可能的最大IP地址,而不是二进制搜索使用的O(log N)方法.然而,常数因素较高,这意味着无法保证这种方法会更快.但是,作为另一种可能更快的方法,可能值得探索.

希望这可以帮助!

Answer 2

问题是范围的气味,这个问题的一个好的数据结构将是Segment Tree.一些 资源可以帮助您入门.

段树的根可以表示地址(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.对于此特定问题,事实证明Segment Trees将与van-Emde Boas树一样快,并且需要较小的空间(O(N)).
5. 这是一个简单但非平凡的数据结构,它比排序更好,因为它是动态的,并且比van-Emde Boas树更容易向面试官解释.
6. 这是最容易编写代码的非平凡数据结构之一:)

请注意,在某些Segment Tree教程中,它们使用数组来表示树.这可能不是你想要的,因为我们不会填充整个树,所以动态分配节点,就像我们在标准二进制树中一样,是最好的.

Answer 3

在您的示例中，192.168.0.0-192.168.0.255 = 马萨诸塞州波士顿。

条目中两个 IP 地址的前三个八位字节 (192.168.0) 是否相同？另外，前三个八位字节对于一个城市来说是唯一的吗？

如果是的话，那么这个问题就更容易解决了