インデックスが「アイテムのコレクションの識別子」を兼ねる配列があり、配列の内容はグループ番号です。グループ番号は 0..N の有限範囲に収まります。ここで、N << length_of_the_array です。したがって、すべてのエントリが何度も複製されます。現在、グループ番号を表すために 2 バイトを使用する必要があります (> 1000 でも < 6500 の場合もあります)。これは、重複した性質のために多くのメモリを消費することになります。
完全な配列のサイズが複数の MB になる可能性があるため、この配列のスペースを最適化する方法はありますか。関連する最適化アルゴリズム/手法へのポインタを高く評価します。参考までに、私が使用しているプログラミング言語は cpp です。
それでも任意の要素への効率的なランダムアクセスが必要ですか? それとも、index->group マップのスペース効率の良いシリアライゼーションについて考えていますか?
それでも効率的なランダムアクセスが必要な場合は、単一の配列ルックアップも悪くありません。最悪の場合、単一のキャッシュ ミスです。最悪の場合、ページ フォールト、または TLB ミスの可能性が高いですが、ほんの数 MB の場合はありそうにありません)。
並べ替えられたランレングス エンコードされたリストは、(繰り返し回数のプレフィックス合計の配列を検索することによって) バイナリ検索できますが、重複を一緒に保つために時々リストを並べ替えることができる場合にのみ機能します。
重複を少なくともある程度グループ化できない場合、ランダムアクセスを可能にするためにできることはあまりありません.
パックされた 12 ビット エントリは、キャッシュ ミスを大幅に減らすのに十分でない限り、おそらく問題に値しません。正しいアドレスを生成するための 2 つの乗算命令と、目的の値を含む 16b ロードでのシフトおよびマスク命令は、キャッシュ ミスに比べてオーバーヘッドが大きくありません。パックされたビットフィールドへの書き込みアクセスは遅く、アトミックではないため、これは深刻な欠点です。構造体を使用してビットフィールドをパックするようにコンパイラーを取得することは、コンパイラー固有の場合があります。たぶん、char配列を使用するのが最善でしょう。