4

ソートされたセットに配置したいタイムスタンプ付きの値のセットがあります。

public class TimedValue {
    public Date time;
    public double value;

    public TimedValue(Date time, double value) {
        this.time = time;
        this.value = value;
    }
}

このセットをソートするためのビジネスロジックでは、最新の値より7日以上古い場合を除き、値は値の降順で並べ替える必要があります。

そこで、テストとして、次のコードを思いつきました...

DateFormat dateFormatter = new SimpleDateFormat("MM/dd/yyyy");
TreeSet<TimedValue> mySet = new TreeSet<TimedValue>(new DateAwareComparator());
mySet.add(new TimedValue(dateFormatter.parse("01/01/2009"), 4.0 )); // too old
mySet.add(new TimedValue(dateFormatter.parse("01/03/2009"), 3.0)); // Most relevant
mySet.add(new TimedValue(dateFormatter.parse("01/09/2009"), 2.0));

ご覧のとおり、最初は最初の値の方が2番目の値よりも関連性がありますが、最終的な値がセットに追加されると、最初の値の有効期限が切れ、関連性が最も低くなります。

私の最初のテストでは、これは機能するはずだと言っています...さらに値が追加されると、TreeSetはリスト全体を動的に並べ替えます。

でも、見ても信じられない。

並べ替えられたコレクションは、各要素が追加されるときにセット全体を並べ替えますか？ソートされたコレクションをこの方法（つまりパフォーマンス）で使用するための落とし穴はありますか？すべての値が追加された後、リストを手動で並べ替えた方がよいでしょうか（おそらくそうなると思います）。



フォローアップ： 多くの（そしてある程度は私でさえ）疑われるように、ソートされたコレクションはこの方法の「動的な並べ替え」をサポートしていません。私の最初のテストは、まったく偶然に「機能」していたと思います。セットに要素を追加すると、「順序」が急速に崩壊しました。すべての素晴らしい回答に感謝し、多くの人から提案されたアプローチを使用するようにコードをリファクタリングしました。

4

8 に答える 8

10

現在見られている最新の値を記憶していない限り、コンパレータがどのように変化を検出できるかはわかりません。これは、涙で終わるアプローチのように聞こえます。

私はあなたが次の線に沿って何かをすることを提案します：

  • 順序付けられていないセット（またはリスト）にデータを収集する
  • 最新の値を見つける
  • その値に基づいてコンパレータを作成し、そのコンパレータを使用するすべての比較が固定されるようにします（つまり、同じ入力値に基づいて異なる結果が返されることはありません。コンパレータ自体は、コンストラクタで最初に提供された値に依存しますが、不変です。 ）。
  • そのコンパレータを使用して、ソートされたコレクションを作成します（次に何をしたいかに応じて、どのような方法でも最適と思われます）
于 2009-05-26T20:13:57.963 に答える
4

私はいくつかの理由でこれに反対することをお勧めします：

  1. 基本的には舞台裏の赤黒木であるため（挿入のたびに最初から再構築する必要はありません）、ツリーの間違った部分に値が含まれる可能性があります（TreeSet APIのほとんどが無効になります）。 。
  2. 動作は仕様で定義されていないため、現在機能している場合でも後で変更される可能性があります。
  3. 将来、このコードにリモートで触れる何かで何かが奇妙にうまくいかないとき、あなたはこれが原因であると疑うことに時間を費やすでしょう。

検索する前にTreeSetを再作成/並べ替えるか、（私の好みで）検索する前にセットを繰り返し処理して、古すぎるオブジェクトを削除することをお勧めします。メモリを速度と交換したい場合は、2番目のリストを日付順に並べて同じオブジェクトでバックアップすることもできます。これにより、TreeSetをフィルタリングするために必要なのは、時間に基づいてTreeSetからオブジェクトを削除することだけです。 -ソートされたリスト。

于 2009-05-26T20:23:43.310 に答える
3

JDKライブラリやサードパーティのライブラリでさえ、結果に一貫性がないコンパレータを処理するように作成されているとは思いません。私はこの作業に依存しません。コンパレータが一度呼び出されたときに2つの値に対して等しくない値を返し、後で呼び出された場合に同じ2つの値に対して等しい値を返すことができるかどうかはもっと心配です。

の契約書を注意深く読んでくださいComparator.compare()。コンパレータはこれらの制約を満たしていますか？

詳述すると、コンパレータが一度呼び出したときに2つの値が等しくないことを返したが、後で値がセットに追加され、コンパレータの出力が変更されたために2つの値が等しいことを後で返す場合、 「設定」（重複なし）は元に戻されます。

彼の答えにおけるジョン・スキートのアドバイスは優れたアドバイスであり、この種の問題について心配する必要はありません。確かに、コンパレータがと一致する値を返さない場合は、equals()大きな問題が発生する可能性があります。ソートされたセットが何かを追加するたびに再ソートされるかどうかは関係ありませんが、順序の変更によって発生する最悪の事態は、セットがソートされたままにならないことです。

于 2009-05-26T20:08:01.157 に答える
2

私はこれがうまくいかないと99％確信しています。セット内の値がその比較動作を突然変更した場合、その値が検出されなくなる可能性があります（実際にはかなり可能性が高いです）。つまり、検索アルゴリズムはある時点で比較を実行し、値が挿入されたときとは異なる結果を返すため、間違ったサブツリーで続行するため、を返しますset.contains(value)。false

于 2009-05-26T20:13:38.307 に答える
2

いいえ、これは機能しません。

コレクションで同等のキーを使用している場合、2つのキー間の比較結果は時間の経過とともに同じである必要があります。

キーをバイナリツリーに格納する場合、パス内の各フォークは、比較操作の結果として選択されます。後で比較して別の結果が返された場合、別のフォークが取得され、以前に保存されたキーは見つかりません。

于 2009-05-26T20:15:15.947 に答える
1

レコードがソートの途中で<7日から>7日に変更される可能性があるため、実行していることはコンパレータのルールに違反します。もちろん、これは機能しないという意味ではありません。内部で何が起こっているかを正確に知っていれば、「予測不可能」と文書化されている多くのことが実際に機能します。

教科書の答えは次のとおりだと思います。これは組み込みの種類では信頼できません。独自のソート関数を作成する必要があります。

少なくとも、日付が境界を越えたときに、TreeSetや「ソートされた構造」に魔法のように頼ることはできません。せいぜい、これは、表示する直前に再ソートし、更新の間に正しいままであることに依存しない場合に機能する可能性があります。

最悪の場合、一貫性のない比較は、ソートをひどく壊す可能性があります。これにより、無限ループやその他の致命的なブラックホールに陥らないという保証はありません。

つまり、使用する予定のクラスや関数についてSunのソースコードを読み、何が起こるかを理解できるかどうかを確認してください。テストは良いですが、テストが難しい潜在的にトリッキーなケースがあります。最も明白なのは、次のとおりです。並べ替えの処理中に、レコードが日付の境界を超えた場合はどうなりますか？つまり、レコードを1回見て、<7であると言うかもしれませんが、次にそれを見るときは>7です。それは悪い、悪いニュースかもしれません。

私が思いついた明らかなトリックの1つは、動的にではなく、レコードを構造に追加したときの日付を年齢に変換することです。そうすれば、ソート内で変更することはできません。構造物が数分以上存続する場合は、適切な時期に年齢を再計算してから、並べ替えます。実際には7日、0時間、0分、2秒であるのに、レコードは7日未満であると言ったので、誰かがあなたのプログラムが間違っていると言うのではないかと思います。誰かが気づいたとしても、彼らの時計はどれくらい正確ですか？

于 2009-05-26T20:27:53.317 に答える
1

コンパレータの不変の性質は、ソートごとにあると想定されていると思います。特定のソート操作の期間中一貫している限り、問題はありません（どのアイテムも7日間の境界ミッドソート）。

ただし、TreeSetについて具体的に質問していることをより明確にしたいと思うかもしれません。これは、新しいアイテムを追加するときに時間を節約するために以前の種類の情報を再利用すると思います。これは少し特殊なケースです。TreeSet javadocsは、特にComparatorセマンティクスに準拠しているため、おそらく公式にはサポートされていませんが、安全かどうかを判断するには、コードを読む必要があります。

データを並べ替える必要がある場合は、「今」として1回だけ使用して完全な並べ替えを行う方がよいと思います。そうすることで、並べ替えに時間がかかる場合に境界をジャンプするリスクを回避できます。

于 2009-05-26T20:13:41.083 に答える
1

すでに述べたように、推移性が侵害されているため、コンパレータはこれを行うことができません。基本的に、アイテムを並べ替えることができるようにするには、（残りの部分とは関係なく）2つそれぞれを比較できる必要がありますが、これは明らかにできません。したがって、シナリオは基本的に機能しないか、一貫性のない結果を生成します。

たぶん、もっと簡単なもので十分でしょう。

  • 必要に応じて値を使用する単純なコンパレータを適用します
  • リスト/コレクションから、最新のものより7日古いすべての要素を削除するだけです。基本的に、新しいアイテムが追加されるたびに、それが最新であるかどうかを確認し、最新である場合は、これより7日古いアイテムを削除します。

リストからアイテムも削除した場合、これは機能しません。その場合、削除したすべてのアイテムを別のリストに保持し（ちなみに、日付で並べ替えます）、元のリストに追加し直す必要があります。削除後のMAX（日付）が小さい場合。

于 2009-05-26T20:59:06.577 に答える