什么是最快的非LINQ算法'；配对'；匹配多个单独列表中的项目

本文关键字：单独 列表 项目 配对 LINQ 算法 什么 | 更新日期: 2023-09-27 18:08:15

重要提示

对于那些将此标记为重复的人，请理解我们不想要基于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"参数实际上代表其中一个列表。(即，如果有四个列表，它也将有一个C侧和一个D侧。(

我们正在尝试构建一个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的方法。

什么是最快的非LINQ算法'；配对'；匹配多个单独列表中的项目

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

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

var list1 = new List<int?>(){1,2,4,5,6,8,9};
var list2 = new List<int?>(){2,3,4,6,8,9,10};
var left = from i in list1
            join k in list2 on i equals k
            into temp
            from k in temp.DefaultIfEmpty()
            select new {a = i, b = (i == k) ? k : (int?)null};

var right = from k in list2
            join i in list1 on k equals i
            into temp
            from i in temp.DefaultIfEmpty()
            select new {a = (i == k) ? i : (int?)i , b = k};
var result = left.Union(right);

如果你需要与你的示例相同的排序，那么你需要提供一个索引并按此排序(然后删除重复项(

var result = left.Select((o,i) => new {o.a, o.b, i}).Union(right.Select((o, i) => new {o.a, o.b, i})).OrderBy( o => o.i);
result.Select( o => new {o.a, o.b}).Distinct();
相关文章：