4

ブックマークのリストがあります。各ブックマークにはキーワードのリストがあります (HashSet として保存されます)。また、考えられるすべてのキーワード ("universe") のセットもあります。

ブックマークに最も多く表示されるキーワードを見つけたい。

合計 698,539 個のキーワード、187,358 個の固有のキーワードを持つ 1356 個のブックマークがあります。

宇宙のすべてのキーワードを反復処理し、それが表示されるブックマークの数を数えると、254,057,448 回のチェックを行っていることになります。私のマシンでは、これに 35 秒かかります。

アルゴリズムは非常に単純です。

var biggest = universe.MaxBy(kw => bookmarks.Count(bm => bm.Keywords.Contains(kw)));

Jon Skeet の MaxByを使用します。

これを大幅に高速化できるかどうかはわかりませんが、何かできることはありますか? おそらく何とかそれを並列化しますか？

dtb のソリューションは、宇宙の構築と最大の要素の発見の両方に 200 ミリ秒未満かかります。とても簡単。

var freq = new FreqDict();
foreach(var bm in bookmarks) {
    freq.Add(bm.Keywords);
}
var biggest2 = freq.MaxBy(kvp => kvp.Value);

FreqDictの上に構築した小さなクラスですDictionary<string,int>。

4

4 に答える 4

4

すべてのキーワードを取得し、それらをグループ化し、最大のグループを取得できます。これはより多くのメモリを使用しますが、より高速になるはずです。

これを試してみたところ、私のテストでは約 80 倍高速でした。

string biggest =
  bookmarks
  .SelectMany(m => m.Keywords)
  .GroupBy(k => k)
  .OrderByDescending(g => g.Count())
  .First()
  .Key;

テスト走行：

1536 bookmarks
153600 keywords
74245 unique keywords

Original:
12098 ms.
biggest = "18541"

New:
148 ms.
biggest = "18541"
于 2012-08-12T07:49:13.940 に答える
2

宇宙全体を反復する必要はありません。アイデアは、ルックアップを作成して最大を追跡することです。

    public Keyword GetMaxKeyword(IEnumerable<Bookmark> bookmarks)
    {
        int max = 0;
        Keyword maxkw = null;

        Dictionary<Keyword, int> lookup = new Dictionary<Keyword, int>();

        foreach (var item in bookmarks)
        {
            foreach (var kw in item.Keywords)
            {
                int val = 1;

                if (lookup.ContainsKey(kw))
                {
                    val = ++lookup[kw];
                }
                else
                {
                    lookup.Add(kw, 1);
                }

                if (max < val)
                {
                    max = val;
                    maxkw = kw;
                }
            }
        }

        return maxkw;
    }
于 2012-08-12T07:49:14.630 に答える
2

私はあなたのサンプルデータを持っておらず、ベンチマークも行っていませんが、突き刺します. 改善できる問題の 1 つは、bm.Keywords.Contains(kw)チェックのほとんどがミスであることであり、それらは回避できると思います。最も制約的なのは、特定のブックマークが持つキーワードのセットです (つまり、通常はユニバースよりもはるかに小さいでしょう)。そのため、他の方法ではなく、その方向から開始する必要があります。

私はこれらの線に沿って何かを考えています。メモリ要件ははるかに高く、何もベンチマークしていないため、遅くなるか、役に立たない可能性がありますが、うまくいかない場合は回答を削除します.

Dictionary<string, int> keywordCounts = new Dictionary<string, int>(universe.Length);
foreach (var keyword in universe)
{
    keywordCounts.Add(keyword, 0);
}

foreach (var bookmark in bookmarks)
{
    foreach (var keyword in bookmark.Keywords)
    {
        keywordCounts[keyword] += 1;
    }
}

var mostCommonKeyword = keywordCounts.MaxBy(x => x.Value).Key;
于 2012-08-12T07:55:20.360 に答える
1

Python で 50 ミリ秒:

>>> import random

>>> universe = set()
>>> bookmarks = []
>>> for i in range(1356):
...     bookmark = []
...     for j in range(698539//1356):
...         key_word = random.randint(1000, 1000000000)
...         universe.add(key_word)
...         bookmark.append(key_word)
...     bookmarks.append(bookmark)
...
>>> key_word_count = {}
>>> for bookmark in bookmarks:
...     for key_word in bookmark:
...         key_word_count[key_word] = key_word_count.get(key_word, 0) + 1
...

>>> print max(key_word_count, key=key_word_count.__getitem__)
408530590

>>> print key_word_count[408530590]
3
>>>
于 2012-08-12T12:25:43.010 に答える