在公共字段上加入C#中两个列表的最有效方法是什么？

Question

你能告诉我哪一个列表连接方法更有效,为什么？还是性能相同？有没有其他方法来处理这种情况(基于字段属性加入2个列表)？

我的代码:

public List<CombinedDatabaseStructure> Combine1(List<DatabaseStructure1> _Data1, List<DatabaseStructure2> _Data2)
{
    List<CombinedDatabaseStructure> combinedAll = new List<CombinedDatabaseStructure>();
    foreach (var row1 in _Data1)
    {
        foreach (var row2 in _Data2)
        {
            CombinedDatabaseStructure combined = new CombinedDatabaseStructure();
            if (row1.ID == row2.ID)
            {
                combined.DatabaseStructure1 = row1;
                combined.DatabaseStructure2 = row2;
                combinedAll.Add(combined);
            }
        }
    }

    return combinedAll;
}

代码2:

public List<CombinedDatabaseStructure> Combine2(List<DatabaseStructure1> _Data1, List<DatabaseStructure2> _Data2)
{
    var joined = from item1 in _Data1.AsEnumerable() 
                 join item2 in _Data2.AsEnumerable() on item1.ID equals item2.ID
                 select new CombinedDatabaseStructure (item1,item2);

    return  joined.ToList<CombinedDatabaseStructure>();
}

Answer 1

作为一般规则:如果.NET框架中有一个内置的方法可以完全按照您的要求进行操作,那么使用它而不是重新实现它通常是一个好主意.它更容易,更易读,更不容易出错,经过更好的测试,通常更有效地实施.

让我们详细看看你的具体问题:

选项1基本上是嵌套循环连接的手动(幼稚)实现,其复杂度为O(n*m).

选项2使用LINQ-to-object的实现join,它在内部使用散列连接,其复杂度为O(n+m).

如果您担心效率,我建议"选项3":让数据库进行连接.它可以使用统计信息为您的数据选择最佳连接策略.

注意:嵌套循环实现效率很低.O(n*log(m))通过使用某种索引查找来查找匹配的Data2行而不是内部循环,可以实现复杂性.在这种情况下,嵌套循环连接可能比散列连接更快,如果n非常小并且m很大.但是,这假定索引已经存在,因为创建索引(例如,通过从列表中创建C#字典)是一个O(m)操作本身.