从C++中的字节数组中提取非零索引的最快方法是什么

Question

我有一个字节数组

unsigned char* array=new unsigned char[4000000];
 ...

我想得到数组中所有非零元素的索引.

当然,我可以做到以下

for(int i=0;i<size;i++)
{
    if(array[i]!=0) somevector.push_back(i);
}

有比这更快的算法吗？

更新1我可以看到多数回答是否定的.我希望有一些我不知道的神奇位操作.有些人建议排序,但在这种情况下并不可行.但是非常感谢你的所有答案.

更新2自此问题发布4年零4个月后,@ wim建议这个答案看起来很有希望.

Answer 1

对于大部分为零的字节数组（稀疏数组），您可以通过一次比较 4 个字节来利用 32 位 CPU。实际的比较一次完成 4 个字节，但是如果任何字节非零，那么您必须确定 unsigned long 中的哪些字节非零，这样会花费更多的精力。如果数组确实很稀疏，那么比较节省的时间可能会补偿确定哪些字节非零的额外工作。

最简单的方法是将 unsigned char 数组的大小设置为 4 字节的某个倍数，这样您就不必担心循环完成后执行最后几个字节。

我建议对此进行时序研究，因为它纯粹是推测性的，并且在某个点上，数组变得足够不稀疏，这将比简单的循环花费更多的时间。

我要问的一个问题是，您如何处理数组的非零元素的偏移量向量，以及是否可以消除该向量。另一个问题是，如果您需要向量，是否可以在将元素放入数组时构建向量。

unsigned char* array=new unsigned char[4000000];
......
unsigned long *pUlaw = (unsigned long *)array;

for ( ; pUlaw < array + 4000000; pUlaw++) {
    if (*pUlaw) {
        // at least one byte is non-zero
        unsigned char *pUlawByte = (unsigned char *)pUlaw;
        if (*pUlawByte)
            somevector.push_back(pUlawByte - array);
        if (*(pUlawByte+1))
            somevector.push_back(pUlawByte - array + 1);
        if (*(pUlawByte+2))
            somevector.push_back(pUlawByte - array + 2);
        if (*(pUlawByte+3))
            somevector.push_back(pUlawByte - array + 3);
    }
}