Алгоритм объединения больших файлов
https://stackoverflow.com/questions/128043
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть несколько файлов журнала событий (по одному событию на строку).Журналы, возможно, могут перекрываться.Журналы генерируются на отдельных клиентских компьютерах, возможно, из нескольких часовых поясов (но я предполагаю, что знаю часовой пояс).Каждое событие имеет временную метку, которая была нормализована в общее время (путем создания экземпляра каждого экземпляра календаря анализаторов журналов с часовым поясом, соответствующим файлу журнала, а затем с помощью getTimeInMillis для получения времени UTC).Журналы уже отсортированы по метке времени.Несколько событий могут происходить одновременно, но они ни в коем случае не являются равными событиями.
Эти файлы могут быть относительно большими, например, 500000 событий или более в одном журнале, поэтому считывание всего содержимого журналов в простое событие [] невозможно.
То, что я пытаюсь сделать, это объединить события из каждого журнала в один журнал.Это что-то вроде задачи сортировки слиянием, но каждый журнал уже отсортирован, мне просто нужно объединить их.Второй компонент заключается в том, что одно и то же событие может быть засвидетельствовано в каждом из отдельных файлов журнала, и я хочу "удалить повторяющиеся события" в выходном журнале файла.
Можно ли это сделать "на месте", например, последовательно обрабатывая несколько небольших буферов каждого файла журнала?Я не могу просто прочитать все файлы в Event [], отсортировать список, а затем удалить дубликаты, но пока мои ограниченные возможности программирования позволяют мне рассматривать это только как решение.Есть ли какой-нибудь более сложный подход, который я могу использовать для этого, когда я одновременно считываю события из каждого журнала?
Решение
Прочитайте первую строку из каждого файла журнала
ПЕТЛЯ
a.Найдите "самую раннюю" строку.
b.Вставьте "самую раннюю" строку в файл основного журнала
c.Прочитайте следующую строку из файла, который содержал самую раннюю строку
Вы могли бы проверить наличие дубликатов между 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 - количество файлов журнала.
Вам следует использовать объекты buffered reader и buffered writer при чтении в файлы и из файлов, чтобы свести к минимуму количество операций чтения и записи с диска и оптимизировать время.
Нам было необходимо объединить в хронологическом порядке несколько файлов журнала, имеющих несколько строк на одну запись журнала (java-приложения часто делают это - их трассировки стека одинаковы).Я решил реализовать простой скрипт shell + perl.Это охватывает наши задачи.Если вас это заинтересовало - переходите по ссылке http://code.google.com/p/logmerge/
Считывайте только по одной строке за раз из обоих исходных файлов.Сравните строки и запишите более старую в выходной файл (и переходите к следующей строке).Делайте это до тех пор, пока не дойдете до конца обоих файлов и не объедините их.
И обязательно удалите дубликаты :)
Я предполагаю, что этот код на 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, но оно должно выглядеть похоже..
ИЛИ вы могли бы позаимствовать утилиту слияния журналов у Awstats, которая является инструментом статистики веб-сайта с открытым исходным кодом.
logresolvemerge.pl это perl-скрипт, который может объединять несколько файлов журналов :вы даже можете использовать несколько потоков для объединения файлов журналов (для многопоточного использования необходим perl 5.8).Почему бы вам не попробовать использовать легкодоступный инструмент вместо того, чтобы создавать его?
