Algoritmo para fusionar archivos grandes

Question

Tengo varios archivos de registro de eventos (un evento por línea). Los registros pueden posiblemente superponerse. Los registros se generan en máquinas cliente separadas de posiblemente varias zonas horarias (pero supongo que conozco la zona horaria). Cada evento tiene una marca de tiempo que se normalizó en un tiempo común (al crear una instancia de cada instancia del calendario de analizadores de registro con la zona horaria apropiada para el archivo de registro y luego usar getTimeInMillis para obtener la hora UTC). Los registros ya están ordenados por marca de tiempo. Se pueden producir varios eventos al mismo tiempo, pero no son eventos iguales.

Estos archivos pueden ser relativamente grandes, como en 500000 eventos o más en un solo registro, por lo que no es posible leer todo el contenido de los registros en un Evento simple [].

Lo que estoy tratando de hacer es combinar los eventos de cada uno de los registros en un solo registro. Es un poco como una tarea combinada, pero cada registro ya está ordenado, solo necesito reunirlos. El segundo componente es que se puede presenciar el mismo evento en cada uno de los archivos de registro separados, y quiero " eliminar eventos duplicados " en el registro de salida del archivo.

¿Se puede hacer esto "en su lugar", como en, trabajando de forma secuencial sobre algunos búferes pequeños de cada archivo de registro? No puedo simplemente leer todos los archivos en un Evento [], ordenar la lista y luego eliminar los duplicados, pero hasta ahora mis limitadas capacidades de programación solo me permiten ver esto como la solución. ¿Hay algún enfoque más sofisticado que pueda usar para hacer esto mientras leo eventos de cada uno de los registros al mismo tiempo?

Answer 1

1. Lea la primera línea de cada uno de los archivos de registro

2. LOOP

   a. Encuentra el " primero " línea.

   b. Inserte el " primero " línea en el archivo de registro maestro

   c. Lea la siguiente línea del archivo que contenía la primera línea

Podrías buscar duplicados entre byc, avanzando el puntero para cada uno de esos archivos.

Answer 2

Claro - abre todos los archivos de registro. Lea la primera línea de cada una en una matriz de líneas "actuales". Luego, seleccione repetidamente la línea con la marca de tiempo más baja de la matriz actual. Escríbalo en la salida y lea una nueva línea del archivo fuente apropiado para reemplazarlo.

Aquí hay un ejemplo en Python, pero también es un buen 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

Answer 3

Consulte este enlace: http : //www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• Usa un montón (basado en una matriz). El número de elementos en este montón / matriz será igual al número de archivos de registro que tiene.

• Lea los primeros registros de todos los archivos e insértelos en su montón.

• Bucle hasta (no hay más registros en ninguno de los archivos)

      > 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

Ahora tiene todos sus eventos en un archivo de registro, están ordenados y no hay duplicados. La complejidad del tiempo del algoritmo es (n log k) donde n es el número total de registros y k es el número de archivos de registro.

Debe usar objetos de lectura y escritura en búfer al leer desde y hacia los archivos para minimizar el número de lecturas y escrituras en el disco, a fin de optimizar el tiempo.

Answer 4

Necesitábamos fusionar cronológicamente varios archivos de registro con varias líneas por entrada de registro (las aplicaciones java lo hacen a menudo; sus rastros de pila son iguales). Decidí implementar el script simple shell + perl. Cubre nuestras tareas. Si le interesa, siga el enlace http://code.google.com/p/logmerge /

Answer 5

Lea solo una línea a la vez de ambos archivos de origen. Compare las líneas y escriba la más antigua en el archivo de salida (y avance a la línea siguiente). Haga esto hasta que haya llegado al final de ambos archivos y haya fusionado los archivos.

Y asegúrate de eliminar los duplicados :)

Supongo que este código en C # puede ilustrar el enfoque:

        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 condición de ruptura no es exactamente la correcta, ya que solo es Quick'n'dirty, pero debería ser similar.

Answer 6

O puede tomar prestada una utilidad de combinación de registros de Awstats que es una herramienta de estadísticas de sitios web de código abierto.

logresolvemerge.pl es un Script de Perl que puede combinar varios archivos de registro: incluso puede utilizar varios subprocesos para combinar los archivos de registro (es necesario tener Perl 5.8 para el uso de varios subprocesos). ¿Por qué no intentas usar una herramienta disponible en lugar de crear una?