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

ゼロ以外の値が比較的まれな場合、使用できるトリックの 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 バイトの倍数にすることです。これにより、ループの完了後に最後の数バイトを実行することを心配する必要がなくなります。

これは純粋に推測であり、単純なループよりも時間がかかるほど十分に配列が疎になるポイントがあるため、これについてタイミング調査を行うことをお勧めします。

私が持つであろう 1 つの質問は、配列のゼロ以外の要素のオフセットのベクトルで何をしているのか、ベクトルをなくすことができるかどうかということです。別の質問は、要素を配列に配置するときにベクトルを構築できるかどうか、ベクトルが必要かどうかです。

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 に答える