c -使用多线程查找在多个链表中遇到的最大键数

Question

我有许多(大约60000)链表，这些链表由排序键递增的节点组成。键在每个链表中只出现一次，但它们可以在不同的链表中重复出现。每个链表的键值从0到4000(或其他大数字)。链接列表的示例如下(尽管这是一个非常小的示例)。

index 0: 1->3->9->212->400

index 1: 6->12->212->231->600

索引2:NULL

index 3: 2->3->1632

index 4: 1->3->45

index 5: 1000->3212

…

输入是一组与链表索引相对应的数字，例如0、3、4

则输出在给定索引中重复次数最多的键。在本例中，输出是3(因为它在所有三个链表中都重复了)。

这个问题可以用顺序算法来解决;遍历每个列表并跟踪优先级队列/max-heap中的键，其中队列的开头/max-heap的根具有命中次数最多的键。

因为这是一个大规模的问题，我想利用多线程的强大功能，以一种比顺序更快的方式解决这个问题，尽可能避免互斥以避免性能损失。有什么建议吗?

Answer 1

这是使用ConcurrentDictionary的非常简单的方法。该解决方案不依赖于正在排序的列表，也不依赖于一个值最多只能在列表中出现一次。此外，我已经用一个空集合替换了null列表，以简化代码。

var data = new Dictionary<Int32, IEnumerable<Int32>> {
  { 0, new[] { 1, 3, 9, 212, 400 } },
  { 1, new[] { 6, 12, 212, 231, 600 } },
  { 2, Enumerable.Empty<Int32>() },
  { 3, new[] { 2, 3, 1632 } },
  { 4, new[] { 1, 3, 45 } },
  { 5, new[] { 1000, 3212 } }
};
var input = new[] { 0, 3, 4 };
var counts = new ConcurrentDictionary<Int32, Int32>();
Parallel.ForEach(
  input.SelectMany(key => data[key]),
  key => counts.AddOrUpdate(key, k => 1, (k, count) => count + 1)
);
var maxCount = counts.OrderByDescending(kvp => kvp.Value).First().Value;
var results = counts
  .Where(kvp => kvp.Value == maxCount)
  .Select(kvp => kvp.Key)
  .ToList();

为了能够正确处理空输入，代码应该稍微修改一下，使用FirstOrDefault而不是First，但这样做只会使代码混乱。

我不知道这段代码是否特别有效，因为ConcurrentDictionary中的锁会有很多争用，所以您可能应该测量性能以更好地理解