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; }
}

其中每个“边”参数实际上代表列表之一。 (即如果有四个列表，它也会有一个 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 集(ASide 为空)实例化新的 ListPairing。

但是，考虑到所有必需的“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());
    }
}