最も正確な注文を失うことなくマージします

Question

2番目の解像度で3つのログファイルがあります。

すべてのファイルにログエントリがありません。

最も正確な注文を混乱させることなくどのようにマージできますか？

---

例1

1ログ

 
12:00:01 system event 3a 
12:00:01 system event 2b 
12:00:02 system event 0d 

Logfile2

 
12:00:01 system event 2b 
12:00:02 system event 1c 
12:00:02 system event 0d 

Logfile3

 
12:00:01 system event 2b 
12:00:01 system event 10z 
12:00:02 system event 1c 
12:00:02 system event 0d 

3aは、私が考える主な問題であること

2bは

（後しかし、3A）を2回表示され、一度表示されます。

---

更新：

例2

1ログ

 
12:00:01 system event 3a 
12:00:01 system event 2b 
12:00:01 system event 1c 

Logfile2

 
12:00:01 system event 3a 
12:00:01 system event 0d 

Logfile3

 
12:00:01 system event 3a 
12:00:01 system event 0d 

[OK]を、この例の0Dでは、二回3Aの後に来る可能性が高いためです。 トポロジカルソートでソートすると、3a、2b、1c、0dが生成されます。

私は正しい順序が3a、0d、2b、1cだと思います。

私は現時点でそれを行う方法がわかりません。

Answer 1

マージとトポロジカルソートのハイブリッドを使いたいと思うような音がします。

Answer 2

トポロジカルソート+マージソートの回答が正しいと思います。具体的には、次のとおりです。

各ログファイルに現在の位置 のポインタを置いてください。

次のタイムスタンプを見つけます（ ファイルすべて）。 にそのタイムスタンプが付いているイベントのみを考慮してください。 （すべてのログファイルが必ずしもイベントを持つわけではありません。 ）

同じ時刻のすべてのイベント スタンプフォームの頂点がグラフに表示されます。 各ログファイル（同じタイムスタンプの の行）は、 というグラフにエッジを表示します（3つのログファイル全体に1つのグラフしかありません。 ）。 単一のログファイルを読み取ると、同じタイムスタンプを持つすべての行が 、各行と次の行には のエッジが追加され、エッジが追加されます。

その時点のトポロジカルソート スタンプを行います。

今度は次のタイムスタンプに進みます。

したがって、例では、12:00:01のタイムスタンプから開始します。

Logfile1 
12:00:01 system event 3a 
12:00:01 system event 2b 

Logfile2 
12:00:01 system event 2b 

Logfile3 
12:00:01 system event 2b 
12:00:01 system event 10z 

頂点は、3a、2b（複数の出現）、および10zです。

ログファイル1は、エッジ3a - > 2bを提供します。 ログファイル2には1つのイベントしかないため、エッジはありません。 ログファイル3は、エッジ2b-> 10zを示します。

トポロジカルソートを行うと、3a、2b、10zが得られます。

（2bで何か特別なことをしたいのかどうかは分かりませんが、「これは2回発生しました」というようなものを印刷することもできますが、必要に応じて頂点にオカレンス数を格納するのは簡単です。

12:00:02に移動しました。等々。

Answer 3

最悪のケースでは、すべての時間が同じで、あなたはこのような問題を抱えて：あなたは実際の配列は、ABAまたはBABであったかどうかを判断することはできません

Logfile 1 
12:00:00 system event a 
12:00:00 system event b 

と

Logfile 2 
12:00:00 system event b 
12:00:00 system event a 

を。この場合には、ちょうどabかちょうどbaを報告するのは正しいとは言えません。

トポロジカルソートは、イベントが一意の場合にのみ機能します。プログラムでは、ファイルを実行し、同じ時間にチャンクを取得します。イベントが一意であることが分かっている場合は、これらのチャンクにトポロジカルソートを使用します。または、直感的には、このチャンク内の3つのチェーンを、別のチェーンの現在のトップ要素の下にも存在しない要素を取るたびにマージすることができます。

特定のタイムスタンプのイベントが一意でない場合、適切な一般的な解決方法は、そのタイムスタンプに対して3方向差分を使用することです。あなたが望むものはおそらく過度の方法ですが、唯一真の正しい解決策です。