分组和选择整数列表的最快方法（最高出现次数）

我有一个包含100万到1亿整数的整数列表。

我想根据它们的出现次数对它们进行排名，并选择前K （此处为K=10 ）的结果。

我已经尝试了4种不同的方法，我的方法1最快。 并行化没有超过我自己在Method1的分组代码，并且由于线程竞争条件导致排名不准确。

Method1和Method4结果准确无误，而Method3和Method3可能由于竞争条件而导致排名不准确。

现在，我正在寻找比Method1更快的任何代码，或者修复并行化方法，使它们准确然后比Method1更快。

 class Benchmark { static List input = new List(); static void Main(string[] args) { int count = int.Parse(args[0]); Random rnd = new Random(); for (int i = 0; i < count; i++) input.Add(rnd.Next(1, count)); DoBench(); Console.ReadKey(); } private static void DoBench() { for (int i = 1; i <= 4; i++) { DateTime start = DateTime.Now; List<KeyValuePair> results = null; switch (i) { case 1: results = Method1(); break; case 2: results = Method2(); break; case 3: results = Method3(); break; case 4: results = Method4(); break; } int resultsCount = 10; var topResults = results.Take(resultsCount).OrderByDescending(x => x.Value).ThenBy(x => x.Key).ToArray(); for (int j = 0; j < resultsCount; j++) Console.WriteLine("No {0,2}: {1,8}, Score {2,4}", j + 1, topResults[j].Key, topResults[j].Value); Console.WriteLine("Time of Method{0}: {1} ms", i, (long)DateTime.Now.Subtract(start).TotalMilliseconds); Console.WriteLine(); } } private static List<KeyValuePair> Method1() { Dictionary dic = new Dictionary(); for (int i = 0; i  x.Value).ToList(); return sorted_results; } private static List<KeyValuePair> Method2() { var sorted_results = input.AsParallel().GroupBy(x => x) .Select(g => new KeyValuePair(g.Key, g.Count())) .OrderByDescending(x => x.Value).ToList(); return sorted_results; } private static List<KeyValuePair> Method3() { ConcurrentDictionary dic = new ConcurrentDictionary(); input.AsParallel().ForAll((number) => { dic.AddOrUpdate(number, 1, new Func((key, oldValue) => oldValue + 1)); }); var sorted_results = dic.OrderByDescending(x => x.Value).ToList(); return sorted_results; } private static List<KeyValuePair> Method4() { var sorted_results = input.GroupBy(x => x) .Select(g => new KeyValuePair(g.Key, g.Count())) .OrderByDescending(x => x.Value).ToList(); return sorted_results; } } 

Answer 1

我认为你可以大大加快算法的一部分，找到10个最高计数，使用选择排序。

最快的方法是使用QuickSelect算法，但这对我来说有点太复杂了。

相反，我将演示使用部分选择排序 。

这是一个使用它的Method5() 。 它与Method1()基本相同，只是它在最后一个阶段使用部分排序而不是完整排序：

 private static List> Method5() { Dictionary dic = new Dictionary(); for (int i = 0; i < input.Count; i++) { int number = input[i]; if (dic.ContainsKey(number)) dic[number]++; else dic.Add(number, 1); } var result = dic.ToList(); partialSort(result, 10); return result; } private static void partialSort(List> list, int k) { for (int i = 0; i < k; ++i) { int maxIndex = i; int maxValue = list[i].Value; for (int j = i+1; j < list.Count; ++j) { if (list[j].Value > maxValue) { maxIndex = j; maxValue = list[j].Value; } } var temp = list[i]; list[i] = list[maxIndex]; list[maxIndex] = temp; } } 

我定时了一个RELEASE（而不是调试）版本，当K == 10时，这在我的PC上看起来快了近三倍。

较小的K相对于集合的大小将成比例地更快。 对于较大的K值（特别是当K接近集合的大小时），此算法可能比普通排序慢。

如果预计K很大，请不要使用此算法。 它的效率高度依赖于K的值相对于集合的大小而言较小。

Answer 2

我找到了一个更快的字典实现分组部分。 我使用了Adam Horvath编写的MapReduce.NET项目中的FastDictionary类（ 链接 ）。

使用FastDictionary我更新了我的Method1并编写了一个更快的新Method6 。 然后我从@Mattew Watson添加了快速排序并编写了Method7 。 最后，我完全把它们打了起来。

编辑

我想出了一个很棒的想法，可以在Method8中Method8地加速分组。 我的想法是使用一个预定义的数组，其大小最大为输入数组，因此我可以用数组替换字典。 当然，当Maximum-Element-of-Input/Size-Of-Input接近1和Maximum-Element-of-Input数量的比率适合存储器时， Method8是有效的。

编辑2

我写了另外3个名为Method9 ， Method10和Method11 。

我注意到收集分组结果并将它们添加到Method8列表需要大量不必要的内存，所以我稍微修改了partialSort并删除了内存开销。

再次，我注意到我在Int32 4个字节中持有的数量相对较少。 为什么？！ 因此，假设输入列表中没有元素出现超过65535 （ short.MaxValue ），我只需用占用内存一半的short数组替换Int32数组。

再一次，我注意到如果我们有一个内存关键场景并且再次假设输入数组中的大多数元素都小于255 （ byte.MaxValue ），我们可以将一个byte与普通字典一起用于具有高出现率的元素。 由于在分组操作期间进行了多次检查，并且最终需要合并结果，这种技术有点慢，但正如您在图表中所看到的，其内存使用量远远少于其他基于字典的初始方法。

时序：

内存使用情况：

时间比较

记忆比较

方法6：

  private static List> Method6() { FastDictionary dic = new FastDictionary(); for (int i = 0; i < input.Count; i++) { int number = input[i]; int pos = dic.InitOrGetPosition(number); int curr = dic.GetAtPosition(pos); dic.StoreAtPosition(pos, ++curr); } var sorted_results = dic.OrderByDescending(x => x.Value).ToList(); return sorted_results; } 

方法7：

  private static List> Method7() { FastDictionary dic = new FastDictionary(); for (int i = 0; i < input.Count; i++) { int number = input[i]; int pos = dic.InitOrGetPosition(number); int curr = dic.GetAtPosition(pos); dic.StoreAtPosition(pos, ++curr); } var result = dic.ToList(); partialSort(result, 10); return result; } 

方法8

  private static List> Method8() { int[] dic = new int[input.Max() + 1]; for (int i = 0; i < input.Count; i++) { dic[input[i]]++; } List> list = new List>(); for (int i = 0; i < dic.Length; i++) { if (dic[i] > 0) list.Add(new KeyValuePair(i, dic[i])); } partialSort(list, 10); return list; } 

方法9

  private static List> Method9() { int[] dic = new int[input.Max() + 1]; for (int i = 0; i < input.Count; i++) { dic[input[i]]++; } List> list = partialSort(dic, 10); return list; } 

方法10

  private static List> Method10() { short[] dic = new short[input.Max() + 1]; for (int i = 0; i < input.Count; i++) { dic[input[i]]++; } List> list = partialSort(dic, 10); return list; } 

方法11

  private static List> Method11() { byte[] dic = new byte[input.Max() + 1]; Dictionary largeDic = new Dictionary(); int index = 0; int val = 0; for (int i = 0; i < input.Count; i++) { index = input[i]; val = dic[index]; if (val < 255) dic[index] = (byte)(val + 1); // casting to byte else { if (largeDic.ContainsKey(index)) { largeDic[index]++; } else { largeDic.Add(index, 255 + 1); } } } List> list = new List>(); if (largeDic.Count == 0) { list = partialSort(dic, 10); } else { if (largeDic.Count < 10) { list.AddRange(largeDic.OrderByDescending(x => x.Value)); var tempList = partialSort(dic, 50); list.AddRange(tempList.Except(list, new KeyValueComparer()).Take(10 - list.Count)); } else { list = largeDic.OrderByDescending(x => x.Value).Take(10).ToList(); } } return list; } 

部分排序

不同的重载只有不同的参数类型（ int[] ， short[] ， byte[] ）

  private static List> partialSort(int[] list, int k) { int[] topIndexes = new int[k]; for (int i = 0; i < k; ++i) { int maxIndex = i; int maxValue = list[i]; for (int j = i + 1; j < list.Length; ++j) { if (list[j] > maxValue) { maxIndex = j; maxValue = list[j]; } } var temp = list[i]; list[i] = list[maxIndex]; list[maxIndex] = temp; topIndexes[i] = maxIndex; } List> top = new List>(); for (int i = 0; i < k; i++) top.Add(new KeyValuePair(topIndexes[i], list[i])); return top; }