在StringBuilder的最快的搜索方法 [英] Fastest search method in StringBuilder

问题描述

我有一个的StringBuilder 的 stb_Swap_Tabu 用于存储课程的名称， 我使用下面的方法找到一个过程：

I have a StringBuilder named stb_Swap_Tabu used to store Course's Names, I am using the following method to find a course:

stb_Swap_Tabu.ToString.Contains("CourseName")

在我的情况下，性能是最重要的问题。 有没有更快的方法？

in my case, Performance is the most important issue. Is there any faster way?

推荐答案

StringBuilder的是不是真的适用于所有字符串的目的。如果你真的需要寻找一个，你必须写你自己的方法。

StringBuilder wasn't really intended for all string purposes. If you really need to search one, you have to write your own method.

有适用于不同的情况下，几个字符串搜索算法。

There are several string-searching algorithms suited to different cases.

下面是一个简单的实现了高德纳 - 莫里斯 - 普拉特算法，只关心序匹配（任何情况下折叠，没有文化相关的整理，只是一个普通的$ C $连接点至$ C $口岸系统匹配）的。它有一些初步的Θ（M）的开销，其中 M 这个词的追捧的长度，然后在找到Θ（N），其中 N 是寻求字的距离，或整个字符串建设者，如果它的长度是不存在的。这击败了简单的字符按char的比较哪个Θ（（N-M + 1）M）（这里的 O（）符号描述上界，Θ（）描述了上限和下限）。

The following is a simple implementation of the Knuth–Morris–Pratt algorithm that only cares about ordinal matches (no case-folding, no culture-related collation, just a plain codepoint to codepoint match). It has some initial Θ(m) overhead where m is the length of the word sought, and then finds in Θ(n) where n is the distance to the word sought, or the length of the whole string-builder if it isn't there. This beats the simple char-by-char compare which is Θ((n-m+1) m) (Where O() notation describes upper-bounds, Θ() describes both upper and lower bounds).

这一切都表示，它听起来像创建一个列表可能是一个更好的办法来手头的工作。

All this said, it does sound like creating a list might be a better approach to the task in hand.

public static class StringBuilderSearching
{
  public static bool Contains(this StringBuilder haystack, string needle)
  {
    return haystack.IndexOf(needle) != -1;
  }
  public static int IndexOf(this StringBuilder haystack, string needle)
  {
    if(haystack == null || needle == null)
      throw new ArgumentNullException();
    if(needle.Length == 0)
      return 0;//empty strings are everywhere!
    if(needle.Length == 1)//can't beat just spinning through for it
    {
      char c = needle[0];
      for(int idx = 0; idx != haystack.Length; ++idx)
        if(haystack[idx] == c)
          return idx;
      return -1;
    }
    int m = 0;
    int i = 0;
    int[] T = KMPTable(needle);
    while(m + i < haystack.Length)
    {
      if(needle[i] == haystack[m + i])
      {
        if(i == needle.Length - 1)
          return m == needle.Length ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - T[i];
        i = T[i] > -1 ? T[i] : 0;
      }
    }
    return -1;
  }      
  private static int[] KMPTable(string sought)
  {
    int[] table = new int[sought.Length];
    int pos = 2;
    int cnd = 0;
    table[0] = -1;
    table[1] = 0;
    while(pos < table.Length)
      if(sought[pos - 1] == sought[cnd])
        table[pos++] = ++cnd;
      else if(cnd > 0)
        cnd = table[cnd];
      else
        table[pos++] = 0;
    return table;
  }
}

这篇关于在StringBuilder的最快的搜索方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！