問題タブ [treeset]

私は最近、いくつかの文字列をJava TreeSetに入れ、距離ベースのコンパレータを実装し、日没に向かって陽気に進んで、特定の問題を解決するために特定のスコアを計算するJavaコードに出くわしました。

私の質問、

• Pythonで利用できる同等のデータ構造はありますか？

  • Javaツリーセットは、基本的に、この順序付けを実現するために何らかのコンパレーターを使用できる順序付けされた辞書のように見えます。

• OrderedDict用のPy3K用のPEPがあるようですが、2.6.xを使用しています。そこにはたくさんの順序付けられたdict実装があります-特に推奨できる人はいますか？

PS、追加するだけです-おそらくDictMixinまたはUserDictをインポートして、独自のソート/順序付けされた辞書を実装し、コンパレータ関数を介してそれを実現することができます-しかし、それはやり過ぎのようです。

ありがとう。

アップデート。答えてくれてありがとう。少し詳しく説明すると、（特定の値lnが与えられた場合）のように定義された比較関数があるとします。

これを、ここに示されている順序付けされたdictリンクに示されている順序付けにどのように統合するかについては少しわかりません。

何かのようなもの、

アイデアは大歓迎です。

私のコードでは、Java TreeSetの反復が主要な時間要素です。システムを見ると、O(n) の複雑さだと思います。誰でもこれを確認できますか？

子ノードから親ノードへの逆方向のリンクを提供することで、パフォーマンスを向上させることができると考えています。

私はSortedSetをこのように定義しています：

そして私はRatedMessage[]の配列を持っています

セットにシリアル化機能がないため、配列を使用する必要がありました。次に、配列を再構築する必要があります。

配列からセットにすべてのアイテムを再度追加する簡単な方法はありますか？

TreeSet のいくつかの操作の複雑さに関するいくつかのことを解決しようとしています。javadoc には次のように書かれています。

「この実装は、基本的な操作 (追加、削除、および含む) の保証された log(n) 時間コストを提供します。」

ここまでは順調ですね。私の質問は、addAll()、removeAll() などで何が起こるかです。ここで Set の javadoc は次のように述べています。

「指定されたコレクションもセットである場合、addAll 操作はこのセットを効果的に変更し、その値が 2 つのセットの結合になるようにします。」

操作の論理的な結果を説明しているだけですか、それとも複雑さについてのヒントを提供していますか? つまり、2 つのセットがたとえば赤黒の木で表されている場合、一方の要素を他方の要素に「追加」するよりも、どうにかして木を結合する方がよいでしょう。

いずれにせよ、2 つの TreeSet を O(logn) の複雑さで 1 つに結合する方法はありますか?

前もって感謝します。:-)

だから私はしばらくの間問題に苦しんでいて、ここで助けを求めたほうがいいと思いました。

TreeSetにTicketオブジェクトを追加しています。TicketはComparableを実装し、equals（）、hashCode（）、およびCompareTo（）メソッドをオーバーライドしています。contains（）を使用して、オブジェクトがすでにTreeSetにあるかどうかを確認する必要があります。セットに2つの要素を追加すると、すべて正常にチェックアウトされますが、3つ目の要素を追加すると、混乱します。

TreeSetに3番目の要素を追加した後、この小さなコードを実行すると、Ticket temp2がチェックしているオブジェクト（verkoopLijst）になります。

これを返します：

今私の質問は、これがどのように可能であるかということです。

編集：

なぜこれは投げるのClassCastExceptionですか？

特定の要素がTreeSet のどのレベルにあるかをすばやく検出する方法を知っている人はいますか? レベルとは、ツリー内のこの要素の深さ、つまりその祖先の数を意味します。

バックグラウンド。 Java の TreeSet クラスを使用して要素を格納します。2 つの要素を比較するには、それらに関する補助情報を計算する必要があります。この補助情報を要素ごとに保存することはできません。これは、メモリが多すぎるためです。一方、比較ごとに補助情報を再生成すると、プログラムが遅すぎます。要素が TreeSet に挿入されると、私の現在の実装では、挿入された要素の補助情報が計算され、要素が TreeSet 内でその場所を見つけるまで再計算されません。その後、補助情報は破棄されます。私のプログラムをスピードアップするために、TreeSet の最上位レベルについても補助情報を保存したいと思います。これらは多くの比較に関与しているためです。したがって、2 つのノードを比較した後、

アップデート。 また、ある種のバランスの取れたツリー (AVL ツリー、赤/黒ツリー、Splay ツリーなど) を実装し、要素の高さにアクセスできる別のクラスを誰かが提案してくれるとありがたいです。

equals特定の基準 (基準 A) に基づいて機能を実装した Java Bean オブジェクトがあります。別の基準 (基準 B) に基づいて一意のオブジェクトを識別する必要があります。equals関数は条件 A を使用するため、使用できませんHashSet。そこで、基準 B に基づくTreeSet私のカスタムで使用することを考えました。私の質問は、このようなことをしてもよいですか? Comparatorこのアプローチに問題はありますか？

ありがとうございました。

Point2D.Float型のTreeSetを作成し、Point2D型のcompare（）を実装するカスタムComparableクラスを使用して作成しています。ただし、TreeSetで「contains」を呼び出すと、クラスキャストエラーが発生します。java.lang.ClassCastException: java.awt.geom.Point2D$Float cannot be cast to java.lang.Comparable

セットは次のように作成されます。

これが私の比較クラスです：

何がうまくいかないかについてのアイデアはありますか？私はそれを無駄にデバッグしようとして何時間もここで立ち往生しています。ありがとう。

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

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

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