V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
monsoon
V2EX  ›  算法

有没有什么简单、性能也还过得去的 匹配 CIDR 集合(包含 IPv6 的 CIDR)的算法推荐?

  •  
  •   monsoon · 2020-05-27 22:54:51 +08:00 · 1254 次点击
    这是一个创建于 1401 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求很简单的,就是有一个 1W 个左右的 CIDR 集合(包括 IP 、CIDR ),想匹配一个 IP 在不在这里面。宿主语言是 Java 之类不直接操作指针的语言。输入结果是一个 true 或者 false 就可以了。 现在我只会 loop 的方法和 binary trie…… IPv6 和 IPv4 我会分成两个集合分开来匹配就可以了。

    找了一下论文,感觉有很多的 Longest prefix match 的算法,但是不知道哪个改起来合适……写起来简单,性能也还可以,内存占用也不太。

    大家有没有什么推荐的算法,不要那种要 128 次匹配(对于 IPv6 )的那种。先谢谢了。

    3 条回复    2020-05-28 20:40:29 +08:00
    rrfeng
        1
    rrfeng  
       2020-05-27 23:30:13 +08:00 via Android   ❤️ 1
    cidr ?要想快直接变数值,然后算出边界来直接比大小啊……简单写个二分查找就不会很差吧
    iRiven
        2
    iRiven  
       2020-05-28 09:46:22 +08:00 via Android   ❤️ 1
    统统转成 u128,然后排序 二分查找,最快
    monsoon
        3
    monsoon  
    OP
       2020-05-28 20:40:29 +08:00
    非常感谢楼上两位,转换成了一个 pair (表示 range ) 的 list,二分法非常好写。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5304 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 09:07 · PVG 17:07 · LAX 02:07 · JFK 05:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.