c# - 从多个单独列表中匹配 'pair up' 项目的最快非 LINQ 算法是什么？

Question

重要说明

对于将其标记为重复的人，请理解我们不需要基于 LINQ 的解决方案。我们的实际示例有几个数以万计的原始列表，并且基于 LINQ 的解决方案的性能不足以满足我们的需求，因为它们必须多次遍历列表才能执行其功能，并随着每个新的源列表进行扩展。

这就是为什么我们专门寻找一种非 LINQ 算法，例如下面这个答案中建议的算法，它们通过枚举器同时遍历所有列表，并且仅一次。这似乎是迄今为止最好的，但我想知道是否还有其他。

现在回到问题...

为了解释我们的问题，请考虑这个假设的问题:

我有多个列表，但为了使这个示例简单，我们将其限制为两个，ListA 和 ListB，这两个列表的类型都是 List<int> 。他们的数据如下:

List A    List B
  1         2
  2         3
  4         4
  5         6
  6         8
  8         9
  9        10

...但是实际列表可能有数万行。

接下来我们有一个名为 ListPairing 的类，其定义如下:

public class ListPairing
{
    public int? ASide{ get; set; }
    public int? BSide{ get; set; }
}

其中每个“side”参数实际上代表列表之一。 (即，如果有四个列表，它也会有一个 CSide 和一个 DSide。)

我们正在尝试构建一个 List<ListPairing>数据初始化如下:

A Side    B Side
  1         -
  2         2
  -         3
  4         4
  5         -
  6         6
  8         8
  9         9
  -        10

Again, note there is no row with '7'

如您所见，结果看起来像一个完整的外部联接。不过，请参阅下面的更新。

现在开始，我们可以简单地这样做......

var finalList = ListA.Select(valA => new ListPairing(){ ASide = valA} );

这会产生...

A Side    B Side
  1         -
  2         -
  4         -
  5         -
  6         -
  8         -
  9         -

现在我们要回填列表 B 中的值。这需要首先检查是否存在与 BSide 匹配的 ASide 的 ListPairing，如果存在，则设置 BSide。

如果不存在具有匹配 ASide 的现有 ListPairing，则仅使用 BSide 集实例化新的 ListPairing(ASide 为空。)

但是，考虑到所需的所有“FindFirst”调用，我感觉这不是最有效的方法。 (这些列表可能有数万个项目长。)

但是，预先将这些列表进行并集会产生以下值...

1, 2, 3, 4, 5, 6, 8, 9, 10 (Note there is no #7)

我的想法是以某种方式使用值的有序并集，然后同时“遍历”两个列表，根据需要构建 ListPairings。这消除了对 FindFirst 的重复调用，但我想知道这是否是最有效的方法。

想法？

更新

人们认为这是使用 LINQ 获取完整外部联接的重复，因为结果是相同的......

在 LINQ 完全外部连接之后，我不是。我正在寻找一种高性能的算法。

因此，我更新了问题。

我提出这个问题的原因是执行该功能所需的 LINQ 对于我们的需求来说太慢了。在我们的模型中，实际上有四个列表，每个列表都可以有数万行。这就是为什么我建议在最后使用 ID 的“联合”方法来获取要遍历的唯一“键”列表，但我认为发布的关于执行相同操作但使用枚举器的答案是一个更好的方法，因为您不需要预先提供 ID 列表。这将产生同时遍历列表中所有项目的单次传递，这将轻松超越基于 LINQ 的方法。

Answer 1

这并没有像我希望的那样整洁，但是如果两个输入列表都已排序，那么您可以一起遍历它们并比较每个列表的头元素:如果它们相等，那么您就有一对，否则单独发出最小的一个并推进该列表。

public static IEnumerable<ListPairing> PairUpLists(IEnumerable<int> sortedAList,
                                                   IEnumerable<int> sortedBList)
{
    // Should wrap these two in using() per Servy's comment with braces around
    // the rest of the method.
    var aEnum = sortedAList.GetEnumerator();
    var bEnum = sortedBList.GetEnumerator();
    bool haveA = aEnum.MoveNext();
    bool haveB = bEnum.MoveNext();

    while (haveA && haveB)
    {
        // We still have values left on both lists.
        int comparison = aEnum.Current.CompareTo(bEnum.Current);
        if (comparison < 0)
        {
            // The heads of the two remaining sequences do not match and A's is
            // lower. Generate a partial pair with the head of A and advance the
            // enumerator.
            yield return new ListPairing() {ASide = aEnum.Current};
            haveA = aEnum.MoveNext();
        }
        else if (comparison == 0)
        {
            // The heads of the two sequences match. Generate a pair.
            yield return new ListPairing() {
                    ASide = aEnum.Current,
                    BSide = bEnum.Current
                };
            // Advance both enumerators
            haveA = aEnum.MoveNext();
            haveB = bEnum.MoveNext();
        }
        else
        {
            // No match and B is the lowest. Generate a partial pair with B.
            yield return new ListPairing() {BSide = bEnum.Current};
            // and advance the enumerator
            haveB = bEnum.MoveNext();
        }
    }
    if (haveA)
    {
        // We still have elements on list A but list B is exhausted.
        do
        {
            // Generate a partial pair for all remaining A elements.
            yield return new ListPairing() { ASide = aEnum.Current };
        } while (aEnum.MoveNext());
    }
    else if (haveB)
    {
        // List A is exhausted but we still have elements on list B.
        do
        {
            // Generate a partial pair for all remaining B elements.
            yield return new ListPairing() { BSide = bEnum.Current };
        } while (bEnum.MoveNext());
    }
}