8

TreeSetには、要素がセットに含まれている場合にtrueを返すcontainsというメソッドがあります。この方法は二分探索を使用し、すべての要素を昇順で反復するわけではないと思います。私は正しいですか？

同じクラスの他のオブジェクトと区別するために2つのStringインスタンス変数を使用するクラスのオブジェクトを含むTreeSetがあります。オブジェクトの2つのインスタンス変数（もちろんgetメソッドを使用）を他の2つのString変数と比較し、それらが等しい場合は要素を返すことで、TreeSetを検索するメソッドを作成できるようにしたいと思います。インスタンス変数が右側のサブツリーの最初の要素に移動するよりも少ない場合、または左側のサブツリーなどでより多くの検索が行われる場合。これを行う方法はありますか？

オブジェクトをArrayListに格納し、バイナリ検索を使用してオブジェクトを見つけることができることはわかっていますが、これはTreeSetを検索するほど速くはありません。

4

5 に答える 5

15 
set.tailSet(obj).first();

あなたが望むことをします。

于 2011-08-30T14:34:08.433 に答える
6

を使用する代わりに、オブジェクトをまたはTreeSetに格納できます（検索するたびに新しい実際を簡単に作成できない場合）。sは実際にはルックアップを目的としたものではありません。TreeMap<Foo, Foo>TreeMap<FooKey, Foo>FooSet

たとえば、FooKeyは、2つのsをFooKey含み、である単純な不変クラスになります。2つのsの値を見つけることは、単純な問題です。もちろん、これは値を見つけたいツリートラバーサルを使用します。StringComparableFooStringtreeMap.get(new FooKey(firstString, secondString))

于 2011-04-05T22:00:03.040 に答える
2

オブジェクトにComparableを実装するか、TreeSetの構築時に渡す別のComparatorクラスを作成する必要があります。これにより、カスタムエントリ比較ロジックを挿入し、TreeSetに最適化されたストア/検索を実行させることができます。

于 2011-04-05T21:27:12.130 に答える
1

私が疑問に思っていたのは、なぜソートされたセットを検索したいのかということです。順番に繰り返し処理したり、すばやく検索したりできるようにしたい場合は、オブジェクトを2つの別々のデータ構造に格納することでメリットが得られる場合があります。あなたのようなものであり、 ColinDが述べたものにSortedSet<Foo>も似ています。HashMap<FooKey,Foo>次に、TreeMapでlog（n）の代わりに一定時間のルックアップを取得します。両方の構造に書き込む必要があるという書き込みペナルティと、2つのデータ構造を持つことによるメモリリソースペナルティがありますが、データへのアクセスは完全に最適化されています。

また、メモリリソースに制約があり、文字列が実際にオブジェクトを区別するものである場合は、オブジェクトに実装hashcode()しequals()てから、Fooそれらをキーと値の両方として使用できます（HashMap<Foo,Foo>たとえば、Fooゲッターを呼び出します。

于 2011-04-06T01:48:33.957 に答える
0

あなたはcomparable/コンパレータの使用についての答えを得ました、しかし私はあなたがそれらの詳細を知る必要はないはずですが、contains（）が二分探索をするのはあなたが正しいと付け加えたいと思いました

于 2011-04-05T21:28:40.243 に答える