2

一部の部分では非常に密になり、他の部分では非常にまばらになる可能性のあるビット配列があります。配列は 2**32 ビットまで大きくなる可能性があります。メモリ内でより効率的に処理できるように、オフセットと長さを含む一連のタプルに変換しています。ただし、これは10101010100011のようなものでは効率が悪い場合があります。これをメモリに保存する良い方法はありますか?

4

5 に答える 5

2

私の理解が正しければ(offset, length)、1 ビットの実行を表すために のタプルを使用していますか? もしそうなら、より良いアプローチは、パックされたビットフィールドの実行を使用することです. 密集した領域では効率の良い配列が得られ、密集していない領域では暗黙のゼロが得られます。たとえば、C++ では、表現は次のようになります。

// The map key is the offset; the vector's length gives you the length
std::map<unsigned int, std::vector<uint32_t> >

ルックアップは、問題のビット位置の前にキーを見つけ、ビットがそのベクトルに含まれるかどうかを確認することで構成されます。存在する場合は、ベクトルからの値を使用します。それ以外の場合は 0 を返します。例:

typedef std::map<unsigned int, std::vector<uint32_t> > bitmap; // for convenience
typedef std::vector<uint32_t> bitfield; // also convenience

bool get_bit(const bitmap &bm, unsigned int idx) {
  unsigned int offset = idx / 32;
  bitmap::const_iterator it = bm.upper_bound(offset);

  // bm is the element /after/ the one we want
  if (it == bm.begin()) {
    // but it's the first, so we don't have the target element
    return false;
  }

  it--;

  // make offset be relative to this element start
  offset -= it.first;
  // does our bit fall within this element?
  if (offset >= it.second.size())
    return false; // nope

  unsigned long bf = it.second[offset];
  // extract the bit of interest
  return (bf & (1 << (offset % 32))) != 0;
}
于 2009-08-10T02:01:41.850 に答える
1

もっと知っておくと役に立ちます。「非常にまばら/密」とは、何百万もの連続する 0/1 を意味するのでしょうか、それとも 0 または 1 に非常に近い 0 の局所的 (どの程度局所的?) な割合を意味するのでしょうか? どちらかの値が優勢ですか? ランレングス エンコーディングを効果的にするパターンはありますか? このデータ構造をどのように使用しますか? (ランダム アクセス? アクセスされたインデックスの分布はどのようなものですか? 巨大なチャンクはまったくアクセスされないか、ほとんどアクセスされませんか?)

1 秒あたり数十億ビットのレートで 40 億ビットすべてにランダムにアクセスして変更することはないと推測できます。ローカル レベルで驚くほど疎/密である場合 (5 ビットまたは 10 ビットを除いて、100 万の連続するビットが同じである可能性が高いなど)、または大規模な繰り返しまたはパターンでいっぱいでない限り、データ構造の選択は依存するというのが私の推測です。データの性質よりも、配列がどのように使用されるかについてです。

于 2009-08-10T02:08:28.300 に答える
0

これらのうち、一度にいくつ記憶しておくつもりですか?

私が見る限り、2**32 ビット = 512M で、ギグの半分にすぎません。これは、最近ではあまり多くのメモリではありません。それと何か良いことはありますか？

サーバーに十分なRAMがあり、起動時にすべて割り当ててからメモリに保持すると、ネットワーク処理スレッドは一定時間内にわずか数命令で実行でき、あらゆるワークロードに対応できるはずです.

于 2009-08-10T20:00:12.463 に答える
0

バイソンのソースコードをチェックしてください。biset の実装を見てください。さまざまな密度のビット配列を処理するために、いくつかのフレーバーの実装を提供します。

于 2009-08-10T04:14:21.463 に答える
0

物事を構造化する方法は、データが何であるかによって異なります。大量のデータを表現しようとすると、ゼロまたは 1 の連続が長くなる必要があります。これにより、それを表現する必要がなくなります。これが当てはまらず、1 と 0 の数がほぼ同じである場合は、すべてのメモリを使用したほうがよいでしょう。

これを圧縮の問題と考えると役立つかもしれません。圧縮が効果的であるためには、圧縮が機能するためには、パターン (またはスペース全体で使用されるアイテムの制限セット) と不均一な分布が必要です。すべての要素が使用され、均等に分散されている場合、圧縮は困難であるか、実際のデータよりも多くのスペースが必要になる可能性があります。

0 と 1 の実行のみ (1 よりも多い) がある場合は、オフセットと長さを使用するのが理にかなっている可能性があります。一貫性のない実行がある場合は、オフセット、長さ、および値を持つビット配列としてビットをコピーできます。

上記がどれほど効率的かは、1 または 0 の連続数が多いかどうかによって異なります。メモリを再表示するためにメモリを使用しているのではなく、メモリ自体を使用していないことを確認するように注意する必要があります (つまり、メモリを表現するためにメモリを使用してから、メモリに配置するだけです)。

于 2009-08-10T03:27:47.313 に答える