在C中提取子字符串的最快方法

问题描述：

我要处理数千个字符串（平均大小约为150kB）。他们每个人都包含以下形式的零个或多个字符串：在C中提取子字符串的最快方法

<a href="/link/i/want">Fixed_String</a>

我想提取所有这样的链接，并把它们放入一个列表。

此外，还有另一个固定的字符串后，我所寻找的字符串将不会出现。

获取字符串的最快方法是什么？

“Fixed_String”部分总是完全一样吗？ – LukeH 2011-06-02 12:20:34

@LukeH：是的，这是一个固定的字符串。 – Hui 2011-06-02 12:22:31

答

子串（）选项

正如泰奥曼Soygul指出，有一个子（）选项，我不知道这是否是或快或慢，因为我没有测试他们并排。

现在，这没有适当地分成子方法，但应该给你的一般想法。
我只是使用一个ReadOnlyCollection因为这是我习惯于当不需要进一步操纵列表。将其更改为您喜欢的任何输出列表类型。

someText变量最有可能最终会偏离GetLinks的参数。

public ReadOnlyCollection<string> GetLinks() 
{ 
    string startingText = "href=''"; 
    string endText = "''>"; 
    string stopText = "Fixed_String"; 
    string someText = @"what is this text <a href=''/link/i/want''>somenormallink</a> some random text <a href=''/another link/i/want''>Fixed_String</a> some more radnom txt "; 

    List<string> myLinks = new List<string>(); 

    string[] rawLinks = someText.Split(new string[] { "<a " }, StringSplitOptions.None); 

    foreach (string rawLink in rawLinks) 
    { 
     if (!rawLink.StartsWith(startingText)) 
     { 
      continue; 
     } 

     myLinks.Add(rawLink.Substring(startingText.Length, rawLink.IndexOf(endText, 1) - startingText.Length)); 


     if (rawLink.Contains(stopText)) 
     { 
      break; 
     } 
    } 


    return new ReadOnlyCollection<string>(myLinks); 
}

导致含有链接的集合：
enter image description here

答

假设字符串格式正确的HTML格式，您可以轻松地用XmlReader类进行解析，该类非缓存且只转发（这使得它非常快速）。您只需寻找适当的节点来检索其'href'属性的值。

您也可以使用像.SubString()这样的普通字符串操作，但是您必须编写许多子例程来处理异常情况。这里的要点是避免RegEx，因为它是最慢的。

你确定吗？我还没有测试过，但对我而言似乎并不那么明显，一系列正则表达式匹配比XmlReader慢得多......没时间现在测试，但稍后可能会用到它:) – Tao 2011-06-02 12:47:05

这不是我在这里发言，这是经验:) RegEx引擎总是比只转发和非缓存解析器（大约是我的经验的10倍）慢。尝试使用RegEx和'XmlReader.Create（..）'从大文档中提取单个元素的属性，然后您会看到... – 2011-06-02 13:24:24

答

我觉得在这种情况下有字符串这是足够大的，平均和其中包含零个或多个子最好的办法，是用Regex class这样的：

string anchorPattern = @"<(.|/)a(.|\n)+?>"; 

foreach (string str in strings) 
{ 
    Regex regex = new Regex(anchorPattern); 

    foreach (Match match in regex.Matches(str)) 
    { 
     // do here what you want with substring in match.Value 
    } 

}

答

手工解析的位可能是解决这个问题的最快方法。正则表达式也是可能的，因为它实际上只是解析链接而不是整个HTML文档的一个非常简单的例子，但是它很容易扼杀这些大文件，性能明智。

现在，让我说这个，我没有测试过这个，我觉得有点肮脏张贴它（我相信它需要更多的边缘情况下检查，以避免错误），但在这里你去：

const char[] quotes = new char[] { '"', '\'' }; 

    private List<string> ExtractLinks(string html) 
    { 
     var links = new List<string>(); 
     string searchFor = ">Fixed_String</a>"; 

     for (int i = html.IndexOf(searchFor); i >= 0; i = html.IndexOf(searchFor, i + searchFor.Length)) 
     { 
      string href = ExtractHref(html, i); 
      if (!String.IsNullOrEmpty(href)) 
       links.Add(href); 
     } 

     return links; 
    } 

    private string ExtractHref(string html, int backtrackFrom) 
    { 
     int hrefStart = -1; 

     // Find "<a", but limit search so we don't backtrack forever 
     for (int i = backtrackFrom; i > backtrackFrom - 255; i--) 
     { 
      if (i < 0) 
       return null; 

      if (html[i] == '<' && html[i + 1] == 'a') 
      { 
       hrefStart = html.IndexOf("href=", i); 
       break; 
      } 
     } 

     if (hrefStart < 0) 
      return null; 

     int start = html.IndexOfAny(quotes, hrefStart); 
     if (start < 0) 
      return null; 

     int end = html.IndexOfAny(quotes, start + 1); 
     if (end < 0) 
      return null; 

     return html.Substring(start + 1, end - start - 1); 
    }

XmlReader可能是一个不行，因为你很可能不能保证这些文件是XHTML格式。如果你想做适当的解析，HTML Agility Pack可能是你最好的选择，或者如果它不能被帮助，可能是一个正确的正则表达式。我发布了这个手册解析，所以你有另一个可以做性能测试的选择。

答

一般正则表达式是小文件的速度。如果文件大小变大（按我的经验大于〜60Kb），则Regex变慢（即使是静态，编译等）。在很好的英语描述找到确切的情况：

Stripping Out Empty XmlElements in a Performant Way and the Bus Factor

玩得开心发现什么是“高巴士因子”。它给我带来了一天的好心情。

在C中提取子字符串的最快方法

相关推荐