Алгоритм объединения больших файлов

Question

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

Эти файлы могут быть относительно большими, например, 500000 событий или более в одном журнале, поэтому чтение всего содержимого журналов в простое событие [] невозможно.

Я пытаюсь объединить события из каждого из журналов в один журнал. Это похоже на задачу слияния, но каждый журнал уже отсортирован, мне просто нужно собрать их вместе. Второй компонент заключается в том, что одно и то же событие может быть засвидетельствовано в каждом из отдельных файлов журнала, и я хочу «удалить повторяющиеся события» в файле вывода файла.

Можно ли это сделать "на месте", например, последовательно работая над некоторыми небольшими буферами каждого файла журнала? Я не могу просто прочитать все файлы в Event [], отсортировать список, а затем удалить дубликаты, но пока мои ограниченные возможности программирования позволяют мне видеть это как решение. Есть ли какой-нибудь более изощренный подход, который я могу использовать для этого, когда я читаю события из каждого из журналов одновременно?

Answer 1

1. Считать первую строку из каждого файла журнала

2. LOOP

   а. Найдите самую раннюю строку.

   б. Вставьте «самую раннюю» строку в основной файл журнала

   с. Прочитайте следующую строку из файла, который содержал самую раннюю строку

Вы можете проверить наличие дубликатов между b и c, перемещая указатель для каждого из этих файлов.

Answer 2

Конечно - открыть каждый файл журнала. Читайте в первой строке для каждого в массив «текущих» строк. Затем несколько раз выберите строку с самой низкой отметкой времени из текущего массива. Запишите его в вывод и прочитайте новую строку из соответствующего исходного файла, чтобы заменить его.

Вот пример на Python, но он также создает хороший псевдокод:

def merge_files(files, key_func):
    # Populate the current array with the first line from each file
    current = [file.readline() for file in files]
    while len(current) > 0:
        # Find and return the row with the lowest key according to key_func
        min_idx = min(range(len(files)), key=lambda x: return key_func(current[x]))
        yield current[min_idx]
        new_line = files[min_idx].readline()
        if not new_line:
            # EOF, remove this file from consideration
            del current[min_idx]
            del files[min_idx]
        else:
            current[min_idx] = new_line

Answer 3

Нам нужно было объединить несколько файлов журналов в хронологическом порядке по нескольким строкам на одну запись журнала (Java-приложения делают это часто - их трассировки стека одинаковы) Я решил реализовать простой скрипт shell + perl. Это покрывает наши задачи. Если вам это интересно - перейдите по ссылке http://code.google.com/p/logmerge/

Answer 4

Оформить заказ по ссылке: http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• Использовать кучу (на основе массива). Количество элементов в этой куче / массиве будет равно количеству имеющихся у вас файлов журналов.

• Считайте первые записи из всех файлов и вставьте их в свою кучу.

• Цикл до (больше нет записей ни в одном из файлов)

      > remove the max element from the heap
      > write it to the output
      > read the next record from the file to which the (previous) max element belonged
          if there are no more records in that file
              remove it from file list
              continue
      > if it's not the same as the (previous) max element, add it to the heap

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

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

Answer 5

ИЛИ вы можете позаимствовать утилиту слияния журналов у Awstats, которая является инструментом статистики сайта с открытым исходным кодом.

logresolvemerge.pl - это скрипт perl, который может объединять несколько файлов журналов: вы можете даже использовать несколько потоков для объединения файлов журналов (необходимо использовать perl 5.8 для многопоточного использования). Почему бы вам не попробовать использовать готовый инструмент вместо его создания?

Answer 6

Чтение только одной строки за раз из обоих исходных файлов. Сравните строки и запишите более старую в выходной файл (и перейдите к следующей строке). Делайте это, пока не дойдете до конца обоих файлов и не объедините файлы.

И обязательно удалите дубликаты:)

Полагаю, этот код в C # может иллюстрировать подход:

        StringReader fileStream1;
        StringReader fileStream2;
        Event eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
        Event eventCursorFile2 = Event.Parse(fileStream2.ReadLine());

        while !(fileStream1.EOF && fileStream2.EOF)
        {
            if (eventCursorFile1.TimeStamp < eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
            }
            else if (eventCursorFile1.TimeStamp == eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }
            else
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }  
        }

Условие разрыва не совсем правильное, так как это просто Quick'n'dirty, но должно выглядеть примерно так ...