java - 优化正则表达式

Question

我正在使用以下代码从连接到大型 ISP 网络(我指的是数万个路由器)的路由器中丢弃不受支持的物理接口(interface)/子接口(interface):

private final static Pattern INTERFACES_TO_FILTER = 
   Pattern.compile("unrouted VLAN|GigabitEthernet.+-mpls layer|FastEthernet.+-802\\.1Q vLAN subif"); 

// Simplification
List<String> interfaces;
// lots of irrelevant code to query the routers 

for (String intf : interfaces) {
   if (INTERFACES_TO_FILTER.matcher(intf).find()) {
      // code to prevent the interface from being used
   } 
}

这个想法是丢弃条目，例如:

• GigabitEthernet2/11.2000 的未路由 VLAN 2000
• GigabitEthernet1/2-mpls层
• FastEthernet6/0/3.2000-802.1Q vLAN 子接口(interface)

此代码在大量接口(interface)(一些路由器有 50k+ 子接口(interface))上被频繁命中(每分钟几次)，缓存也没有太大帮助，因为新的子接口(interface)被配置/丢弃非常频繁。计划是优化正则表达式，使过程完成得更快一点(每一纳秒都很重要)。各位大神能指点一下吗？

注意 mpls 层 和802.1Q 支持其他类型的接口(interface)，未路由的 VLAN 不支持

Answer 1

有一些字符串搜索算法允许您尝试在一个长度为 n 的字符串中搜索 k 个字符串，同时比明显的 O(n*k) 成本要便宜。

他们通常会将滚动哈希值与您的单词的现有哈希值列表进行比较。一个典型的例子是 Rabin-Karp algorithm .维基页面甚至有一个关于这个的部分。该原理还有更高级的版本，但原理很容易理解。

不知道 Java 中是否已经有执行此操作的库(我认为是)，但这就是我要尝试的 - 尽管这里 5 个字符串相当小(不同的大小也使它更复杂)。所以最好检查一下良好的 KMP 字符串搜索是否更快——我认为这确实是迄今为止最好的解决方案(默认的 java api 使用简单的字符串搜索，所以使用 lib)

关于您的正则表达式:为性能关键搜索代码回溯正则表达式实现？我怀疑这是个好主意。

PS:如果您针对您的问题发布了一个测试集和一个测试工具，那么好人很可能会看到他们能击败最喜欢的东西多少 - 以前已经奏效了.. 人性很容易被欺骗 :)