一种更高效的正则表达式或替代方案？

Question

我有一个包含100万行左右的文件。

 {<uri::rdfserver#null> <uri::d41d8cd98f00b204e9800998ecf8427e> <uri::TickerDailyPriceVolume> "693702"^^<xsd:long>}
 {<uri::rdfserver#null> <uri::d41d8cd98f00b204e9800998ecf8427e> <uri::TickerDailyPriceId> <uri::20fb8f7d-30ef-dd11-a78d-001f29e570a8>}

每一行都是一个语句。

struct Statement
    string C;
    string S;
    string P;
    string O;
    string T;

目前我正在使用一个while循环中的TextReader，并使用正则表达式解析每一行：

Regex lineParse = new Regex(@"[^<|\""]*\w[^>\""]*", RegexOptions.Singleline | RegexOptions.Compiled);

这种解析需要花费相当长的时间，我希望有人能指点一下更高效的解析策略。

有些行有5个匹配项，有些只有4个。以下是每行的解析方式：

{<uri::rdfserver#null> <uri::d41d8cd98f00b204e9800998ecf8427e> <uri::TickerDailyPriceVolume> "693702"^^<xsd:long>}

Statement()
    C = uri::rdfserver#null
    S = uri::d41d8cd98f00b204e9800998ecf8427e
    P = uri::TickerDailyPriceVolume
    O = 693702
    T = xsd:long

{<uri::rdfserver#null> <uri::d41d8cd98f00b204e9800998ecf8427e> <uri::TickerDailyPriceId> <uri::20fb8f7d-30ef-dd11-a78d-001f29e570a8>}

Statement()
    C = uri::rdfserver#null
    S = uri::d41d8cd98f00b204e9800998ecf8427e
    P = uri::TickerDailyPriceId
    O = uri::20fb8f7d-30ef-dd11-a78d-001f29e570a8

来自评论的额外信息：“我看到的低性能实际上是由于我在代码中设置的有条件断点。如果没有这个断点，一切都很快。但如果有任何改进想法，我会感兴趣。” -Eric Schoonover

- spoon16

---

我看到的性能差是由于我在代码中设置了一个条件断点。如果没有那个断点，一切都很快。但如果有人有任何改进的想法，我会很感兴趣 :) - Eric Schoonover

你可能想要将此信息添加到您的帖子中，这样人们就知道您不再寻求速度了。 - Nathan W

我仍在寻找速度，只是我发布的正则表达式并不像我想象中的那么慢。 - Eric Schoonover

我很想知道你的方法与@sixlettervariables提供的方法相比如何。我预计Split方法会明显更快。 - Alan Moore

顺便提一下，在这个字符类 - [^<|""] - 中，你不需要管道符或反斜杠。OR是隐含的，并且在C#逐字字符串中，双引号通过加倍来转义，而你已经做到了。 - Alan Moore

Answer 1

最快的方法是简单的字符串分割（如下所示）：

line.Split(new char[] { '{', '<', '>', '}', ' ', '^', '"' },
           StringSplitOptions.RemoveEmptyEntries);

下一个最快的是锚定正则表达式（丑陋）：

Regex lineParse
    = new Regex(@"^\{(<([^>]+)>\s*){3,4}(""([^""]+)""\^\^<([^>]+)>\s*)?\}$",
                RegexOptions.Compiled);
Match m = lineParse.Match(line);
if (m.Groups[2].Captures.Count == 3)
{
    Data data = new Data { C = m.Groups[2].Captures[0].Value,
        S = m.Groups[2].Captures[1].Value, P = m.Groups[2].Captures[2].Value,
        O = m.Groups[4].Value, T = m.Groups[5].Value };
} else {
    Data data = new Data { C = m.Groups[2].Captures[0].Value,
        S = m.Groups[2].Captures[1].Value, P = m.Groups[2].Captures[2].Value,
        O = m.Groups[2].Captures[3].Value, T = String.Empty };
}

随机数据1M行的计时（以String.Split为基准）：

Method                #1  Wall (Diff)       #2  Wall (Diff)
------------------------------------------------------------
line.Split                3.6s (1.00x)         3.1s (1.00x)
myRegex.Match             5.1s (1.43x)         3.3s (1.10x)
itDependsRegex.Matches    6.8s (1.88x)         4.4s (1.44x)
stateMachine              8.4s (2.34x)         5.6s (1.82x)
alanM.Matches             9.1s (2.52x)         7.8s (2.52x)
yourRegex.Matches        18.3s (5.06x)        12.1s (3.90x)

更新内容包括@AlanM和@itdepends的正则表达式。看起来Regex.Matches比Regex.Match慢，但是你给解析器提供的上下文线索越多，它就执行得越好。@AlanM使用的单个负字符类最简单易读，但比最神秘的（我的）要慢。向@itdepends致敬，他提供了最简单的正则表达式，产生了最快的时间。好吧，虽然我认为编写状态机来解析行是疯狂的，但实际上它表现得并不差...感谢@RexM的建议。我还添加了我家里的Q6600（#2）和工作中旧的Xeon（#1）的时间。

- sixlettervariables

Answer 2

有时候状态机比正则表达式快得多。

- Rex M

---

+1，我本来想嘲笑你的回答，直到我自己写了出来。它不是最糟糕的，也不是最好的。令人惊讶的是，在所需的工作量下还算不错... - user7116

由于正则表达式只是状态机的一种特殊情况，通过正确的优化，您应该能够击败任何正则表达式引擎。 - Eclipse

Answer 3

经过一些测试后，我得出了以下结论：

@"<(?<capture>[^>]+)>|""(?<capture>[^""]+)"""

这个值需要通过match.Groups[1].Value来获取。

在我的非科学测试中，它比原问题中的那个快了大约75-80%。

Match与Matches

在生产中，我通常使用Match，但在上述情况下使用了Matches。我从未考虑过性能方面的影响，所以进行了一些测试，使用完全相同的正则表达式：

for(Match match = regex.Match(input); match.Success; match = match.NextMatch())
// min 5.01 sec
// max 5.15 sec

foreach(Match match in regex.Matches(input))
// min 5.66 sec
// max 6.07 sec

因此，Match肯定可以比Matches更快。

- it depends

---

为您的代码添加了计时功能，大约可以从 OP 的正则表达式中节省 3 秒。 - user7116

+1，我认为这是回溯和正则表达式中提供的上下文的结合。尖括号为您的正则表达式提供了上下文，而仅使用负字符类则无法提供。 - user7116

Answer 4

据我所见，迄今为止提供的正则表达式比它们需要的要复杂得多。如果 @sixlettervariables 的分割方法可行，则匹配应该使用此正则表达式：

@"[^{}<> ^""]+"

但我仍然期望String.Split方法更快。

- Alan M

---

我认为使String.Split更快的原因是它不使用正则表达式。尝试使用Regex.Split。 - Alan Moore

哦，我明白你在谈论匹配与匹配性能。但是你每行只做一次匹配，而且你的正则表达式几乎没有回溯机会。其他所有人都必须对每行执行多次匹配。 - Alan Moore