7

我有一个字节数组

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 提出了这个看起来很有希望的答案。

4

5 回答 5

4

除非您的向量是有序的，否则如果您使用单线程程序，这是执行您想要执行的操作的最有效算法。您可以尝试优化要存储结果的数据结构，但及时这是您能做的最好的事情。

于 2012-09-22T16:36:00.787 回答
1

如果非零值相对较少，您可以使用的一个技巧是哨兵值：

unsigned char old_value = array[size-1];
array[size-1] = 1; // make sure we find a non-zero eventually

int i=0;

for (;;) {
  while (array[i]==0) ++i; // tighter loop
  if (i==size-1) break;
  somevector.push_back(i);
  ++i;
}

array[size-1] = old_value;
if (old_value!=0) {
  somevector.push_back(size-1);
}

这避免了在每次迭代时都检查索引和值。

于 2012-09-23T05:00:13.793 回答
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);
    }
}
于 2012-09-23T17:06:56.360 回答
0

提高速度的唯一方法是使用并发。

于 2012-09-22T16:34:45.887 回答
0

这并不是您问题的真正答案，但我试图想象您要解决的问题。

有时在对矩阵执行运算时（在数学意义上），当您知道绝大多数矩阵元素将为零（稀疏矩阵）时，可以改进运算。您完全不使用大数组，而是简单地存储指示非零元素的对 {index, value} 来进行这样的优化。

于 2012-09-22T16:42:50.657 回答