更快计算项目出现的套数?
我有一个书签列表。 每个书签都有一个关键字列表(存储为HashSet)。 我还有一组所有可能的关键字(“宇宙”)。
我想找到大多数书签中出现的关键字。
我有1356个书签,总共有698,539个关键字,其中187,358个是唯一的。
如果我遍历Universe中的每个关键字并计算它出现的书签数量,我就会进行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
之上构建的一个小类。
我没有您的样本数据,也没有进行任何基准测试,但我会采取措施。 可以改进的一个问题是大多数bm.Keywords.Contains(kw)
检查都是未命中的,我认为可以避免这些。 最受约束的是给定书签的任何一个关键字集(即:它通常比宇宙小得多),所以我们应该从那个方向开始而不是从另一个方向开始。
我正在考虑这些问题。 内存需求要高得多,因为我没有对任何事情进行基准测试,它可能会更慢,或者没有帮助,但如果它不适合你,我会删除我的答案。
Dictionary keywordCounts = new Dictionary(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;
您可以获取所有关键字,对其进行分组,并获得最大的群组。 这会占用更多内存,但应该更快。
我尝试过这个,在我的测试中它快了大约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"
您不需要遍历整个Universe。 想法是创建一个查找和跟踪最大值。
public Keyword GetMaxKeyword(IEnumerable bookmarks) { int max = 0; Keyword maxkw = null; Dictionary lookup = new Dictionary(); 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; }
在python 50ms:
>>> 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 >>>