Algorithme de fusion de gros fichiers

Question

J'ai plusieurs fichiers journaux d'événements (un événement par ligne). Les journaux peuvent éventuellement se chevaucher. Les journaux sont générés sur des machines clientes distinctes de plusieurs fuseaux horaires (mais je suppose que je connais le fuseau horaire). Chaque événement a un horodatage normalisé en une heure commune (en instanciant chaque instance de calendrier d'analyseurs de journal avec le fuseau horaire approprié au fichier journal, puis en utilisant getTimeInMillis pour obtenir l'heure UTC). Les journaux sont déjà triés par horodatage. Plusieurs événements peuvent se produire en même temps, mais ils ne sont en aucun cas des événements égaux.

Ces fichiers peuvent être relativement volumineux, comme dans 500 000 événements ou plus dans un seul journal. Par conséquent, il est impossible de lire tout le contenu des journaux dans un simple événement [].

Ce que je tente de faire est de fusionner les événements de chacun des journaux en un seul journal. C'est un peu comme une tâche mergesort, mais chaque journal est déjà trié, je dois juste les rassembler. La deuxième composante est que le même événement peut être observé dans chacun des fichiers journaux séparés, et je souhaite "supprimer les événements en double". dans le journal de sortie du fichier.

Cela peut-il être fait "en place", comme dans, en travaillant séquentiellement sur de petits tampons de chaque fichier journal? Je ne peux pas simplement lire tous les fichiers dans un événement [], trier la liste, puis supprimer les doublons, mais jusqu'à présent, mes capacités de programmation limitées ne me permettent que de voir cela comme une solution. Existe-t-il une approche plus sophistiquée que je peux utiliser pour ce faire lorsque je lis simultanément les événements de chacun des journaux?

Answer 1

1. Lisez la première ligne de chacun des fichiers journaux

2. LOOP

   a. Recherchez le " plus ancien " ligne.

   b. Insérer le " plus ancien " ligne dans le fichier journal principal

   c. Lire la ligne suivante du fichier contenant la première ligne

Vous pouvez rechercher les doublons entre b et c, en faisant avancer le pointeur de chacun de ces fichiers.

Answer 2

Bien sûr - ouvrez chaque fichier journal. Lisez la première ligne pour chacun dans un tableau de lignes 'actuelles'. Ensuite, sélectionnez à plusieurs reprises la ligne avec l'horodatage le plus bas du tableau actuel. Ecrivez-le dans la sortie et lisez une nouvelle ligne du fichier source approprié pour la remplacer.

Voici un exemple en Python, mais il crée également un bon pseudocode:

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

Consultez ce lien: http : //www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• Utilisez un tas (basé sur un tableau). Le nombre d'éléments dans ce tas / tableau sera égal au nombre de fichiers journaux que vous avez.

• Lisez les premiers enregistrements de tous les fichiers et insérez-les dans votre tas.

• Boucle jusqu'à (aucun enregistrement dans aucun des fichiers)

      > 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

Vous avez maintenant tous vos événements dans un seul fichier journal, ils sont triés et il n’ya pas de doublons. La complexité temporelle de l'algorithme est (n log k), où n représente le nombre total d'enregistrements et k le nombre de fichiers journaux.

Vous devez utiliser des objets lecteur et écrivain en mémoire tampon lors de la lecture vers et depuis des fichiers pour réduire le nombre de lectures et d'écritures sur disque, afin d'optimiser le temps.

Answer 4

Nous devions fusionner chronologiquement plusieurs fichiers journaux comportant plusieurs lignes pour une entrée de journal (les applications Java le font souvent - leurs traces de pile sont les mêmes). J'ai décidé d'implémenter le script simple shell + perl. Cela couvre nos tâches. Si cela vous intéresse, suivez le lien http://code.google.com/p/logmerge. /

Answer 5

Ne lisez qu'une ligne à la fois dans les deux fichiers source. Comparez les lignes et écrivez la plus ancienne dans le fichier de sortie (et passez à la ligne suivante). Faites-le jusqu'à la fin des deux fichiers et la fusion des fichiers.

Et assurez-vous de supprimer les doublons:)

Je suppose que ce code en C # peut illustrer l'approche:

        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());
            }  
        }

La condition de rupture n’est pas tout à fait correcte, il s’agit simplement de Quick'n'dirty, mais elle devrait avoir l’air similaire.

Answer 6

OU vous pouvez emprunter un utilitaire de fusion de journaux à Awstats, un outil de statistiques de site Web à source ouverte.

logresolvemerge.pl est un Script perl pouvant fusionner plusieurs fichiers journaux: vous pouvez même utiliser plusieurs threads pour fusionner les fichiers journaux (vous devez disposer de perl 5.8 pour une utilisation multi-thread). Pourquoi n'essayez-vous pas d'utiliser un outil facilement disponible au lieu d'en construire un?