c# - 在多个列表中分布非唯一元素的最有效方法

Question

假设我有一个整数列表或其他任何东西

List<int> motherlist = { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 }

Console.WriteLine(children.Count); // 10

我想找到所有重复项，而不是将它们从列表中删除，而是将它们分布在其他列表中，因此所有 child 的最终计数应该与 Motherlist 相同:

List<List<int>> children = { { 1, 2, 5, 7, 6 }, { 1, 2 }, { 1, 2 }, { 2 }}

Console.WriteLine(children.Sum(l => l.Count())); // 10 same as mother

到目前为止，我尝试了一种蛮力方法，方法是遍历 Mother 的所有元素，将这些元素与所有其他元素进行比较并检查重复项，如果发现重复项，我将其添加到存储桶列表(列表列表)中，依此类推，直到最后一个元素。
但是，对于只有 300 个项目的母列表，蛮力方法需要 7 个 CPU 秒。
我想如果我有 1000 件元素，这将花费很长时间。
在 C# .NET 中是否有更快的方法来做到这一点？

Answer 1

我建议将重复项分组，然后考虑组的大小进行循环:

public static IEnumerable<List<T>> MyDo<T>(IEnumerable<T> source, 
                                           IEqualityComparer<T> comparer = null) {
  if (null == source)
    throw new ArgumentNullException(nameof(source));

  var groups = new Dictionary<T, List<T>>(comparer ?? EqualityComparer<T>.Default);

  int maxLength = 0;

  foreach (T item in source) {
    if (!groups.TryGetValue(item, out var list)) 
      groups.Add(item, list = new List<T>());
    
    list.Add(item);
    maxLength = Math.Max(maxLength, list.Count);
  }
  
  for (int i = 0; i < maxLength; ++i) {
    List<T> result = new List<T>();

    foreach (var value in groups.Values)
      if (i < value.Count)
        result.Add(value[i]);

    yield return result;
  }
}

演示:

  int[] source = new int[] { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };

  var result = MyDo(source).ToList();

  string report = string.Join(Environment.NewLine, result
    .Select(line => $"[{string.Join(", ", line)}]"));

  Console.Write(report);

结果:

[1, 2, 5, 7, 6]
[1, 2]
[1, 2]
[2]

压力演示:

  Random random = new Random(1234); // seed, the results to be reproducible

  // We don't want 1000 items be forever; let's try 1_000_000 items
  int[] source = Enumerable
    .Range(1, 1_000_000)
    .Select(x => random.Next(1, 1000))
    .ToArray();

  Stopwatch sw = new Stopwatch();

  sw.Start();

  var result = MyDo(source).ToList();

  sw.Stop();

  Console.WriteLine($"Time: {sw.ElapsedMilliseconds} ms");

结果: (可能因工作站而异)

  Time: 50 ms