6

これは難しい質問ではないはずですが、続行する前に誰かにバウンスしてもらいたいと思います。これらの予想されるアクティビティに基づいて、使用するデータ構造を決定する必要があります。

  1. ソートされた順序で頻繁に繰り返す必要があります（先頭から開始）。
  2. ソートされたビューから任意の要素を削除/復元する必要があります。
  3. 後で、データを頻繁に再利用して、複数の並べ替えられたビューを操作します。
  4. また、後で、ソートされたビュー内の要素の位置を頻繁に変更します。

ちなみに、これはJavaです。

私の最善の推測は、カスタムのリンクされたハッシュセット（リンクを並べ替えられた順序で配置するため）をロールするか、ツリーセットを使用することです。しかし、私はまだ完全にはわかりません。推奨事項？

編集：任意の削除/復元のため、おそらくツリーセットに固執する必要がありますよね？

実際、必ずしもそうとは限りません。うーん...

4

2 に答える 2

3

データ構造に一意ではない値を保存する場合は、Google コレクションの標準の LinkedHashSet または LinkedMultiset を使用します。

于 2010-02-21T10:17:12.770 に答える
3

理論的には、適切なデータ構造は多方向ツリー、できれば B+ ツリーのようなものだと思います。従来、これはディスクベースのデータ構造ですが、最新のメイン メモリには、キャッシュと仮想メモリのレイヤーがあるため、多くの類似した特性があります。

B+ ツリーの順序反復は非常に効率的です。これは、(1) リーフ ノードのリンクされたリストのみを反復処理するためです。ブランチ ノードは不要であり、(2) 非常に優れた局所性が得られます。

任意の要素の検索、削除、および挿入は、バランスの取れたツリーと同様に log(n) ですが、定数係数は異なります。

ツリー内での再ソートは、ほとんどの場合、ブロックのリンク リスト (リーフ ノード) を操作するときに優れたパフォーマンスを発揮するアルゴリズムを選択することであり、リーフ ノードを使用する必要性を最小限に抑えます。アイテムがブランチ ノードで並べ替えられたら、リーフ ノードを介して要約情報を伝播するだけです。

しかし- 実用的には、これは必要であると確信している場合にのみ行うことです。標準的なコンテナを使用した方がよい可能性は十分にあります。アルゴリズム/データ構造の最適化は最良の最適化ですが、まだ時期尚早な場合もあります。

于 2010-02-21T11:19:08.877 に答える