0

だから私は Set にたくさんのレコードを含むプログラムを持っています。セットには数個のアイテムが含まれる場合もあれば、数十万個のアイテムが含まれる場合もあります。各レコードが持つ 1 ビットのデータはタイムスタンプです。セット内のすべてのアイテムを削除する必要がありますが、互いに 15 秒以内にあるアイテムは 1 つだけです。それを行う最も効率的な方法は何ですか?

現在、セットの複製を作成しています。次に、最初のアイテムを他のすべてのアイテムと比較してセットを反復処理し、繰り返します。15 秒以内の一致が見つかった場合は、重複セットから削除します。次に、複製セットがファイルに書き出されます。

明らかにこれは機能しますが、これは途方もなく非効率的であることに最終的に気付きました。大きなセットの場合、他の問題が発生していないと仮定すると、これには非常に長い時間がかかるようです。Javaでこれを行うための、より賢く、より速く、より効率的な(または適切な)方法を誰かが提供してくれますか? レコードにはタイムスタンプが含まれているため、それらを並べ替えるとおそらく非常に役立つことに気づきました。ただし、これをすべてプログラム内に収めておきたいので、ソートとコンパレータを調べる必要があると思います。

問題に頭を悩ませることはできません。私は自分のコードを改善するためにいくつかの他の考えを思いつきましたが、私はまだ完全に間違っていると感じずにはいられません。提案をありがとう。

ああ、これは仕事のためであり、学校などではありません。

4

4 に答える 4

5

現在、説明したアルゴリズムはO(n 2 )時間で実行されます。

より高速なアルゴリズムが必要な場合、できることは次のとおりです。

  • コレクションを並べ替えます (Java に基本クラスの並べ替え機能がなかったら驚くでしょう) O(n * lg(n))
  • 互いに15秒以内のすべての「一致」は、互いに隣り合っています
  • 隣接する要素O(n)のみをチェックして、各要素を1回繰り返すだけで済みます

それを行うと、アルゴリズムよりもはるかに管理しやすいO(n * lg(n))時間の複雑さになる可能性があります

Java の Array.sort() に関する情報を次に示します。

于 2013-01-11T19:30:40.800 に答える
1

Set を引き続き使用できます。TreeSet (または複数のスレッドがある場合はConcurrentSkipListSet ) のように、最初から並べ替えられていることを確認してください。タイムスタンプが比較されるように Comparable を実装するか、同じことを行う Comparator を提供します。

これにより、(今までのように) 重複を避けることが保証され、コードも簡素化されます。TreeSet に挿入すると、O(n log n) 時間もかかります。

ここからは、Sam I am によって提案されたアプローチを続けることができます。イテレータは要素の昇順でトラバースします。各要素を前の要素と次の要素のみと比較する必要があります。

ところで、すべてを別のセットにコピーする必要はありません。ツリーセットの削除ではなく、イテレータの削除メソッドを必ず使用してください。コレクションを反復処理し、ループで削除するときに ConcurrentModificationException を回避します。

于 2013-01-11T20:43:10.563 に答える
0

地図をお持ちの場合は、次のように言います。

Map<Long, List<MyClass>> map;

ここで、キーはタイムスタンプであり、次のように実行できます。

// Value of wanted elements
List<MyClass> ret = new ArrayList<MyClass>();

// Go over all timestamps: if a timestamp is wanted, add all
// corresponding elements
for (Map.Entry<Long, List<MyClass>> entry: map.entrySet())
    if (wanted(entry.getKey()))
        ret.addAll(entry.getValue());

// Return
return ret;
于 2013-01-11T20:28:42.820 に答える
0

パフォーマンスについてはテストしていませんが、これを実装する方法の 1 つは、Set を作成し、問題のオブジェクト タイプの equals() メソッドをオーバーライドすることです。

public boolean equals( Object o )
{
  return( Math.abs( this.getTimestampSeconds() - o.getTimestampSeconds() ) < 15 );
}

これにより、各行をセットに追加すると、任意の 15 秒のタイム スライスに対して 1 つのエントリだけになります。

* 編集 **

通常のドメイン オブジェクトに対しては、このオーバーライドは実行しません。おそらく、この目的のためにのみ作成された、ある種のファサードオブジェクトでのみこれを行うでしょう。

また、他の方がおっしゃる通りです。これは、入力リストがタイムスタンプの昇順でソートされていることを前提としています。

于 2013-01-11T22:07:28.567 に答える