将两个列表根据属性合并为一个列表

Question

我想问一下是否有一种简洁高效的方法将两个MyClass列表合并成一个？

MyClass的结构如下：

ID：int类型

Name：字符串类型

ExtID：可空整数类型

这两个列表的来源不同，但它们共享相同的ID。因此列表看起来是这样的：

MyClass instance from List1
ID = someInt
Name = someString
ExtID = null

从List2中获取MyClass实例

ID = someInt (same as List1)
Name = someString (same as List1)
ExtID = someInt

我需要的是将这两个列表合并成一个包含以下内容的列表：

ID = someInt (from List1)
Name = someString (from List1)
ExtID = someInt (null if no corresponding item - based on ID - on List2)

我知道可以使用 foreach 循环来完成这个任务，但我想知道是否有更优雅、更受欢迎（因为性能和可读性）的方法？

- pzaj

---

编写一个“合并”函数，将具有相同“ID”的两个实例合并为一个 - 然后您可以连接列表，按ID分组，最后使用您的合并函数折叠/减少组 - 这就是我为可读性所做的 - 对于性能，您可能需要排序和循环。 - Random Dev

Answer 1

根据优先级，有很多不同的方法，例如联合加查找：

//this will create a key value pairs: id -> matching instances
var idMap = list1.Union(list2).ToLookup(myClass => myClass.ID);
//now just select for each ID the instance you want, ex. with some value
var mergedInstances = idMap.Select(row => 
      row.FirstOrDefault(myClass => myClass.ExtId.HasValue) ?? row.First());

上述方法的优点在于，它能够处理任何数量的任何列表，即使它们包含许多重复的实例，然后您可以轻松修改合并条件。

一个小的改进是提取一个合并实例的方法：

MyClass MergeInstances(IEnumerable<MyClass> instances){
     return instances.FirstOrDefault(myClass => myClass.ExtId.HasValue) 
          ?? instances.First(); //or whatever else you imagine
}

现在只需在上面的代码中使用它即可。

 var mergedInstances = idMap.Select(MergeInstances);

简洁、灵活、简单，没有额外的条件。性能方面不完美，但谁在乎。

编辑：由于性能是重点，以下是一些更多的选项

1. 像上面一样查找较小的列表，然后迭代大的列表并进行所需的更改 O(m log m) + O(n)。m-较小的列表大小，n-较大的列表大小-应该是最快的。

2. 按元素ID对两个列表进行排序。创建一个for循环，遍历它们，保持当前索引为两个列表中具有相同id的元素。如果只有一个列表中有它，则将索引移动到下一个最小的id。O(n log n) + O(m log m) + O(n)；

- mikus

---

如果每个元素都需要搜索其他列表的元素，则复杂度将为O(n^2)，而上述方法将更快，因为查找是O(log n) * O(n)的Select（实际上是一个foreach循环），复杂度为O(n log n)，比O(n^)更优。我赢了；）。使用查找表（字典/映射）是一种方法。你还可以得到灵活性。如果你能改进现有的解决方案，可以考虑从一开始就提供字典而不是列表。 - mikus

你可以在其中一个列表上创建一个查找表（或字典），然后只需使用查找表对第二个列表进行foreach循环，以快速查找值。 此外，您可以考虑对两个列表进行排序，并执行一次智能循环，仅通过两个列表O(n log n) + O(n)。 - mikus

如果名称是唯一的，您可以从一开始就基于名称而不是ID。 :) 如果不是，则对合并算法没有帮助，也没有关系。 因此，要么按照上述方式操作，要么从较小的列表中创建查找表并遍历其他列表（我认为这是最快的方法）。或者您将它们按ID（或名称）排序，并进行一次循环，同时在索引增加的方式下迭代两个列表，以便始终指向相同的元素ID。我会在答案中包含它。 - mikus

还有一个问题：Lookup 比 Dictionary 更快吗？我在考虑使用 Dictionary，因为我不需要重复的键（ID 总是唯一的）+ 我可以在每次迭代中从 Dictionary 中删除已经使用过的项（这样做在性能方面是否更好？） - pzaj

很难说它是否会更快，它不会压缩列表中的元素（或任何其他可枚举对象），因此肯定会更快，如果您只期望一个元素，则它是适合使用的 :) - mikus

Answer 2

这是你想要的吗？

var joined = from Item1 in list1
         join Item2 in list2
         on Item1.Id equals Item2.Id // join on some property
         select new MyClass(Item1.Id, Item1.Name, Item1.ExtID??Item2.ExtID);

编辑：如果您正在寻找外连接，

var query = from Item1 in list1
            join Item2 in list2 on Item1.Id equals Item2.Id into gj
            from sublist2 in gj.DefaultIfEmpty()
            select new MyClass(Item1.Id, Item1.Name, sublist2??string.empty);

就易读性而言，使用foreach循环并不是一个太糟糕的想法。

- Godsent

---

由于这是内连接，看起来如果其中一个列表中缺少某些ID，则它将无法正常工作。 - mikus

是的，没错，添加了外连接的情况。 - Godsent

Answer 3

我建议在该类的一个方法中创建foreach循环，这样每次需要执行此操作时，您都可以使用类似以下的内容。

instanceList1.MergeLists(instanceList2)

通过这种方法，您可以在合并操作中控制您想要的一切。

- Paulo Lima

---

@mikus LINQ 确实使用迭代和迭代器，因此关于foreach的评论不适用。另一方面，当OP询问如何编写该函数时，“编写自己的函数”不是一个好答案。也许应该将其删除并重新发布为评论？ - Panagiotis Kanavos

我只是假设他知道如何执行该函数，我认为这将是更好的方法。（他说他不想使用foreach，但我认为他的意思是，他不想每次需要执行合并操作时都使用它） - Paulo Lima