Pierwsze 100 adresów URL z pliku dziennika

Question

Jeden z moich przyjaciół został poproszony o następujące pytanie w wywiadzie. Czy ktoś może mi powiedzieć, jak go rozwiązać?

Mamy dość duży plik dziennika, około 5 GB. Każda linia pliku dziennika zawiera adres URL, który użytkownik odwiedził w naszej witrynie. Chcemy dowiedzieć się, jakie są najpopularniejsze 100 adresów URL odwiedzanych przez naszych użytkowników. Jak to zrobić?

Answer 1

Jeśli mamy więcej niż 10 GB pamięci RAM, po prostu zrób to prosto z hashmap.

W przeciwnym razie rozdziel go na kilka plików, używając funkcji skrótu. Następnie przetwórz każdy plik i zdobądź 5 najlepszych. W przypadku "5 najlepszych" dla każdego pliku łatwo będzie uzyskać ogólne górne 5.

Inne rozwiązanie można sortować za pomocą dowolnej zewnętrznej metody sortowania. Następnie zeskanuj plik, aby policzyć każde wystąpienie. W trakcie tego procesu nie musisz śledzić liczby. Możesz bezpiecznie rzucić wszystko, co nie robi się w top5.

Answer 2

Po prostu posortuj plik dziennika zgodnie z URL-ami (potrzebuje stałej przestrzeni, jeśli wybrałeś algorytm sortowania sterty lub szybkiego sortowania), a następnie policz dla każdego adresu URL ile razy się pojawi (łatwe, linie o tych samych adresach URL są obok siebie).

Ogólna złożoność to O (n * Log (n)).

Dlaczego dzielenie w wielu plikach i utrzymując jedynie Top 3 (lub top 5 lub top N) dla każdego pliku jest źle:

 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 nigdy nie dotrze do górnej 3 w poszczególnych plików, ale jest najlepiej ogólnie.

Answer 3

Ponieważ plik dziennika jest dość duży, należy odczytać plik dziennika za pomocą czytnika strumienia. Nie czytaj wszystkiego w pamięci. Oczekuję, że możliwe będzie posiadanie liczby możliwych różnych połączeń w pamięci podczas pracy nad plikiem dziennika.

// 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 

czas przebiegu wynosi O (n) + O (M * log (m)), gdzie n jest rozmiar pliku dziennika w linii i w którym m oznacza liczbę odrębnych znalezione linki.

Oto C# implementacja pseudokodu. Rzeczywisty czytnik plików i plik dziennika nie są dostarczane. Zamiast tego dostarczana jest prosta emulacja odczytu pliku dziennika przy użyciu listy w pamięci.

Algorytm używa hashmap do przechowywania znalezionych linków. Algorytm sortowania znajduje później 100 najlepszych linków. Do algorytmu sortowania wykorzystywana jest prosta struktura danych kontenera danych.

Złożoność pamięci zależy od oczekiwanych, odrębnych łączy. Histop musi zawierać różne znalezione linki, inaczej ten algorytm nie zadziała.

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

Edit: Ta odpowiedź została zaktualizowana na podstawie uwag

• dodania: czas i analizę złożoności pamięci
• dodaną działa: pseudo-kod
• dodania: wyjaśnić, w jaki sposób zarządzaj dość dużym plikiem rejestru