큰 파일 병합 알고리즘

StackOverflow https://stackoverflow.com/questions/128043

  •  02-07-2019
  •  | 
  •  

문제

이벤트의 몇 가지 로그 파일이 있습니다 (한 줄 당 이벤트). 로그가 겹칠 수 있습니다. 로그는 여러 시간 영역에서 별도의 클라이언트 시스템에서 생성됩니다 (그러나 시간대를 알고 있다고 가정합니다). 각 이벤트에는 공통 시간으로 정규화 된 타임 스탬프가 있습니다 (로그 파일에 적합한 타임 존과 함께 각 로그 파서 캘린더 인스턴스를 인스턴스화 한 다음 gettimeinmillis를 사용하여 UTC 시간을 얻습니다). 로그는 이미 타임 스탬프에 의해 정렬되었습니다. 여러 이벤트가 동시에 발생할 수 있지만 결코 동등한 이벤트가 아닙니다.

이 파일은 단일 로그에서 500000 이벤트 이상과 같이 비교적 클 수 있으므로 로그의 전체 내용을 간단한 이벤트 []로 읽는 것은 불가능합니다.

내가 시도하는 것은 각 로그의 이벤트를 단일 로그로 병합하는 것입니다. 그것은 mergesort 작업과 비슷하지만 각 로그는 이미 정렬되어 있습니다. 두 번째 구성 요소는 각 별도 로그 파일에서 동일한 이벤트를 목격 할 수 있으며 파일 출력 로그에서 "중복 이벤트 제거"를 원합니다.

각 로그 파일의 작은 버퍼 위에 순차적으로 작동하는 것처럼 "제자리에"수행 할 수 있습니까? 모든 파일에서 모든 파일을 이벤트 []에 읽고 목록을 정렬 한 다음 복제를 제거 할 수는 없지만 지금까지 제한된 프로그래밍 기능을 사용하면 솔루션으로 만 볼 수 있습니다. 각 로그의 이벤트를 동시에 읽을 때이 작업을 수행하는 데 사용할 수있는 더 정교한 접근법이 있습니까?

도움이 되었습니까?

해결책

  1. 각 로그 파일에서 첫 번째 줄을 읽습니다.

  2. 고리

    ㅏ. "가장 초기"라인을 찾으십시오.

    비. 마스터 로그 파일에 "초기"줄을 삽입하십시오.

    씨. 가장 초기 줄이 포함 된 파일에서 다음 줄을 읽으십시오.

B와 C 사이의 중복을 확인하여 각 파일의 포인터를 발전시킬 수 있습니다.

다른 팁

물론 - 모든 로그 파일을 엽니 다. 각각의 첫 번째 줄에서 '현재'라인 배열로 읽으십시오. 그런 다음 현재 배열에서 가장 낮은 타임 스탬프로 라인을 반복적으로 선택하십시오. 출력에 쓰고 적절한 소스 파일에서 새 줄을 읽어 대체하십시오.

파이썬의 예는 다음과 같습니다. 그러나 좋은 의사 코드도 만듭니다.

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/

두 소스 파일에서 한 번에 한 줄만 읽으십시오. 선을 비교하고 이전 판을 출력 파일에 쓰고 다음 줄로 전진하십시오. 두 파일의 끝에 도달하고 파일을 병합 할 때 까지이 작업을 수행하십시오.

그리고 복제를 제거하십시오 :)

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

휴식 조건은 이것이 단지 빠르기 때문에 정확히 옳지 않지만 비슷해 보일 것입니다 ..

또는 오픈 소스 웹 사이트 통계 도구 인 AWSTATS에서 로그 병합 유틸리티를 빌릴 수 있습니다.

LogresolveMerge.pl 여러 로그 파일을 병합 할 수있는 PERL 스크립트입니다. 여러 스레드를 사용하여 로그 파일을 병합 할 수도 있습니다 (멀티 스레드 사용을 위해서는 Perl 5.8이 필요함). 도구를 구축하는 대신 쉽게 사용할 수있는 도구를 사용해 보지 않겠습니까?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top