c# - 从一个列表中排除另一个列表中存在的项目

Question

我有一个列表，例如 List<string> ListProviderKeys它有一些值(value)。我还有来自下面类的第二个列表，例如 List<ChangesSummary> SecondList;

public class ChangesSummary
{
    public string TableName { get; set; }
    public string ProviderKey { get; set; }
    public string ProviderAdrsKey { get; set; }
    public string ProviderSpecialtyKey { get; set; }
    public string FieldName{ get; set; }
}

假设第一个列表包含的值与我们放入 ProviderKey 的值相同第二个列表中的字段。现在我想要的是将第二个列表缩减为只包含其 ProviderKey 的值。 IS NOT 已经在第一个列表中。我怎样才能做到这一点？我知道运营商 Except 但不确定如何在这种情况下应用它!

Answer 1

我能想到的最好的是:

A) 创建字典并使用它的快速查找

B) 在此字典上使用 LINQ .Where 方法和 .ContainsKey()，该字典内部使用 Hashtable 并执行快速查找。

这应该将搜索复杂度降低到几乎 O(1) 而不是 O(N) 甚至更糟(当我们使用 LINQ .Where() 与 .Any() 或 .Contains() 并导致嵌套循环)。

来自 MSDN page :

The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

所以我们可以做的是:

Dictionary<string, string> dict = ListProviderKeys.ToDictionary(s => s);

var newList = SecondList.Where(e => !dict.ContainsKey(e.ProviderKey)).ToList();

这是一个非常简单、简短但完整的示例，说明了它并测试了它的性能:

class Person
{
    public int Id { get; set; }        
}

class Program
{
    static void Main(string[] args)
    {
        List<int> ints = new List<int>();
        List<Person> People = new List<Person>(1000);

        for (int i = 0; i < 7500; i++)
        {
            ints.Add(i);
            ints.Add(15000 - i - 1);
        }

        for (int i = 0; i < 45000; i++)
            People.Add(new Person() { Id = i });

        Stopwatch s = new Stopwatch();

        s.Start();

        // code A (feel free to uncomment it)         
        //Dictionary<int, int> dict = ints.ToDictionary(p => p);

        //List<Person> newList = People.Where(p => !dict.ContainsKey(p.Id)).ToList();

        // code B
        List<Person> newList = People.Where(p => !ints.Contains(p.Id)).ToList();

        s.Stop();

        Console.WriteLine(s.ElapsedMilliseconds);
        Console.WriteLine("Number of elements " + newList.Count);

        Console.ReadKey();
    }

在 release 模式下结果是:

代码 A 和代码 B 都输出 30 000 个元素，但是:

code B用了2000多ms，code A只用了5ms