c# - 具有非唯一条目的两个列表之间的差异

Question

我有两个列表。一个代表我的代码可以运行的函数类型，另一个代表将运行这些函数的代理。这两个列表应该是一对一的关系，但是当远程服务请求更多功能时，我需要找出这两个列表之间的区别。 问题是条目不是唯一的，因此我不能只调用 list1.RemoveAll(list2) 因为这会删除 List2 中包含的具有相同值的所有条目，而不是每个条目仅删除一个条目.

这就是我需要的:

{a,a,a,a,b,b,c} - {a,a,b,c} = {a,a,b}

这就是我现在的做法:

var difference = list1.ToList();
foreach (var entry in list2)
{
    difference.Remove(entry);
}

它很实用并且可以完成工作，但它破坏了我在其余代码中的 Linq 用法。

我尝试找出一种方法并在网上搜索，但找不到使用 Linq 来执行此操作的方法。

Answer 1

对于长集合(序列)，嵌套循环和Remove可能无效(从O (N * M)到O(N * N * M)) 您可以尝试用 O (N + M) 时间进行分组和字典复杂。请注意，该实现不保持初始顺序({a, b, b, a} - {b} == {a, a, b}，而不是 {a, b, a}):

List<char> left = new List<char>() { 'a', 'a', 'a', 'a', 'b', 'b', 'c' };
List<char> right = new List<char>() { 'a', 'a', 'b', 'c' };

var counts = right
  .GroupBy(item => item)
  .ToDictionary(chunk => chunk.Key, chunk => chunk.Count());

var difference = left
  .GroupBy(item => item)
  .SelectMany(chunk => chunk.Skip(counts.TryGetValue(chunk.Key, out var skip) ? skip : 0))
  .ToList();

编辑:创建基准很容易；基准；如果序列较长 (N = 200000)，则以 hash(GroupBy、Dictionary)为准；确保如果您没有那么长的集合，您可以安全地保留初始代码:

Random rnd = new Random(1);

int N = 200000;

List<char> left = Enumerable
  .Range(0, N)
  .Select(index => (char)(rnd.Next('z' - 'a') + 'a'))
  .ToList();

List<char> right = Enumerable
  .Range(0, N)
  .Select(index => (char)(rnd.Next('z' - 'a') + 'a'))
  .ToList();

现在让马跑:

Stopwatch watch = new Stopwatch();

watch.Start();

// Hash solution
var counts = right
  .GroupBy(item => item)
  .ToDictionary(chunk => chunk.Key, chunk => chunk.Count());

var result = left
  .GroupBy(item => item)
  .SelectMany(chunk => chunk.Skip(counts.TryGetValue(chunk.Key, out var skip) ? skip : 0))
  .ToList();

watch.Stop();

TimeSpan tHash = watch.Elapsed;

watch.Reset();
watch.Start();

// Initial solution
var difference = left.ToList();

foreach (var entry in right) {
  difference.Remove(entry);
}

watch.Stop();

TimeSpan tInitial = watch.Elapsed;

Console.Write($"Hash: {tHash}; Initial {tInitial}");

结果(酷睿 i7 3.6GHz)11 毫秒 与 1.4 秒

  Hash: 00:00:00.0111296; Initial 00:00:01.3957468