объединить без потери наиболее точного порядка

Question

У меня есть три файла журнала со вторым разрешением.

В каждом файле отсутствуют некоторые записи журнала.

Как объединить, не испортив наиболее точный порядок?

---

Пример 1

Logfile1

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

Logfile1

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

Хорошо, в этом примере 0d идет после 3a дважды, что является более вероятным порядком.Сортировка с топологической сортировкой даст 3a, 2b, 1c, 0d.

Я думаю, что правильный порядок - это 3a, 0d, 2b, 1c.

Я не знаю, как это сделать в данный момент.

Answer 1

Похоже, вы хотите использовать гибрид слияния и топологической сортировки.

Answer 2

В худшем случае все времена одинаковы, и у вас есть такие проблемы:

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

Вы не можете определить, была ли фактическая последовательность aba илибабы.В этом случае было бы неправильно сообщать только ab или просто ba.

Топологическая сортировка будет работать, только если события уникальны.В вашей программе запускаются файлы, занимающие куски, которые находятся на одном и том же времени.Если вы знаете, что события уникальны, используйте топологическую сортировку этих кусков.Или, более интуитивно, вы можете просто объединить три цепочки в этом чанке, каждый раз беря элемент, который также не находится ниже текущего верхнего элемента любой из других цепочек - что на самом деле то же самое, выраженное по-другому.

Если события для конкретной временной метки не являются уникальными, правильное общее решение состоит в том, чтобы использовать трехстороннюю разницу для этой временной метки.Вероятно, излишний путь для того, что вы хотите, но единственно верное решение.

Answer 3

Я думаю, что топологическая сортировка + ответ сортировки слияния верна. Вот мое мнение об этом:

Держать указатель на текущую позицию в каждом файле журнала.

Найти следующую метку времени (для всех файлы). Учитывайте только те события, которые иметь эту отметку времени. (Не все файлы журнала обязательно будут события.)

Все события с тем же временем Вершины штампов в вашем графике. Каждый файл журнала (строки с этим то же время) дает вам преимущества ваш график (есть только один график, через все три файла журнала). Ты получаешь края, читая один файл журнала, все строки с одинаковой отметкой времени, и для каждой строки и следующей строки добавьте ребро.

сделать топологическую сортировку для того времени печать.

Теперь перейдите к следующей отметке времени.

Итак, в вашем примере вы начнете с отметки времени 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.

Logfile 1 дает вам преимущество 3a-> 2b. Logfile 2 имеет только одно событие, поэтому нет ребер. Logfile 3 дает вам преимущество 2b-> 10z.

Выполнение топологической сортировки дает 3a, 2b, 10z.

(Непонятно, хотите ли вы сделать что-то особенное с 2b и распечатать «это произошло дважды» или что-то в этом роде. Это просто, если вы хотите сохранить количество вхождений в вершине.)

Теперь вы переходите к 12:00:02. И так далее.