5

いくつかの連続したコンテナーを操作し、この配列内でデータ (およびおそらくフリー レンジ) を含む連続した範囲のインデックスをすばやく取得できるデータ構造を想像してみてください。この範囲を「ブロック」と呼びましょう。各ブロックは、その先頭と末尾のインデックスを認識しています。

struct Block
{
    size_t begin;
    size_t end;
}

配列を操作すると、データ構造がブロックを更新します。

    array view          blocks [begin, end]
--------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9     [0, 9]

pop 2                   block 1 splitted

0 1 _ 3 4 5 6 7 8 9     [0, 1] [3, 9]

pop 7, 8                block 2 splitted

0 1 _ 3 4 5 6 _ _ 9     [0, 1] [3, 6] [9, 9]

push 7                  changed end of block 3

0 1 _ 3 4 5 6 7 _ 9     [0, 1] [3, 7] [9, 9]

push 5                  error: already in

0 1 _ 3 4 5 6 7 _ 9     [0, 1] [3, 7] [9, 9]

push 2                  blocks 1, 2 merged

0 1 2 3 4 5 6 7 _ 9     [0, 7] [9, 9]

プロファイリングの前から、ブロックの取得速度がアプリケーションのパフォーマンスの基礎となることはわかっています。基本的な使用法は次のとおりです。

  • 非常に頻繁に連続ブロックを取得
  • 非常にまれな挿入/削除
  • ほとんどの場合、ブロック数を最小限に抑えたい (断片化を防ぐ)

すでに試したこと：

  1. std::vector<bool>+ std::list<Block*>. 変更ごとに: true/false を に書き込みvector、それを for ループでトラバースして を再生成しlistます。ブロックのクエリごとに が返されlistます。私たちが望んでいたよりも遅い。

  2. std::list<Block*>リストを直接更新するため、トラバースはありません。リストを返します。デバッグ/テストする多くのコード。

質問:

  1. そのデータ構造には一般的な名前がありますか?
  2. そのようなデータ構造は既に実装されていますか (デバッグおよびテスト済み)?
  3. いいえの場合、そのようなデータ構造の高速で堅牢な実装についてアドバイスできますか?

私の説明が明確でない場合は申し訳ありません。

編集

このコンテナーの典型的なアプリケーションは、バッファー (システムまたは GPU メモリ) の管理です。GPU の場合、単一の頂点バッファーに大量のデータを格納してから、一部の領域を更新/無効化できます。描画呼び出しごとに、描画するバッファ内の有効な各ブロックの最初と最後のインデックスを知る必要があり (多くの場合、1 秒間に 10 分の 1 から数百回)、場合によっては (1 秒に 1 回) データのブロックを挿入/削除する必要があります。

もう 1 つのアプリケーションは、カスタムの「ブロック メモリ アロケータ」です。その目的のために、侵入型リンクリストを介して「Alexandrescu A. - Modern C++ Design」本に実装された同様のデータ構造。より良い選択肢を探しています。

4

4 に答える 4

4

単純な赤黒ツリーまたは B+ ツリーのいずれかの構造に似たツリーを試してみることをお勧めします。

于 2013-08-20T22:49:54.263 に答える
1

最初の解決策 (bool のベクトル + ブロックのリスト) は良い方向のようですが、リストを最初から完全に再生成する (またはベクトル全体を調べる) 必要はないことに注意してください。新しく変更されたインデックスを修正する必要がある場所を見つけ、リスト上の適切なブロックを分割/マージします。

リストのトラバーサルが長すぎることが判明した場合は、代わりにブロックのベクトルを実装できます。この場合、各ブロックは開始インデックスにマップされ、各穴には穴がどこで終わるかを示すブロックがあります。常に次のブロックにジャンプするため、このベクトルをリストと同じくらい速くトラバースできます (ブロックの終わりを決定するために 1 回の O(1) ルックアップ、次のブロックの開始を決定するために別の O(1) ルックアップ)。ただし、(プッシュ/ポップの場合) インデックスに直接アクセスすることもでき、二分探索でそれらを囲んでいるブロックを見つけ出すこともできます。それらは実際のブロックのように)、挿入/削除でも O(1) である必要があります.重要な部分は、ブロック間には常に単一の穴があり、その逆も同様です.

于 2013-08-20T23:20:03.307 に答える
0

Why are you using a list of blocks? Do you need stable iterators AND stable references? boost::stable_vector may help. If you don't need stable references, maybe what you want is to write a wrapper container that contains a std::vector blocks and a secondary memory map of size blocks.capacity() which is a map from iterator index (which is kept inside returned iterators to real offset in the blocks vector) and a list of currently unused iterator indices.

Whenever you erase members from blocks, you repack blocks and shuffle the map accordingly for increased cache coherence, and when you want to insert, just push_back to blocks.

With block packing, you get cache coherence when iterating at the cost of deletion speed. And maintain relatively fast insert times.

Alternatively, if you need stable references and iterators, or if the size of the container is very large, at the cost of some access speed, iteration speed, and cache coherency, you wrap each entry in the vector in a simple structure that contains the real entry and an offset to the next valid, or just store pointers in the vector and have them at null on deletion.

于 2013-12-13T07:21:58.810 に答える