9

多くのポインターを格納する複雑なツリー データ構造をコーディングしています。ポインター自体は多くのスペースを占有しますが、これは私が期待しているものです。

ですから、これに関する例があるかどうかを尋ねるためにここにいます。例: 64 ビット データ型の場合、ポインターが指しているデータが確実に連続している場合、32 ビット以下のポインターを使用できますか?

リンクされたデータ構造の透過的なポインター圧縮という論文を見つけましたが、もっと簡単な解決策があると思いました。

アップデート：

オクトリーです。GPU に関するこれに関する論文はGigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenesで、GPU では 15 ビット ポインターを使用します。

4

5 に答える 5

5

ポインターを使用する代わりに、配列へのインデックスを使用します。インデックスはshort、配列の長さが 65536 未満の場合はa 、2147483648 未満の場合はint32_tになります。

任意のポインターは実際にはメモリ内のどこにでもある可能性があるため、数ビット以上短縮する方法はありません。

于 2013-01-23T04:03:17.170 に答える
1

ポインタの使用に多くのスペースが必要な場合：

ポインターの配列を使用し、ポインターをその配列内のインデックスに置き換えます。これにより、別の間接参照が追加されます。64k未満のポインターでは、[ short ]配列が必要です（Linux）

簡単な実装

#define   MAX_PTR  60000

void *aptr[MAX_PTR];
short nb = 0;

short ptr2index(void *ptr) {
  aptr[nb] = ptr;
  return (short)nb++;
}

void *index2ptr(short index) {
  return aptr[index];
}

... utilization ...

... short next; // in Class

Class *c = new Class();
mystruct->next = ptr2index((void *)c);

...

Class *x = (Class *)index2ptr(otherstruct->next);
于 2013-01-23T05:47:16.337 に答える
1

場合によっては、単に配列を使用してノードを保持することができます。の二分木ノードには、からへarr[i]の子があります。i！= 0の場合、その親はになります。もちろん、実際のポインタアドレスを計算するには、と言うことができます。これは実際には、ヒープに使用されるツリーのように、仕様によっていっぱいになるツリーのかなり一般的な実装です。arr[(i*2)+1]arr[(i+1)*2]arr[(i-1)/2]&arr[i]

ただし、ノードがその子を見つける方法を自分自身で知るためには、コンテナへのインデックスまたはポインタのいずれかが必要になる可能性があります。（それでも、2つのピースのうちの1つだけでは、少しフープジャンプを行う必要があります。簡単に行うには、両方のピースが本当に必要です。。しかし、覚えるのではなく計算する必要があるのは、あまり覚えないようにするときに支払う代償です。）かなりスペース効率の良いものを維持するには、ノードをダムダウンする必要があります。それらを基本的に構造体、あるいは値だけにして、ツリークラスにすべてのノード検索を実行させます。ノードへのポインターを渡すだけで、そのポインターは、コンテナーがノードのインデックス（したがって、その子がどこにあるか）を把握するために必要なすべてのものになります。また、ツリーをトラバースする関数には、ツリーポインターとノードポインターの両方を渡す必要があります。

ただし、これにより、ツリーが常にほぼ満杯にならない限り（つまり、リーフノードのほとんど/すべてが最後にない限り）、多くのスペースを節約できないことに注意してください。ツリーの最下部（最上部がルート）にないすべてのリーフノードについて、（（ノードサイズ）*（ツリーサイズ/ i））バイトのようなものを浪費します。

ツリーがいっぱいになっている、またはノードが特定の制限されたスペースにあることを期待できない場合は、ここで最適化することはそれほど多くありません。ツリーの要点は、ノードが子へのポインタを持っていることです。配列で偽造することもできますが、価値のあるツリーを作成するには、ノードの子を簡単に見つけることができる必要があります。

于 2013-01-23T04:39:09.013 に答える
1

1 つのオプションは、連続したメモリの大きなブロックを割り当てるカスタム アロケータを作成し、そこにノードを連続して格納することです。各ノードは、単純なポインター演算を使用してメモリにマップできる単純なインデックスによって参照できます (例: node_ptr = mem_block_ptr + node_index)。

すぐに、これらのメモリ ブロックが複数あるということは、特定のノードがどのメモリ ブロックに存在するかがわからないことを意味することに気付きます。ここでパーティショニングの出番です。水平および/または垂直のパーティショニングを選択できます。どちらも複雑さのレベルを大幅に高め、どちらにも長所と短所があります ( [1]と[2]を参照)。

ここで重要なことは、データが予測可能な方法で分割されるようにすることです。

参考文献:

  1. スケーラブルなデータベースの構築: さまざまなデータベース シャーディング スキームの長所と短所
  2. 37signals - Mr. Moore がシャーディングをパント
于 2013-01-23T05:46:03.180 に答える
0

あなたの問題に対処する非常に簡単な方法は、ポインタの使用を減らすことです (ばかげているようです)。

次の 2 つのアプローチを比較します。

template <typename T>
struct OctreeNaiveNode {
    T value;
    Point center;
    OctreeNaiveNode* parent;
    std::unique_ptr<OctreeNaiveNode> children[8];
}; // struct OctreeNaiveNode

// sizeof(OctreeNaiveNode) >= sizeof(T) + sizeof(Point) + 9 * sizeof(void*)

template <typename T>
struct OctreeNode {
    T value;
    Point center;
    std::unique_ptr<OctreeNode[]> children; // allocate for 8 only when necessary
}; // struct OctreeNode

// sizeof(OctreeNode) >= sizeof(T) + sizeof(Point) + sizeof(void*)

それはどのように機能しますか：

  • 親ポインターは単純な反復子にのみ必要です。ノードよりもはるかに少ない反復子を使用する場合は、深い反復子 (ルートまでの親のスタックを保存する反復子) を使用する方が経済的です。RB ツリーではあまりうまく機能しない (バランスを取る) ことに注意してください。
  • 単一の子ポインター: 子へのポインターの配列を持つ代わりに、子の配列へのポインターを作成します。8 つではなく 1 つの動的割り当てを意味するだけでなく (ヒープの断片化/オーバーヘッドが少ない)、ノード内の 8 つではなく 1 つのポインターも意味します。

オーバーヘッド：

  • Point = std::tuple<float,float,float>=> sizeof(T) + sizeof(Point) >= 64=> +100%
  • Point = std::tuple<double,double,double>=> sizeof(T) + sizeof(Point) >= 256=> +25%

したがって、圧縮ポインター戦略を掘り下げるのではなく、データ構造を作り直して、そもそもポインター/間接参照を少なくすることをお勧めします。

于 2013-01-25T08:04:04.690 に答える