c# – 在byte []中查找byte []的速度和在string中查找字符串 –
我有一个任务,我需要在文件中查找序列.在进行测试应用程序时,我将文件读取为字符串(File.ReadAllText)并使用string.IndexOf来查找序列.当我尝试用字节实现相同的算法(将文件作为字节数组读取并在字节数组中查找字节数组)时,我注意到在byte []中查找byte []的速度大约是在字符串中查找字符串的3倍.我确保彻底检查它,完全相同的代码,一个使用byte []和其他使用字符串,执行时需要3倍 – 比如16s for byte vs~5s for string.
为了查找字节数组,我使用了这里描述的方法byte[] array pattern search.为了查找字符串,我使用了字符串类的内置IndexOf函数.这是我试过的byte []的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如何处理在字符串中查找字符,它做什么样的优化,它使用什么算法?是否有比我在这里使用的算法更快的算法?也许有人知道我在这里做错了什么,所以它需要的时间比它应该多?我真的不明白如何在字符串中查找字符串的速度是在byte []中查找byte []的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,hNext++) { if (*hNext == *N) { bool Found = true; for (byte* hInc = hNext+1,nInc = N+1,hInc++) ; if (Found) return i; } } return -1; } } 现在,执行安全的时间与完全相同.我的问题又来了 – 任何想法为什么?与安全相比,它不应该更快,因为它不安全并且使用指针操作吗? 解决方法
因为字符串搜索算法已经过大量优化;它是用紧密的非托管代码编写的,不需要花时间检查数组边界.如果你以同样的方式优化你的字节搜索算法,它会同样快;字符串搜索算法使用您正在使用的相同的天真算法. 你的算法很好 – 这是标准的“幼稚”搜索,尽管凯文声称,但天真的算法在实践中几乎总是在典型数据上最快.在现代硬件上浏览阵列寻找字节非常快.这取决于你的问题的大小;如果你在人类基因组中间寻找一条长DNA链,那么Boyer-Moore完全值得花费预处理.如果你在一个20 KB的文件中寻找0xDEADBEEF,那么如果它被有效实现你就不会打败天真的算法. 为了获得最大速度,您应该在此处关闭安全系统并使用不安全的指针算法编写代码. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |