로그 파일에서 상위 100 개 URL 얻기

Question

내 친구 중 한 명이 인터뷰에서 다음 질문을 받았습니다. 아무도 그것을 해결하는 방법을 말해 줄 수 있습니까?

매우 큰 로그 파일 인 약 5GB가 있습니다. 로그 파일의 각 행에는 사용자가 사이트에서 방문한 URL이 들어 있습니다. 우리는 사용자가 방문한 가장 인기있는 100 개의 URL이 무엇인지 파악하려고합니다. 그것을하는 방법?

Answer 1

10GB 이상의 RAM이있는 경우 해시 맵을 사용하면 간단하게 처리 할 수 ​​있습니다.

그렇지 않으면 해시 함수를 사용하여 여러 파일로 분리하십시오. 그런 다음 각 파일을 처리하고 상위 5 개를 얻습니다. 각 파일에 대해 "상위 5 개"를 사용하면 전체 상위 5 개를 쉽게 얻을 수 있습니다.

또 다른 솔루션은 외부 정렬 방법을 사용하여 정렬 할 수 있습니다. 그런 다음 파일을 한 번 스캔하여 각각의 발생을 계산하십시오. 이 과정에서 카운트를 추적 할 필요가 없습니다. top5에없는 물건은 안전하게 버릴 수 있습니다.

Answer 2

URL에 따라 로그 파일을 정렬하고 (힙 정렬 또는 빠른 정렬과 같은 알고리즘을 선택한 경우 일정한 공간이 필요함) 각 URL을 몇 번 표시하는지 계산합니다 (쉽게 URL이 같은 줄은 서로 옆에).

전체적인 복잡성은 O (n * Log (n))입니다.

이

 File1 File2 File3 
url1 5  0  5 
url2 0  5  5 
url3 5  5  0 
url4 5  0  0 
url5 0  5  0 
url6 0  0  5 
url7 4  4  4 

url7는 결코 개별 파일에서 상위 3으로하지 않습니다하지만입니다 : 많은 파일의 분할 및 각 파일에 대해 (또는 상위 5 개 또는 상위 N) (3) 상단에만 유지가 잘못 왜

전반적으로 가장 좋습니다.

Answer 3

로그 파일이 상당히 크기 때문에 스트림 판독기를 사용하여 로그 파일을 읽어야합니다. 그것을 메모리에서 모두 읽지 마십시오. 로그 파일을 작업하는 동안 가능한 뚜렷한 링크가 메모리에있을 가능성이 높습니다.

// Pseudo 
Hashmap map<url,count> 
while(log file has nextline){ 
    url = nextline in logfile 
    add url to map and update count 
} 

List list 
foreach(m in map){ 
    add m to list   
} 

sort the list by count value 
take top n from the list 

런타임은 O (N) + O (m의 * 로그 (m)) n은 라인의 로그 파일의 크기 및 여기서 m은 별개의 볼 연결의 개수이다.

다음은 의사 코드의 C# 구현입니다. 실제 파일 판독기 및 로그 파일은 제공되지 않습니다. 대신 메모리의 목록을 사용하여 로그 파일을 읽는 간단한 에뮬레이션이 제공됩니다.

알고리즘은 해시 맵을 사용하여 발견 된 링크를 저장합니다. 정렬 알고리즘은 이후 상위 100 개의 링크를 찾습니다. 간단한 데이터 컨테이너 데이터 구조가 정렬 알고리즘에 사용됩니다.

메모리 복잡성은 예상되는 개별 링크에 따라 다릅니다. 해시 맵은 발견 된 고유 링크 인 을 포함 할 수 있어야합니다. 그렇지 않으면이 알고리즘이 작동하지 않습니다.

// Implementation 
using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Program 
{ 
    public static void Main(string[] args) 
    { 
     RunLinkCount(); 
     Console.WriteLine("press a key to exit"); 
     Console.ReadKey(); 
    } 

    class LinkData : IComparable 
    { 
     public string Url { get; set; } 
     public int Count { get; set; } 
     public int CompareTo(object obj) 
     { 
      var other = obj as LinkData; 
      int i = other == null ? 0 : other.Count; 
      return i.CompareTo(this.Count); 
     } 
    } 

    static void RunLinkCount() 
    { 
     // Data setup 
     var urls = new List<string>(); 
     var rand = new Random(); 
     const int loglength = 500000; 
     // Emulate the log-file 
     for (int i = 0; i < loglength; i++) 
     { 
      urls.Add(string.Format("http://{0}.com", rand.Next(1000) 
       .ToString("x"))); 
     } 

     // Hashmap memory must be allocated 
     // to contain distinct number of urls 
     var lookup = new Dictionary<string, int>(); 

     var stopwatch = new System.Diagnostics.Stopwatch(); 
     stopwatch.Start(); 

     // Algo-time 
     // O(n) where n is log line count 
     foreach (var url in urls) // Emulate stream reader, readline 
     { 
      if (lookup.ContainsKey(url)) 
      { 
       int i = lookup[url]; 
       lookup[url] = i + 1; 
      } 
      else 
      { 
       lookup.Add(url, 1); 
      } 
     } 

     // O(m) where m is number of distinct urls 
     var list = lookup.Select(i => new LinkData 
      { Url = i.Key, Count = i.Value }).ToList(); 
     // O(mlogm) 
     list.Sort(); 
     // O(m) 
     var top = list.Take(100).ToList(); // top urls 

     stopwatch.Stop(); 
     // End Algo-time 

     // Show result 
     // O(1) 
     foreach (var i in top) 
     { 
      Console.WriteLine("Url: {0}, Count: {1}", i.Url, i.Count); 
     } 

     Console.WriteLine(string.Format("Time elapsed msec: {0}", 
      stopwatch.ElapsedMilliseconds)); 
    } 
} 

편집 :이 답변은 코멘트를 기반으로 업데이트되었습니다

• 추가 :
• 추가 시간과 메모리 복잡도 분석을 실행 : 의사 코드를
• 추가 : 우리는 방법을 설명 꽤 큰 로그 파일을 관리하십시오.