StringBuilder中最快的搜索方法

Question

我有一个名为 stb_Swap_Tabu 的 StringBuilder，用于存储课程名称， 我正在使用以下方法查找一门课程：

stb_Swap_Tabu.ToString.Contains("CourseName")

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

- Alaa Alweish

---

如果你需要使用 StringBuilder，那么每次想要搜索时都需要调用 ToString，这在性能方面并不是一个好主意。StringBuilder 用于构建字符串；假设你正在构建字符串，那么你已经有了组成部分；为什么不直接在这些组成部分中进行搜索呢？ - LukeH

使用StringBuilder可能不是存储可搜索名称列表的最合适数据类型。为什么不使用List<string>，并使用List的Contains方法？ - Rotem

你有这个字符串的实际例子吗？你说它存储了“课程名称” - 无论“课程”的意思是否是“课程”，“名称”都暗示着不止一个名称 - 因此，这可能是一种分隔符字符串。如果是这样的话，将它转换为单独名称的List<string>或HashSet<string>将会有很多意义。 - Marc Gravell

更多字符串使用HashSet，较少的字符串使用list。 - Chibueze Opata

@Shaks 取决于你对它的其他用途。StringBuilder 不适合搜索（即使采用我的答案中的方法，它只能与字符串一样好），但如果由于其他工作而需要构建器，则选择是在搜索与放入更可搜索的集合之间进行，搜索它，然后根据结果更新或重建基于字符串构建器。在这种情况下，如果有很多其他适合字符串构建器的工作，则搜索字符串构建器可能是最好的整体选择。 - Jon Hanna

Answer 1

StringBuilder并不是为所有字符串目的而设计的。如果你真的需要搜索一个，你必须编写自己的方法。

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

以下是Knuth-Morris-Pratt算法的简单实现，它只关心序数匹配（没有大小写转换，没有与文化相关的排序，只是一个纯粹的代码点到代码点的匹配）。它有一些初始的Θ(m)开销，其中m是所需单词的长度，然后在Θ(n)中找到所需单词的距离或整个字符串构建器的长度，如果它不存在的话。这击败了简单的逐字符比较，其复杂度为Θ((n-m+1) m)（其中O()符号描述上限，Θ()描述上下限）。

尽管如此，创建一个列表似乎更好地解决了手头的任务。

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

- Jon Hanna

---

正如@JonHanna所提到的，我有一个使用构建器的很好的理由，这就是为什么我的问题标题是：“StringBuilder中最快的搜索方法”。 经过我的测试，@JonHanna提供的答案在一些修改后比使用“Contains”要好28％。我将尝试制作抽象代码并在此分享。 - Alaa Alweish

StringBuilder有一个必须搜索字符串并且甚至需要使用起始和结束索引的“Replace”函数，却没有提供“indexOf”函数，这毫无意义。为什么我们要重做已经完成的工作呢？ - Slight

这段代码对于我来说失败了，使用的干草堆是“abcde”，针是“cd”，它返回false。 - Juri Robl

应该只是 return m;，而不是 return m == needle.Length ? -1 : m; 吗？ - Juri Robl

@JuriRobl那部分是为了匹配.NET约定，表示未找到的情况下返回-1。不过我不知道是什么原因导致了失败，如果有机会我会稍后查看。 - Jon Hanna

我同意，应该只是 return m;。否则它会返回 -1。 - neilsimp1

Answer 2

我知道这是一个老问题，但当我尝试为自己的项目创建解决方案时，它出现在我的搜索结果中。我以为我需要搜索StringBuilder.ToString方法的结果，但后来我意识到我可以直接调用StringBuilder本身的方法。我的情况可能与你的不同，但我想分享一下：

Private Function valueFormatter(ByVal value As String) As String
    ' This will correct any formatting to make the value valid for a CSV format
    '
    ' 1) Any value that as a , in it then it must be wrapped in a " i.e. Hello,World -> "Hello,World"
    ' 2) In order to escape a " in the value add a " i.e. Hello"World -> Hello""World
    ' 3) if the value has a " in it then it must also be wrapped in a " i.e. "Hello World" -> ""Hello World"" -> """Hello World"""
    ' 
    ' VB NOTATAION 
    ' " -> """"
    ' "" -> """"""

    If value.Contains(",") Or value.Contains("""") Then
        Dim sb As New StringBuilder(value)
        If value.Contains("""") Then sb.Replace("""", """""")
        sb.Insert(0, """").Append("""")
        Return sb.ToString
    Else
        Return value
    End If
End Function

- вʀaᴎᴅᴏƞ вєнᴎєƞ