优化正则表达式

Question

优化正则表达式

3

我正在使用以下代码从连接到大型ISP网络（指数以万计的路由器）的路由器中丢弃不支持的物理接口/子接口：

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
   } 
}

这个想法是丢弃以下条目：

未路由的VLAN 2000，用于GigabitEthernet2/11.2000
GigabitEthernet1/2-mpls层
FastEthernet6/0/3.2000-802.1Q vLAN子接口

这段代码在大量接口（一些路由器有50k+子接口）上经常被触发（每分钟几次），缓存也没有太多帮助，因为新的子接口经常被配置/丢弃。计划优化正则表达式，以便该过程完成得更快（每纳秒都很重要）。你们能给我指点吗？

注意：mpls层和802.1Q适用于其他类型的接口，但不适用于未路由的VLAN。

- Anthony Accioly

为什么不先隔离应该匹配的字符串并检查呢？ - ratchet freak

1

你尝试过直接使用String.contains而不是正则表达式吗？ - JB Nizet

你提供的那些条目是完整的行还是从行中间截取的一些单词？ - piotrekkr

3

我不确定，但很容易测试它是否有价值。您还可以使用indexOf，并仅在找到“-mpls ayer”之后测试'GigabitEthernet' + 15的索引（15是'GigabitEthernet'的长度）。 - JB Nizet

1

那么 matches() 也能起作用，因为它不会在每个位置都尝试（只尝试一次匹配而不是 intf.length()）。 - ratchet freak

显示剩余4条评论

4个回答

2

我为了进一步参考而回答自己的问题，虽然功劳归于@piotrekkr，因为他指出了方向。同时，我也要感谢@JB和@ratchet。最终我使用了matches()，逻辑上使用了indexOf和几个contains，速度几乎与单个正则表达式相同（这对我来说是新闻，我一直认为单个正则表达式比多次调用contains更快）。

以下是一个解决方案，根据分析器的结果，它比原来快了几倍（在Matcher类方法中花费的时间约少了7倍）：

^(?:unrouted VLAN.++|GigabitEthernet.+?-mpls layer|FastEthernet.+?-802\\.1Q vLAN subif)$

- Anthony Accioly

1

如果您的问题是您有许多长字符串常量需要搜索，我建议使用Java标准C工具“lex”的类比。

快速搜索将带您到JFlex。我没有使用过这个特定的工具，可能还有其他可用的工具，但这是我会寻找的工具的一个例子。

- theglauber

好吧，Lex 最终只会为他创建一个有限状态机，而正则表达式已经在做这件事了。 - Voo

好观点。我想使用词法分析工具有两个原因：（1）我希望该工具能够比正则表达式更好地优化有限状态机（因为它可以花更多时间进行优化）。（2）与具有许多|的长正则表达式相比，lex文件为我提供了一种更可读的方式来组织我的搜索字符串。 - theglauber

1

如果你必须使用正则表达式，请尝试更改为这个：

^(?:unrouted VLAN)|(?:GigabitEthernet.+?-mpls layer)|(?:FastEthernet.+?-802\.1Q vLAN subif)

^ 使引擎只匹配字符串的开头，而不是字符串中的任何位置

.+? 使 + 不贪婪

(?:...) 使 () 成为非捕获组

- piotrekkr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Voo · Accepted Answer

有一些字符串搜索算法，可以让你尝试在长度为n的字符串中以比明显的O(n*k)更便宜的代价同时搜索k个字符串。

它们通常会将滚动哈希与单词现有哈希列表进行比较。其中一个主要的例子就是Rabin-Karp算法。维基页面甚至有一节专门介绍这个。还有更高级的版本原理存在，但原理很容易理解。

我不知道Java是否已经有了这样的库（我认为应该有），但这是我会尝试的方法——虽然5个字符串在这里相当小（而且大小不同会使事情变得更加复杂）。因此最好检查一下是否使用良好的KMP字符串搜索更快——我认为那真的是迄今为止最佳的解决方案（默认的Java API使用了朴素的字符串搜索，所以使用库）。

关于你的正则表达式：回溯正则表达式实现对于性能关键的搜索代码来说，我认为这不是一个好主意。

附注：如果你发布一个测试集和测试工具，人们很可能会看到他们能够击败喜欢的东西——这种方法以前行过。人类的本质很容易被欺骗 :)