需要一个算法倒塌网络块范围内成超范围名单 [英] need an algorithm for collapsing netblock ranges into lists of superset ranges

问题描述

我的数学福失败了我！我需要降低网络的有效方式范围为超集，如如果IP的I输入范围列表：

My math-fu is failing me! I need an efficient way of reducing network ranges to supersets, e.g. if I input list of IP ranges:

• 为1.1.1.1 2.2.2.5
• 1.1.1.2 2.2.2.4到
• 10.5.5.5到155.5.5.5
• 10.5.5.6到10.5.5.7

我想回到取值范围如下：

I want to return the following ranges:

• 为1.1.1.1 2.2.2.5
• 10.5.5.5到155.5.5.5

注意：输入列表不排序（尽管他们可能是？）。用简单的方式来做到这一点是检查各范围的每个列表中，查看是否输入范围，x是一个子集，并且如果是的话，用插入范围×。但是，当你插入一个新的范围可能是现有的范围的超集，所以你要检查现有的范围，看看他们是否可以折叠（例如，从我的名单中删除）。

Note: the input lists are not ordered (though they could be?). The naive way to do this is to check every range in the list to see if the input range x is a subset, and if so, NOT insert range x. However, whenever you insert a new range it might be a superset of existing ranges, so you have to check the existing ranges to see if they can be collapsed (e.g., removed from my list).

推荐答案

这是段计算联合。一个优化算法（在O（n日志（N）））包括在具体操作如下：

This is a union of segments computation. An optimal algorithm (in O(nlog(n))) consists in doing the following:

1. 在排序的所有端点（起点和终点）的列表L（每个端点都应该知道它属于段）。如果一个端点是等于一个起点，起点应被视为比enpoint小。
2. 经过排序列表L由左到右，并保持数 LE-RE ，其中 LE 的是，你已经通过了离开端点的数量， RE 的是，你已经通过正确的端点的数量。
3. 每次 LE-RE 达到零，你是在段的连接工会结束时，你知道你已经看到过了段（工会自previous返回到零）之一超集。
4. 如果您还保持了最小值和最大值，每个归零之间，你有超集的范围。

1. sort all endpoints (starting and ending points) in a list L (each endpoint should know the segment it belongs to). If an endpoint is equal to a starting point, the starting point should be considered smaller than the enpoint.
2. go through the sorted list L from left to right and maintain the number LE-RE, where LE is the number of left endpoints that you have already passed, and RE is the number of right endpoints that you have already passed.
3. each time LE-RE reaches zero, you are at the end of a connected union of segments, and you know that the union of the segments you have seen before (since the previous return to zero) is one superset.
4. if you also maintained the min and max, between each return to zero, you have the bounds of the superset.

最后，你获得不相交的超集的排序列表。不过，两人的超集A和B可以是相邻（A的终点就是B的起始点之前）。如果你想A和B合并，就可以做到这一点无论是简单的后处理步骤，或者稍微修改步骤3：在 LE-RE 达到零，你会认为这是一个结束超只有L中的下一个元素是不是你的当前元素的直接继承者。

At the end, you obtain a sorted list of disjoint supersets. Still, two supersets A and B can be adjacent (the endpoint of A is just before the starting point of B). If you want A and B to be merged, you can do this either by a simple postprocessing step, or by slightly modifying step 3: when LE-RE reaches zero, you would consider it the end of a superset only if the next element in L is not the direct successor of your current element.

这篇关于需要一个算法倒塌网络块范围内成超范围名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！