11

各構造の利点は何ですか？

私のプログラムでは、これらの手順を実行しますが、上記のどのデータ構造を使用する必要があるのか​​ 疑問に思っていました。

  1. ソートされていない配列を取得し、それらをソート済み構造体に追加します1。
  2. ソートされたデータをたどり、正しいデータを削除する
  3. データを追加 (決して削除しない) し、その構造を配列として返す
4

5 に答える 5

13

TreeSetまたはLinkedListをいつ使用するかをいつ知っていますか？各構造の利点は何ですか？

一般に、コレクションタイプは、必要な構造プロパティとパフォーマンスプロパティに基づいて決定します。たとえば、TreeSetはセットであるため、重複を許可せず、要素の挿入順序を保持しません。対照的に、LinkedListはリストであるため、重複を許可し、挿入順序を保持します。パフォーマンスの面では、TreeSetは挿入と削除を提供しますが、O(logN)最初または最後に挿入を提供し、選択した位置または削除に挿入を提供します。LinkedListO(1)O(N)

詳細はすべて、それぞれのクラスとインターフェースのjavadocsに詳しく説明されていますが、有用な要約はJavaコレクションのチートシートにあります。

ただし、実際には、コレクションタイプの選択は、アルゴリズムの設計と密接に関連しています。2つは並行して実行する必要があります。（アルゴリズムにプロパティX、Y、Zのコレクションが必要であると判断し、そのようなコレクションタイプが存在しないことを発見するのはよくありません。）

あなたのユースケースでは、TreeSetの方が適しているようです。O(N^2)ソートを行うために他のデータ構造に変換する必要のない大きなLinkedListをソートする効率的な方法はありません（つまり、より良い方法はありません）。O(N)以前にソートされたLinkedListの正しい位置に要素を挿入する効率的な方法（つまり、より良い方法）はありません。3番目の部分（配列へのコピー）は、LinkedListまたはTreeSetでも同様に機能します。O(N)どちらの場合も操作です。

[コレクションは十分に大きいので、Oの複雑さが実際のパフォーマンスを正確に予測できると思います...]

于 2010-09-23T00:40:54.527 に答える
2

TreeSetの真の力と利点は、それが実現するインターフェースにあります-NavigableSet

なぜそれがとても強力なのですか、そしてその場合は？

Navigable Setインターフェイスは、たとえば次の3つの優れたメソッドを追加します。

    headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive)
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

これらの方法により、効果的な検索アルゴリズムを整理できます（非常に高速）。

例：Millaで始まり、Wladimirで終わるすべての名前を見つける必要があります。

    TreeSet<String> authors = new TreeSet<String>();
    authors.add("Andreas Gryphius");
    authors.add("Fjodor Michailowitsch Dostojewski");
    authors.add("Alexander Puschkin");
    authors.add("Ruslana Lyzhichko");
    authors.add("Wladimir Klitschko");
    authors.add("Andrij Schewtschenko");
    authors.add("Wayne Gretzky");
    authors.add("Johann Jakob Christoffel");
    authors.add("Milla Jovovich");
    authors.add("Taras Schewtschenko");
    System.out.println(authors.subSet("Milla", "Wladimir"));

出力：

    [Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky]

TreeSetはすべての要素を調べるのではなく、最初と最後の要素を見つけて、範囲内のすべての要素を含む新しいコレクションを返します。

于 2012-08-30T15:26:45.653 に答える
1

ツリーセット:

TreeSet基になる赤黒ツリーを使用します。したがって、セットは と考えることができますdynamic search tree。頻繁に読み取り/書き込みを行い、順序を維持する必要がある構造が必要な場合は、TreeSet が適しています。

于 2010-09-23T01:35:57.110 に答える
0

並べ替えを維持したい場合、ほとんどが追加である場合は、Comparator を使用した TreeSet が最善の策です。JVM は、項目を配置する場所を決定するために、最初から LinkedList をトラバースする必要があります。LinkedList = O(n) 操作の場合、TreeSet = O(log(n)) 基本的な操作の場合。

于 2010-09-23T00:22:14.180 に答える