8

我有一段必须扫描的文本，每行至少包含 2 部分，有时包含 4 部分信息。问题是每行可以是 15-20 个不同动作中的 1 个。

在 ruby​​ 中，当前代码看起来有点像这样：

text.split("\n").each 做 |line| #大约20次..

.....................

      表达式['actions'].each 执行 |pat, reg| #大约20次

.....................

这显然是“问题”。我确实设法通过将所有正则表达式组合成一个来使其更快（在 C++ 中提高 50%），但这仍然不是我需要的速度——我需要快速解析数千个这些文件！

现在我将它们与正则表达式相匹配——但这太慢了。我从 ruby​​ 开始，然后跳到 C++，希望能提高速度，但它并没有发生。

我随便阅读了有关 PEG 和基于语法的解析，但它看起来有点难以实现。这是我应该去的方向还是有不同的路线？

基本上我正在解析扑克手牌历史，手牌历史的每一行通常包含我需要收集的 2-3 位信息：玩家是谁，多少钱或行动需要什么牌......等等。

需要解析的示例文本：

掩埋帖子 $5
按钮在座位 #4
*** 洞牌 ***
处理混乱 31337 [8s 广告]
宣威7折
OneMiKee 折叠
syhg99 通话 $5
掩埋场加注到 10 美元

在我收集了这些信息之后，每个动作都会变成一个 xml 节点。

现在我的 ruby​​ 实现比我的 C++ 快得多，但这很可能。只是因为我已经 4 到 5 年没有用 c 代码编写了

更新： 我不想在这里发布所有代码，但到目前为止，我的手/秒如下所示：

588 手/秒——c++ 中的 boost::spirit
60 手/秒——1 个非常长且复杂的 C++ 正则表达式（所有正则表达式放在一起）
33 手/秒——ruby 中的正常正则表达式样式

我目前正在测试 antlr，看看我们是否可以走得更远，但到目前为止，我对 Spirit 的结果非常满意。

相关问题：针对多个正则表达式有效地查询一个字符串。

4

10 回答 10

7

我会建议

祝你好运

于 2008-11-20T00:04:48.047 回答
4

Boost.Spirit是一个很棒的库，它允许您进行详细的解析器分析，并且由于解析器是直接生成并编译到您的代码中的，因此应该比动态计算的解决方案快得多。语法主要使用表达式模板（许多重载运算符的花哨术语）完成，这意味着您实际上将它们直接写入代码中。

于 2008-11-20T00:05:44.350 回答
2

如果您使用 Perl，这是一种方法。
复制自perldoc perlfaq6

while (<>) {
    chomp;
    PARSER: {
        m/ \G( \d+\b    )/gcx   && do { print "number: $1\n";  redo; };
        m/ \G( \w+      )/gcx   && do { print "word:   $1\n";  redo; };
        m/ \G( \s+      )/gcx   && do { print "space:  $1\n";  redo; };
        m/ \G( [^\w\d]+ )/gcx   && do { print "other:  $1\n";  redo; };
    }
}

对于每一行，PARSER循环首先尝试匹配一系列数字，然后是单词边界。此匹配必须从最后一个匹配的位置开始（或第一个匹配的字符串开头）。由于m/ \G( \d+\b )/gcx使用了c标志，如果字符串不匹配那个正则表达式，perl 不会重置pos()并且下一个匹配从相同的位置开始尝试不同的模式。

于 2008-11-20T20:11:40.357 回答
1

请参阅正则表达式匹配可以简单快速（但在 Java、Perl、PHP、Python、Ruby 中很慢...）。根据数据量和正则表达式的复杂程度，编写自己的解析逻辑可能会更快。

于 2008-11-20T00:12:11.153 回答
1

我随便阅读了有关 PEG 和基于语法的解析，但它看起来有点难以实现。这是我应该去的方向还是有不同的路线？

就我个人而言，我已经成长为喜欢 PEG。可能需要一点时间才能适应它们，但我认为它们更易于维护，这是一个明显的胜利。当您在输入中发现新的边缘情况时，我发现解析代码是许多意外错误的根源。与循环和条件繁重的正则表达式代码相比，带有非终结符的声明性语法在发生这种情况时更容易更新。命名是强大的。

在 Ruby 中有Treetop，它是一个使用 PEG 的解析器生成器。我最近发现用简短的语法替换正则表达式繁重的手写解析器非常愉快。

于 2008-11-30T09:50:50.487 回答
0

正则表达式匹配是否有重叠？也就是说，当两个或多个正则表达式匹配同一行时，它们是否总是匹配该行的不同部分（不重叠）？

如果匹配项从不重叠，请使用一个结合了您现在拥有的 15 个正则表达式的正则表达式运行您的搜索：

regex1|regex2|regex3|...|regex15

如果您需要能够确定 15 个正则表达式中的哪一个匹配，请使用捕获组。

为长正则表达式搜索一次数据将比搜索 15 次更快。快多少取决于您使用的正则表达式引擎和正则表达式的复杂性。

于 2008-11-20T07:12:29.883 回答
0

在 Perl 中尝试一个简单的测试。阅读“学习”功能。我可能会尝试的是：

  • 如果这些文件非常大，则将整个文件或大量行读取为单个字符串
  • 在每行的开头添加一个行号。
  • “研究”字符串。这会按字符构建查找表，可以很大。
  • 在字符串上运行正则表达式匹配，以换行符为界（使用 m 和 s 正则表达式修饰符）。该表达式应提取行号以及数据。
  • 将按行号索引的数组项设置为在该行上找到的数据，或者做一些更聪明的事情。
  • 最后，您可以处理存储在数组中的数据。

我没有尝试过，但它可能很有趣。

于 2008-11-21T23:19:40.883 回答
0

如果你有一个漂亮的四核或八核服务器用于此，另一个想法。

建立一个划分工作的处理管道。第一阶段可以将文件切割成一个游戏或每个手，然后将每个文件写入第二阶段的八个管道中的一个，这些管道读取数据、处理数据并以某种方式产生输出，可能会写入另一台机器上的数据库。

根据我的经验，这些基于管道的多进程设计几乎与多线程设计一样快且更容易调试。使用网络套接字而不是管道来设置机器集群也很容易。

于 2008-11-21T23:28:01.367 回答
0

好的，这让事情变得更清楚（扑克手牌历史）。我猜你正在制作一个统计工具（侵略因素，摊牌，自愿将$投入底池等）。我不知道你为什么需要过快的速度；即使您使用 16 张牌桌进行多桌游戏，手牌也只能以适中的速度进行。

我不了解 Ruby，但在 Perl 中，我会做一个小 switch 语句，同时将重要部分放入 $1、$2 等。根据我的经验，这并不比进行字符串比较然后拆分慢线用其他方式。

HAND_LINE: for ($Line)
    { /^\*\*\* ([A-Z ]+)/ and do 
        { # parse the string that is captured in $1
          last HAND_LINE; };
      /^Dealt to (.+) \[(.. ..)\]$/ and do
        { # $1 contains the name, $2 contains the cards as string
          last HAND_LINE; };
      /(.+) folds$/ and do
        { # you get the drift
          last HAND_LINE; }; };

我不认为你真的可以让它更快。将检查在第一个位置出现最多的行（可能是折叠语句）和最后只出现稀疏的行（开始新手，"*** NEXT PHASE ***"）。

如果您发现实际文件读取是一个瓶颈，您也许可以看看您可以使用哪些模块来处理大文件；对于 Perl，Tie::File我想到了。

确保您只阅读每手牌一次。不要在每手牌之后再次读取所有数据，而是保留例如已经解析的手牌 ID 的哈希表。

于 2008-11-22T00:34:48.690 回答
0

对于这样的问题，我只是闭上眼睛并使用 Lexer+Parser 生成器。您可能可以通过手动优化来击败它，但使用生成器要容易得多。此外，当输入突然改变时，它会更加灵活。

于 2008-11-30T10:15:34.960 回答