[已解决]求个脚本或工具能合并ip地址段的脚本
- astolia
- 论坛版主
- 帖子: 6542
- 注册时间: 2008-09-18 13:11
Re: 求个脚本或工具能合并ip地址段的脚本
这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的
- susbarbatus
- 帖子: 2966
- 注册时间: 2010-04-10 16:14
- 系统: Arch Linux
- Kandu
- 帖子: 108
- 注册时间: 2008-12-24 12:02
- 联系:
Re: 求个脚本或工具能合并ip地址段的脚本
ocaml 源码。依赖 batteries ocamlgraph lwt ok_monad ok_parsec
ocaml 和依赖可通过 opam 安装
后两个依赖尚未推送到 opam 软件库,可在我的 bitbucket 下载
ocaml 和依赖可通过 opam 安装
后两个依赖尚未推送到 opam 软件库,可在我的 bitbucket 下载
代码: 全选
open Ok_parsec
open Parsec
let decimalToBinary dec=
let rec decimalToBinary= function
| 0-> []
| n-> string_of_int (n mod 2) :: decimalToBinary (n / 2)
in
decimalToBinary dec |> List.rev |> String.concat ""
let binaryToDecimal bin=
("0b" ^ bin) |> int_of_string |> string_of_int
(* 将 subnet, 类型为 string * int 转换为字符串,用于输出 *)
let subnetToStr subnet=
let (ip, mask)= subnet in
let cleanUp ip=
(String.sub ip 0 mask) ^ (String.make (32-mask) '0')
in
let ip= cleanUp ip in
let sec1= String.sub ip 0 8
and sec2= String.sub ip 8 8
and sec3= String.sub ip 16 8
and sec4= String.sub ip 24 8 in
([sec1; sec2; sec3; sec4]
|> List.map binaryToDecimal
|> String.concat ".")
^ "/"
^ string_of_int mask
(* 定义 ip地址各小段的 parser *)
let ipSec=
many num_dec |>> BatString.of_list
(* 定义后面的 mask 位的 parser *)
let mask=
many num_dec |>> BatString.of_list
(* 得到 ip 地址的值表示 *)
let ip ipSecS=
let (sum, _)= List.fold_right
(fun num (sum, shift)->
(sum + (int_of_string num) lsl shift, shift+8))
ipSecS
(0, 0)
in sum
(* 定义 subnet 的分析器 *)
let subnet=
let%m ipSecS= sepBy (char '.') ipSec in
char '/' >>
let%m mask= mask |>> int_of_string in
let ip= ip ipSecS |> decimalToBinary in
let ip= String.make (32 - (String.length ip)) '0' ^ ip in
return (ip, mask)
(* 从输入产生一份 subnet 的列表 *)
let subnets input=
input
|> BatIO.lines_of
|> BatEnum.fold
(fun content line-> line::content)
[]
(* 尝试合并两个网域 *)
let merge net1 net2=
let rec merge net1 net2=
let (ip1, mask1)= net1
and (ip2, mask2)= net2 in
if mask1 = mask2 then
if String.sub ip1 0 mask1 <> String.sub ip2 0 mask1 then
if String.sub ip1 0 (mask1-1) = String.sub ip2 0 (mask1-1)
then merge (ip1, (mask1-1)) (ip2, (mask1-1))
else None
else Some net1
else
if String.sub ip1 0 mask1 = String.sub ip2 0 mask1
then Some net1
else None
in
let (ip1, mask1)= net1
and (ip2, mask2)= net2 in
if mask1 > mask2 then
merge net2 net1
else
merge net1 net2
(* 合并一份列表里面的所有网域 *)
let rec mergeAll res nets=
let mergeRes net=
match res with
| []-> None
| res::_-> merge res net
in
match nets with
| net::left->
(match mergeRes net with
| Some net-> mergeAll (net::List.tl res) left
| None-> mergeAll (net::res) left)
| []-> res
let main ()=
let subnets= subnets BatIO.stdin in (* 从 stdin 输入,得到网域列表 *)
let subnets=
subnets
|> List.map (parse_string subnet) (* 对列表里面的每个网域通过 subnet 语法分析器进行并发分析,得到 subnet list 结构,也就是 (string * int) list *)
|> List.map (fun thread-> (* 检查分析是否有误 *)
match Lwt.state thread with
| Lwt.Return Parsec.Ok (r, _)->r
| _-> failwith "parse_error")
|> List.rev
in
mergeAll [] subnets (* 无误就开始合并作业 *)
|> mergeAll []
|> List.map subnetToStr (* 然后将列表里的每个 subnet 转换为字符串 *)
|> List.iter print_endline (* 并输出到标准输出 *)
let ()= main ()
上次由 Kandu 在 2015-08-05 12:40,总共编辑 1 次。
- Kandu
- 帖子: 108
- 注册时间: 2008-12-24 12:02
- 联系:
Re: 求个脚本或工具能合并ip地址段的脚本
上傳了一個可執行檔的壓縮檔
以上寫法僅能處理非常好地排序好的網域條目。
若需要處理任意排列的網域條目的話,要稍作修改。
。讀寫 stdin, stdout. 利用重定向應該夠用。
以上寫法僅能處理非常好地排序好的網域條目。
若需要處理任意排列的網域條目的話,要稍作修改。
- Kandu
- 帖子: 108
- 注册时间: 2008-12-24 12:02
- 联系:
Re: 求个脚本或工具能合并ip地址段的脚本
忘了說依賴 libev4, apt-get install libev4 了才能用。因爲 ok_parsec 本來是用來做併發解析用的。
先轉成二進制就很好分析了。
原理就是,若兩個網域 mask 相同,僅僅最後的有效位不同的話,說明這兩個網域合起來覆蓋了 mask-1 的更大網域,可以合併。返回任一網域最後有效位置0,mask-1的網域即可。
若兩網域不同, mask 小的那個也就是大網域,若大網域覆蓋小網域,也能合併。直接返回大網域。
先轉成二進制就很好分析了。
原理就是,若兩個網域 mask 相同,僅僅最後的有效位不同的話,說明這兩個網域合起來覆蓋了 mask-1 的更大網域,可以合併。返回任一網域最後有效位置0,mask-1的網域即可。
若兩網域不同, mask 小的那個也就是大網域,若大網域覆蓋小網域,也能合併。直接返回大網域。
- astolia
- 论坛版主
- 帖子: 6542
- 注册时间: 2008-09-18 13:11
Re: 求个脚本或工具能合并ip地址段的脚本
就是位运算呗。源里的aggregate的C源代码总看得懂了吧
- Kandu
- 帖子: 108
- 注册时间: 2008-12-24 12:02
- 联系:
-
- 帖子: 1
- 注册时间: 2017-10-31 23:15
Re: [已解决]求个脚本或工具能合并ip地址段的脚本
请问楼主,如何解决的,求解。 拜谢。
-
- 帖子: 5
- 注册时间: 2008-04-17 10:22
Re: [已解决]求个脚本或工具能合并ip地址段的脚本
perl脚本不错,1000+行的路由条目经过两次合并变为100+行了,牛!
-
- 帖子: 1
- 注册时间: 2019-05-14 9:07
- 系统: ubuntu
Re: [已解决]求个脚本或工具能合并ip地址段的脚本
aggregate 这个工具具体在哪呢? 大神们指导下
- astolia
- 论坛版主
- 帖子: 6542
- 注册时间: 2008-09-18 13:11