C# StringBuilder 中最快的搜索方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12261344/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest search method in StringBuilder
提问by Alaa
I have a StringBuildernamed stb_Swap_Tabuused to store Course's Names,
I am using the following method to find a course:
我有一个StringBuilder命名stb_Swap_Tabu用来存储课程的名称，我使用下面的方法找到一个过程：
stb_Swap_Tabu.ToString.Contains("CourseName")
in my case, Performance is the most important issue. Is there any faster way?
就我而言，性能是最重要的问题。有没有更快的方法？
采纳答案by Jon Hanna
StringBuilder wasn't really intended for all string purposes. If you really need to search one, you have to write your own method.
StringBuilder 并不是真正用于所有字符串目的。如果您真的需要搜索一个，则必须编写自己的方法。
There are several string-searching algorithms suited to different cases.
有几种适合不同情况的字符串搜索算法。
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 mis the length of the word sought, and then finds in Θ(n)where nis 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).
下面是 Knuth-Morris-Pratt 算法的一个简单实现，它只关心序数匹配（没有大小写折叠，没有与文化相关的排序规则，只是一个简单的代码点到代码点匹配）。它有一些初始Θ(m)开销，其中m查找的单词的长度是哪里，然后查找到查找的单词的距离在Θ(n)哪里n，或者如果不存在，则查找整个字符串生成器的长度。这击败了简单的逐字符比较Θ((n-m+1) m)（其中O()符号描述了上限，Θ()描述了上限和下限）。
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;
}
}
回答by в?a???? в?н???
I know this is an old question but it came up in my search results when I was trying to create a solution for my own project. I thought I needed to search a StringBuilder.ToString's method results but then I realized I could just call methods on the StringBuilderitself. My situation may not be the same as yours, but I though I'd share:
我知道这是一个老问题，但是当我尝试为自己的项目创建解决方案时，它出现在我的搜索结果中。我以为我需要搜索 aStringBuilder.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
