我有一个的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;
}
}