7
我有一個任務，我需要查找文件中的序列。在做測試應用程序時，我已經將文件讀取爲字符串（File.ReadAllText）並使用string.IndexOf來查找序列。當我試圖用字節實現相同的算法（以字節數組讀取文件並在字節數組中查找字節數組）時，我注意到在byte []中查找byte []的速度大約是在字符串中查找字符串的3倍。我一定要徹底檢查它，並且完全相同的代碼，使用byte []和其他使用字符串的代碼需要執行3倍的數量 - 例如，字節爲16秒，字符串爲〜5秒。在字節[]中查找字節[]的速度和在字符串中的字符串 - 爲什麼後者更快？
爲了查找字節數組，我使用了這裏描述的方法byte[] array pattern search。爲了查找字符串，我使用了string類的內置IndexOf函數。下面是的IndexOf的實現爲字節[]我嘗試之一：
public int IndexOf(byte[] source, byte[] pattern, int startpos = 0)
{
int search_limit = source.Length - pattern.Length;
for (int i = startpos; i < search_limit; i++)
{
if (source[i] == pattern[0])
{
bool found = true;
for (int j = 1; j < pattern.Length; j++)
{
if (source[i + j] != pattern[j])
{
found = false;
break;
}
}
if (found)
return i;
}
}
return -1;
}
基本上，查找下一個匹配對以字節陣列的字節序列有三個時間只要查找用於在字符的序列下一個匹配串。我的問題是 - 爲什麼？
有誰知道.net處理查找字符串中的字符，它做了什麼樣的優化，它使用什麼算法？有沒有比我在這裏使用的算法更快的算法？也許有人有一個想法，我在這裏做錯了，所以它需要更多的時間比它應該？我真的不明白如何在字符串中查找字符串可以是在字節[]中查找字節[]的3倍...
更新：我已經嘗試了建議的不安全算法。它如下：
public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
{
long i = startpos;
fixed (byte* H = Haystack) fixed (byte* N = Needle)
{
for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
{
bool Found = true;
for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
if (Found) return i;
}
return -1;
}
}
}
奇怪的是，它實際上證明是慢一倍！我改成了加我個人的調整（檢查第一個字母試圖通過針頭重複之前），現在看起來是這樣的：
public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
{
long i = startpos;
fixed (byte* H = Haystack) fixed (byte* N = Needle)
{
for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
{
if (*hNext == *N)
{
bool Found = true;
for (byte* hInc = hNext+1, nInc = N+1, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
if (Found) return i;
}
}
return -1;
}
}
現在，它需要完全相同的時間來執行的安全可靠。我的問題再次 - 任何想法爲什麼？難道它不是更快，因爲它是不安全的，並與指針相比，當與安全相比？
我會爲字節數組實現[this algorithm]（http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm）並再次測試。 – I4V
那麼，大多數字符串比較函數和'IndexOf'歸結爲內部CLR調用，通常是'InternalFindNLSStringEx'或'InternalCompareString'。本地CLR實現可能會更快。 – vcsjones
好的，現在你已經有了一個指針算術解決方案，如果你想使它更快，你將不得不開始考慮在那裏實際上正在做什麼機器操作。例如：更快的方法是：將一個字節從32位字中移出四次，或者製作四個掩碼，一個字節位於四個位置，將字節數組視爲int數組，並檢查每個int以查看與掩碼進行「與」操作時是否匹配任何掩碼？後者可能會快幾個週期。這是人們在優化此算法時所做的一些事情。 –