-
Notifications
You must be signed in to change notification settings - Fork 0
saubcy/Distinct-IP
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
应用场景: 有很多给定了IP起始地址跟结束的IP段及其所对应的地理位置信息,如: 1035616256|1035632639|湖南省|\N|电信 3524669440|3524673535|湖南省|\N|联通 1038896384|1038896639|湖南省|岳阳市|铁通 3549370624|3549371903|湖南省|永州市|移通 3702087680|3702095871|湖南省|怀化市|电信 3740532736|3740598271|湖南省|长沙市|电信 但是并不能保证这些数据是无交叉重叠的。 为了快速的查询一个给定的IP地址是否在此库中有记录必须对数据进行预处理,即处理成所有IP段单调递增并且无重叠的。 算法描述: 数据排序:10 20 30 40 45 50 数据下标: 0 1 2 3 4 5 对下标来说:n与n+1(n为偶数)对应的数及它俩之间的数为数据片断中的数。 若要找开始数为5经束数为35且不与上重叠的信息,则重新排序: 数据排序:5 10 20 30 35 40 45 50 数据下标:0 1 2 3 4 5 6 7 那么所求则为:下标在0(对应数5)至4(对应数35),下标n与n+1(n为偶数)对应数之间的数为所求。所以所求下标为(0,1)、(2,3),所求对应的数则为(5,10)及(20,30)。 又在上例中:要找(15,46)之间的数。 数据排序:10 15 20 30 40 45 46 50 数据下标: 0 1 2 3 4 5 6 7 那么所求则为:下标在1(对应数15)至6(对应数46),下标n与n+1(n为偶数)对应数之间的数。所求下标为(2,3)、(4,5),所求对应数为(20,30)、(40,45)。 即首先根据IP段的宽度进行升序排序,然后逐步遍历所有IP段依照上述算法进行插入,只取与数据集合中不重叠的部分。 目录说明: distinct_ip.cpp // 实现代码 testcase // 测试用例目录
About
Processing the discrete IP data to continuous and non-overlapping
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published