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

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

2. ПЕТЛЯ

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

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

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

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

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

Вот пример на 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

Перейдите по этой ссылке: 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 — количество файлов журнала.

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

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

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

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

Я предполагаю, что этот код на С# может иллюстрировать подход:

        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, но оно должно выглядеть похоже.

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

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