3

配列全体に 1 と 0 がランダムに広がっている配列があります。

int arr[N] = {1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1....................N}

ここで、配列内のすべての 1 をできるだけ早く取得したいのですが、配列の正確な位置 (インデックスに基づく) を失うべきではないため、並べ替えオプションは無効です。したがって、残っている唯一のオプションは線形検索、つまり O(n) です。これよりも優れたものはありますか。

リニア スキャンの背後にある主な問題は、スキャンを X 回実行する必要があることです。したがって、最初の線形スキャンが発生したら、このリストを維持する何らかの他のデータ構造が必要であると感じています。これにより、線形スキャンを何度も実行する必要がなくなります。

Let me be clear about final expectations-

配列の特定の範囲内の 1 の数を見つける必要があるだけです。正確には、配列内の 1 の数を 40 ～ 100 の範囲内で見つける必要があります。したがって、これはランダムな範囲になる可能性があり、その範囲内で 1 のカウントを見つける必要があります。範囲の要件が異なるため、配列を何度も反復する必要があるため、合計とすべてを行うことはできません

4

6 に答える 6

8

並べ替えを線形検索のより高速な代替手段と見なしたことに驚いています。

それらがどこで発生するかわからない場合は、線形検索よりも良い方法はありません。おそらく、ビットまたはcharデータ型を使用した場合、いくつかの最適化を行うことができますが、これをどのように使用するかによって異なります。

これに対して実行できる最善の最適化は、分岐予測を克服することです。各値は 0 または 1 であるため、これを使用して、1 インデックスを格納するために使用される配列のインデックスを進めることができます。

簡単なアプローチ:

int end = 0;
int indices[N];

for( int i = 0; i < N; i++ )
{
    if( arr[i] ) indices[end++] = i;  // Slow due to branch prediction
}

分岐なし:

int end = 0;
int indices[N];

for( int i = 0; i < N; i++ )
{
    indices[end] = i;
    end += arr[i];
}

[編集]上記をテストしたところ、分岐なしのバージョンはほぼ 3 倍高速であることがわかりました (ランダムに配置された 1 億要素配列での 20 回の繰り返しで 4.36 秒対 11.88 秒)。

ここに戻って結果を投稿すると、要件が更新されていることがわかります。あなたが望むものは、動的プログラミングのアプローチで本当に簡単です...

行うことは、1 要素大きい新しい配列を作成することだけです。この配列には、配列の先頭から現在のインデックスまで (ただし、インデックスは含まれません) の 1 の数が格納されます。

arr   :   1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1
count : 0 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 5 6 6 6 6 7

（上にオフセットarrしたので、より整列します）

これで、O(1) 時間で任意の範囲の 1 の数を計算できます。indexAとの間の 1 の数を計算するには、次のBようにします。

int num = count[B+1] - count[A];

明らかに、非分岐予測バージョンを使用して、最初にカウントを生成できます。これらすべてにより、すべてのクエリを合計する単純なアプローチよりもかなり高速化されるはずです。

int *count = new int[N+1];
int total = 0;

count[0] = 0;

for( int i = 0; i < N; i++ )
{
    total += arr[i];
    count[i+1] = total;
}


// to compute the ranged sum:
int range_sum( int *count, int a, int b )
{
    if( b < a ) return range_sum(b,a);
    return count[b+1] - count[a];
}
于 2013-05-15T05:12:16.027 に答える
3

1 回のリニア スキャンで問題ありません。配列の範囲全体で複数のスキャンを探しているので、一定の時間で実行できると思います。どうぞ：

  1. 配列をスキャンして、キー = 配列のキー = シーケンス (1,2,3,4,5,6....) のビットマップを作成しますtuple<IsOne,cumulativeSum>。累積合計は、それらに遭遇した場合の 1 の加算です。

    配列 = 1 1 0 0 1 0 1 1 1 0 1 0

    タプル: (1,1) (1,2) (0,2) (0,2) (1,3) (0,3) (1,4) (1,5) (1,6) (0, 6) (1,7) (0,7)

  2. ケース 1: 累積合計の下限が 0 の場合。1 の数 [6,11] = 11 番目の累積合計 - 6 番目の累積合計 = 7 - 3 = 4

    ケース 2: 累積合計の下限が 1 の場合。 1 の数 [2,11] = 11 番目の累積合計 - 2 番目の累積合計 + 1 = 7-2+1 = 6

ステップ 1 は O(n)

ステップ 2 は 0(1)

全体の複雑さは間違いなく線形ですが、十分なメモリがある場合は、範囲を数回操作する必要があるタスクの場合、上記のアルゴリズムの方が優れているようです:)

于 2013-05-15T06:21:24.060 に答える
1

単純な線形配列データ構造である必要がありますか? または、たまたま必要なプロパティを持ち、必要な API を提供できるが、実装の詳細を非表示 (カプセル化) できる独自のデータ構造を作成できますか?

独自のものを実装でき、保証されたスパース性 (1 または 0 のいずれか) がある場合は、線形よりも優れたパフォーマンスを提供できる可能性があります。正確なストリームを保持する (または再生成できるようにする) 必要があることがわかりました。そのため、配列、ビットマップ、またはランレングス エンコーディングを格納する必要があります。(RLE は、ストリームが任意ではなく実際にランダムである場合は役に立ちませんが、かなりのスパース性またはいずれかの長い文字列を含むパターンがある場合は非常に役立ちます。たとえば、ビットマップ画像の白黒ラスターは、多くの場合、 RLE)。

ストリームがまばらであることが保証されているとしましょう --- たとえば、ビットの 10% 以下が 1 になること (または、逆に 90% 以上が 1 になること)。その場合は、RLE でソリューションをモデル化し、すべての 1 のカウントを維持することができます (ビットを設定すると単純に増加し、ビットをクリアすると減少します)。これらの要素の任意の範囲の設定ビット数をすばやく取得する必要がある場合は、単一のカウンターの代わりに、ストリームのパーティション用に便利なサイズのカウンターの配列を使用できます。(この場合、便利なサイズとは、メモリ内、キャッシュ内、またはレジスタ セット内に簡単に収まるものを意味しますが、合計 (完全に範囲内にあるすべてのパーティション) と線形スキャンの間の合理的なトレードオフを提供します。

非常に非常に大きなストリームの場合、パーティションの合計の多層「インデックス」を使用することもできます --- 最大の (最も粗い) 粒度から「フラグメント」に向かっていずれかの端までトラバースします (パーティションの次のレイヤーを使用)合計)、小さなフラグメントのみの線形検索で終了します。

明らかに、そのような構造は、構造の構築と維持の複雑さ (挿入には追加の操作が必要であり、RLE の場合、追加/先頭追加以外の場合は非常にコストがかかる可能性があります) と、任意に長い線形検索/インクリメントを実行する費用との間のトレードオフを表しています。スキャンします。

于 2013-05-15T06:29:23.590 に答える
0

C (または派生言語) を使用していますか? もしそうなら、配列のエンコーディングを制御できますか? たとえば、ビットマップを使用してカウントできるとします。ビットマップの優れた点は、ルックアップ テーブルを使用してカウントを合計できることです。ただし、サブ範囲の端が 8 で割り切れない場合は、最後の部分的なバイトを特別に処理する必要がありますが、速度は大幅に向上します。 .

そうでない場合は、少なくとも 1 バイトとしてエンコードできますか? その場合、スパース性が存在する場合は、スパース性を利用できる可能性があります (より具体的には、ゼロのマルチ インデックス スワスが頻繁に存在することを期待します)。

だから：

u8 input = {1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1....................N};

あなたは（未テスト）のようなものを書くことができます：

uint countBytesBy1FromTo(u8 *input, uint start, uint stop)
{ // function for counting one byte at a time, use with range of less than 4,
  // use functions below for longer ranges
  // assume it's just one's and zeros, otherwise we have to test/branch
    uint sum;
    u8 *end = input + stop;
    for (u8 *each = input + start; each < end; each++)
        sum += *each; 
    return sum;
}

countBytesBy8FromTo(u8 *input, uint start, uint stop)
{
    u64 *chunks = (u64*)(input+start);
    u64 *end = chunks + ((start - stop) >> 3);
    uint sum = countBytesBy1FromTo((u8*)end, 0, stop - (u8*)end);
    for (; chunks < end; chunks++)
    {
        if (*chunks)
        {
            sum += countBytesBy1FromTo((u8*)chunks, 0, 8);
        }
    }
}

基本的なトリックは、ターゲット配列のスライスを、言語が一度に見ることができる単一のエンティティにキャストし、その値のいずれかがゼロであるかどうかを推論によってテストし、ブロック全体をスキップする機能を利用することです。ゼロが多いほど、うまく機能します。大きなキャスト整数が常に少なくとも 1 つある場合、このアプローチはオーバーヘッドを追加するだけです。u32 を使用する方がデータに適している場合があります。または、1 と 8 の間に u32 テストを追加すると役立ちます。ゼロが 1 よりもはるかに一般的なデータセットの場合、私はこの手法を大いに活用しました。

于 2013-05-15T06:06:17.360 に答える
0

並べ替えが無効なのはなぜですか? 元の配列のクローンを作成し、クローンを並べ替え、必要に応じて の位置をカウントおよび/またはマークすることができ1ます。

于 2013-05-15T06:11:41.127 に答える