我需要遍历一组字节,搜索一个 4 字节的值(所有 4 个字节都相同)。数据的长度是可变的,这些字节可以在数据中的任何地方;我正在寻找第一个实例。我试图找到可能最快的实现,因为此逻辑在我的代码的关键部分运行。
这只会在 Windows 下的 x86 和 x64 上运行。
typedef unsigned char Byte;
typedef Byte* BytePtr;
typedef unsigned int UInt32;
typedef UInt32* UInt32Ptr;
const Byte MARKER_BYTE = 0xAA;
const UInt32 MARKER = 0xAAAAAAAA;
UInt32 nDataLength = ...;
BytePtr pData = ...;
BytePtr pEnd = pData + nDataLength - sizeof ( UInt32 );
// Option 1 -------------------------------------------
while ( pData < pEnd )
{
if ( *( (UInt32Ptr) pData ) == MARKER )
{
... // Do something here
break;
}
pData++;
}
// Option 2 -------------------------------------------
while ( pData < pEnd )
{
if ( ( *pData == MARKER_BYTE ) && ( *( (UInt32Ptr) pData ) == MARKER ) )
{
... // Do something here
break;
}
pData++;
}
我认为选项 2
更快,但我不确定我的推理是否正确。
选项 1
首先从内存中读取 4 个字节,将其与 4 字节常量进行检查,如果未找到,则进入下一个字节并重新开始。从内存中准备好的下一个 4 字节将与已读取的 3 个字节重叠,因此需要再次获取相同的字节。我的 4 字节标记之前的大多数字节将被读取两次。
选项 2
一次仅读取 1 个字节,如果该单个字节匹配,则从该地址读取完整的 4 字节值。这样,所有字节只读一次,只有 4 个匹配的字节被读两次。
我的推理是正确的还是我忽略了什么?
在有人提出之前,是的,我确实需要执行这种优化。 :)
编辑:请注意,此代码只能在基于 Intel/AMD 的计算机上运行。我不在乎其他架构是否无法运行它,只要正常的 x86/x64 计算机(台式机/服务器)运行它没有问题或性能损失。
编辑 2:如果有帮助,编译器是 VC++ 2008。
最佳答案
您也可以尝试 Boyer-Moore 方法。
pData = start + 3;
int i;
while(pData < pEnd) {
for(i = 0; i < 4; ++i) {
if (*(pData-i) != MARKER_BYTE) {
pData += 4-i;
break;
}
}
if (i == 4) {
/* do something here with (pData-3) */
break;
}
}
如果幸运的话,它只会测试每四个字节,直到找到匹配为止。
对于像这样的短模式,任何人都可以猜测这比测试每个字节快还是慢。
关于c - 这两个循环中哪个更快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10607591/