1

この並べ替えの状況に適した（単純な）アルゴリズム/方法は次のとおりです。

各アイテムが2つのフィールドで構成されるアイテムの配列があります:(ID、タイムスタンプ)

同じ ID を持つアイテムのペアが多数あります。

最も古いタイムスタンプを持つアイテムから始めて、アイテムがID間で可能な限り交互になるように配列をソートしたいと思います。

たとえば、次の入力を使用します。

(1, 15:00)
(1, 15:05)
(1, 15:10)
(2, 15:15)
(2, 15:20)
(2, 15:25)
(3, 15:30)
( 4時15分35秒)
(3時15分40秒)

私はこの出力を得るでしょう：

(1, 15:00)
(2, 15:15)
(3, 15:30)
(4, 15:35)
(1, 15:05)
(2, 15:20)
(3, 15:40)
( 1, 15:10)
(2, 15:25)

私は主に概念的に単純なアルゴリズムを探していますが、もちろん、パフォーマンスが優れていれば素晴らしいことです。

今私が考えることができる最高のものは次のようなものです：

  1. 一時配列 T の初期化/作成
  2. 配列 A から: ID が T にない最も古いタイムスタンプを持つ項目 X を取得します。
  3. 結果セット R に X を追加し、T に X.ID を追加し、A から X をポップします。
  4. X が存在する限り、ステップ 2-3 を繰り返します。そうでない場合は、ステップ 1 から再開します。
  5. A が空になったら終了
4

1 に答える 1

2
  1. すべてのアイテムを、最初にIDで、次に時間でソートするソート済みマルチマップに配置します。（たとえば、IDでキー設定されたお気に入りのソートされた連想コンテナーを使用してこれを実装できます。ここで、ソートされたコンテナーの各値は、それ自体がすべての時間値を保持する別のソートされたコンテナーです。
  2. このマルチマップにはまだ要素がありますが、昇順の各キーについて、そのキーを持つ最初の要素を削除し、結果に追加します。

完了したら、問題を正しく理解していれば、希望どおりの結果が得られます。

これは、Guavaを使用したJavaの例ですTreeMultimap（テストされていません）。

TreeMultimap<Id, Timestamp> map = new TreeMultimap<Id, Timestamp>();
for (/* ... every item ... */) {
  map.put(item.getId(), item.getTimestamp());
}

List<Entry> outputList = new ArrayList<Entry>();
while (!map.isEmpty()) {
  for (Id key : map.keySet()) {
    Timestamp value = map.get(key).first();
    outputList.add(new Entry(key, value));
    map.remove(key, value);
  }
}
return outputList;
于 2013-02-13T22:19:45.877 に答える