2

さまざまな構成でプログラムを実行してから統計データを読み込んでいます。a6つの構成（ 、、b...、 ）があるとしましょうf。構成は直線的に変化しない可能性があるため、測定値を表と考えると、表にギャップがある可能性があります。問題は、これらの統計データをメモリに構造化することです。

最初に頭に浮かぶのは、これらの構成を動的に割り当てられた6つの深さの配列に読み取ることです。

struct data ******measurements;

これで問題なく動作します。メモリのオーバーヘッドはほとんどなく（実際にデータが割り当てられる構成のみ）、アクセス時間はO(1)です。

ほとんどの人がポインタを好まないという事実に******加えて、これには、構成を追加することは配列に次元を追加することを意味し、配列への読み取り/書き込みが関数にカプセル化されない限り醜くなる可能性があるという欠点があります。（書き込みは、必要に応じて割り当てを処理するためにすでにカプセル化されているため、実際にはそれほど大きな問題ではありません）。

頭に浮かぶもう1つのアイデアは、AVLツリーなどを使用するためのマップを使用するstruct configことstruct dataです（私はすでに持っているので、実装のオーバーヘッドはありません）。これにより、構成パラメーターを拡張する問題は解決されますが、アクセス時間がに短縮されO(log(n))ます。

O(log(n))テストの数は、違いを生むためにかなり多くなる可能性があります。

私の質問は：ここで6つの深さのネストされた配列を使用することは正当化されますか？それとも、これを行うためのより良い方法はありますか？

4

3 に答える 3

2

現在の設定は O(1) ではなく、O(k) であることに注意してください。ここで、k は次元数です。バランスの取れたツリーでは、とにかく O(log 2^k) == O(k) になります (各次元には 2 つの選択肢があると想定していますが、問題ではありません...ここでは単なる定数です)。ただし、バランスの取れたツリーの実装では、より大きなオーバーヘッドが予想される場合と予想されない場合があります。

できることは、typedef とゲッター/セッター関数 (できればインライン化可能) でインターフェイスを抽象化してから、必要な実装を使用することです。そうすれば、ポインターをそれほど処理する必要がなくなり、内部の構造体を引き続き使用できます。

于 2012-06-11T17:14:58.503 に答える
2

X ツリーは、高次元データの効率的な格納と検索のための一般的な選択肢です。リンクされているウィキペディアの記事は単なるスタブですが、より信頼できる情報源を示しています。

これらは基本的に R ツリーの改良版であり、オーバーラップを最小限に抑えるように最適化されています。

私は手に負えない交流の実装を知りません。

于 2012-06-11T17:47:35.277 に答える
1

実際のパフォーマンスのボトルネック (メモリの浪費以外) は計算ではなく、発生する間接参照とキャッシュ ミスの数です。これらは、インデックスなどの計算を数百から数千倍も支配する可能性があります。したがって、最善の選択は、間接参照の数を減らし、計算に少し投資することです。私が見る限り、これは 6 つのインデックスをハッシュすることによって行うのが最善です。これにより、最初にハッシュ テーブルに格納されている値 (おそらくポインター) を検索し、次に関心のあるデータを直接フェッチするという間接的な作業が 2 つに減ります。

于 2012-06-12T08:15:45.113 に答える