Algoritmo para mesclar arquivos grandes
https://stackoverflow.com/questions/128043
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho vários arquivos de log de eventos (um evento por linha). Os logs podem se sobrepor. Os logs são gerados em máquinas clientes separadas de possivelmente vários fusos horários (mas presumo que conheço o fuso horário). Cada evento possui um registro de data e hora que foi normalizada em um tempo comum (instantando a instância do calendário de cada Parsers de log com o fuso horário apropriado ao arquivo de log e usando gettimeInmillis para obter o tempo da UTC). Os logs já são classificados pelo Timestamp. Vários eventos podem ocorrer ao mesmo tempo, mas não são de maneira alguma eventos iguais.
Esses arquivos podem ser relativamente grandes, como em 500000 eventos ou mais em um único log; portanto, ler todo o conteúdo dos logs em um evento simples [] não é viável.
O que estou tentando fazer é mesclar os eventos de cada um dos logs em um único log. É como uma tarefa de mesclagem, mas cada log já está classificado, eu só preciso reuni -los. O segundo componente é que o mesmo evento pode ser testemunhado em cada um dos arquivos de log separados e quero "remover eventos duplicados" no log de saída de arquivos.
Isso pode ser feito "no lugar", como em, trabalhando sequencialmente em alguns pequenos buffers de cada arquivo de log? Não posso simplesmente ler todos os arquivos em um evento [], classificar a lista e remover duplicatas, mas até agora meus recursos de programação limitados apenas me permitem ver isso como a solução. Existe alguma abordagem mais sofisticada que eu possa usar para fazer isso enquanto leio eventos de cada um dos logs simultaneamente?
Solução
Leia a primeira linha de cada um dos arquivos de log
CICLO
uma. Encontre a linha "mais antiga".
b. Insira a linha "mais antiga" no arquivo de log Master
c. Leia a próxima linha do arquivo que continha a linha mais antiga
Você pode verificar duplicatas entre B e C, avançando o ponteiro para cada um desses arquivos.
Outras dicas
Claro - abra todos os arquivos de log. Leia na primeira linha para cada uma de uma matriz de linhas 'atuais'. Em seguida, escolha repetidamente a linha com o timestamp mais baixo da matriz atual. Escreva na saída e leia uma nova linha do arquivo de origem apropriado para substituí -lo.
Aqui está um exemplo no Python, mas também faz um bom pseudocódigo:
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
Confira este link: http://www.codeodor.com/index.cfm/2007/5/10/sorting-relly-big-files/1194
Use uma pilha (com base em uma matriz). O número de elementos nesse heap/matriz será igual ao número de arquivos de log que você possui.
Leia os primeiros registros de todos os arquivos e insira -os em sua pilha.
Faça um loop até (não há mais registros em nenhum dos arquivos)
> 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
Agora você tem todos os seus eventos em um arquivo de log, eles são classificados e não há duplicatas. A complexidade do tempo do algoritmo é (n log k), onde n é o número total de registros e k é o número de arquivos de log.
Você deve usar o leitor em buffer e os objetos de escritor em buffer ao ler de e para os arquivos para minimizar o número de leituras e gravações em disco, a fim de otimizar o tempo.
Fomos necessários para mesclar cronologicamente vários arquivos de log com várias linhas de acordo com uma entrada de log (os aplicativos Java fazem isso com frequência - seus traços de pilha são os mesmos). Decidi implementar o script shell+perl simples. Ele cobre nossas tarefas. Se você estiver interessado nele - siga pelo link http://code.google.com/p/logmerge/
Leia apenas uma linha de cada vez a partir de ambos os arquivos de origem. Compare as linhas e escreva a mais antiga com o arquivo de saída (e adiante para a próxima linha). Faça isso até chegar ao final dos dois arquivos e você mesclou os arquivos.
E certifique -se de remover duplicatas :)
Eu acho que este código em C# pode ilustrar a abordagem:
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());
}
}
A condição de quebra não está exatamente certa, pois isso é apenas rápido, mas deve parecer parecido ..
Ou você pode emprestar um utilitário de mesclagem de log da AWSTATS, que é uma ferramenta de estatísticas de site de código aberto.
LogresolVemerge.pl é um script PERL que pode mesclar vários arquivos de log: você pode até usar vários threads para mesclar os arquivos de log (precisam ter o Perl 5.8 para uso com vários thread). Por que você não tenta usar uma ferramenta prontamente disponível em vez de construir uma?
