6

私の友人の一人がインタビューで次の質問をされました。誰かがそれを解決する方法を教えてもらえますか？

約5GBのかなり大きなログファイルがあります。ログファイルの各行には、ユーザーが当サイトでアクセスしたURLが含まれています。ユーザーがアクセスした最も人気のある100のURLを把握したいと思います。どうやってするの？

4

3 に答える 3

7

10GB 以上の RAM がある場合は、hashmap を使用して簡単に実行してください。

それ以外の場合は、ハッシュ関数を使用して複数のファイルに分割します。そして、各ファイルを処理してトップ 5 を取得します。各ファイルの「トップ 5」を使用すると、全体のトップ 5 を簡単に取得できます。

別の解決策は、外部のソート方法を使用してソートすることです。次に、ファイルを 1 回スキャンして、出現するたびにカウントします。その過程で、カウントを追跡する必要はありません。トップ 5 に入らないものは安全に捨てることができます。

于 2012-05-24T08:50:37.760 に答える
2

URLに従ってログファイルをソートするだけです（ヒープソートやクイックソートなどのアルゴリズムを選択した場合、一定のスペースが必要です）。次に、URLごとに表示回数を数えます（簡単です。同じURLの行が隣り合っています） ）。

全体的な複雑さは O(n*Log(n)) です。

多くのファイルに分割し、各ファイルの上位 3 (または上位 5 または上位 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 に入ることはありませんが、全体としては最高です。

于 2012-05-24T09:22:40.263 に答える
1

ログ ファイルはかなり大きいため、ストリーム リーダーを使用してログ ファイルを読み取る必要があります。メモリ内のすべてを読み取らないでください。ログファイルの作業中に、可能な数の異なるリンクをメモリ内に保持することは実行可能であると思います。

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

編集：この回答はコメントに基づいて更新されました

  • 追加: 実行時間とメモリの複雑さの分析
  • 追加: 疑似コード
  • 追加: かなり大きなログ ファイルをどのように管理するかを説明する
于 2012-05-24T09:47:33.740 に答える