1

重複なしと順序の維持の要件を持つ要素を保存する必要があるという問題に取り組んでいます。LinkedHashSet私の両方の要件を満たしていたので、私は一緒に行くことにしました。

このコードがあるとしましょう：

 LinkedHashSet hs = new LinkedHashSet();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  if(hs.contains("D")){
       //do something to remove elements added after"D" i-e remove "E", "C" and "F"
       //maybe hs.removeAll(Collection<?>c) ??
   }

これらの要素を削除するロジックを教えてください。

間違ったデータ構造を使用していますか? もしそうなら、より良い代替手段は何ですか？

4

4 に答える 4

3

LinkedHashSet を使用している場合は、イテレータを使用して削除を行う必要があると思います。つまり、要素を見つけて、末尾に到達するまで削除し続けます。これは O(n) になりますが、(二重にリンクされたリストとハッシュセットを使用して) 独自の LinkedHashSet を作成した場合でも、O(1) でリンクされたリストを切り取ることができるように、生のリンク構造にアクセスできますが、 O(n) コストが再び発生する場所である HashSet から、リンクされたリストから切り取ったすべての要素を削除する必要があります。

要約すると、要素を削除してから、その要素へのイテレータを保持し、最後まで要素を削除し続けます。LinkedHashSet が必要な呼び出しを公開しているかどうかはわかりませんが、おそらくそれを理解できるでしょう。

于 2013-04-08T22:49:41.453 に答える
0

したがって、上記のいくつかのことを試した後、別のデータ構造を実装することにしました。この問題の O(n) に問題はなかったので (データが非常に小さいため)

私はグラフを使用しました。このライブラリは非常に便利でした: http://jgrapht.org/

私がやっていることは、すべての要素を頂点として追加し、DirectedGraphそれらの間にエッジを作成することです (エッジは、別の無関係な問題の解決にも役立ちました)。要素を削除するときは、次の疑似コードで再帰関数を使用します。

removeElements(element) {

tempEdge = graph.getOutgoingEdgeFrom(element)
if(tempEdge !=null)
   return;
tempVertex = graph.getTargetVertex(tempEdge)
removeElements(tempVertex)
graph.remove(tempVertex)

}

グラフ DS がこの種の問題に適していないことには同意しますが、私の条件下では、これは完全に機能します...乾杯!

于 2013-07-25T17:46:08.823 に答える
0

ここでの基本的な問題は、キーと値のマッピングを表す「マップ」と、挿入順序を表す「リスト」の 2 つのデータ構造を維持する必要があることです。

特定のポイント以降の要素をすばやく削除できる「マップ」組織と「リスト」組織があります。たとえば、さまざまな種類の順序付けされたツリーと、配列ベースとチェーンベースのリストの両方 (ポイントを見つけるためのコストを法とする)。

ただし、2 つのデータ構造から N 個の要素を削除することは不可能のようですO(N)。2 番目のデータ構造からそれらを削除するには、削除されるすべての要素にアクセスする必要があります。（実際、これを数学的に証明できると思います...）

つまり、現在使用しているデータ構造よりも複雑なデータ構造はありません。

(カスタム コレクション クラスを使用して) パフォーマンスを改善できる領域は、反復子の明示的な使用を避けることです。イテレーターと標準のイテレーター API を使用すると、コストはO(N)データ構造内の要素の総数になります。削除された要素の数でこれを行うことができO(N)ます...ハッシュエントリノードにもシーケンスの次/前のリンクがある場合。

于 2013-04-08T23:09:47.667 に答える