在一个列表中找到不在另一个列表中的项

Question

我有两个对象列表，我想从第一个列表中获取所有那些在第二个列表中的字符串a不匹配的对象。

public class ObjectA  
{  
    string Item;  
    int b;  
}

public class ObjectB  
{  
    string Item;  
    int b;  
}

这可以通过LINQ轻松完成，但有没有更快的方法？

var newList = objectAList.Where(a => !objectBList.Any(b => b.Item == a.Item)).ToList()

- user3266638

---

你的列表大小是多少？另一种方法是使用两个嵌套的for语句。但是说这样会更快并没有太大意义。你应该进行一些基准测试。对于小型列表的行为可能是可以忽略的，但对于中型或大型列表可能不是这样。什么是小？什么是大？通过所有这些问题，我试图说服你，如果你没有找到另一种解决相同问题的方法并进行基准测试，那么这就没有任何意义。 - Christos

你是在寻找更快的方式，非LINQ方式，或者既是非LINQ方式又更快的方式吗？你有没有关于解决这个问题的想法或尝试过什么方法？ - Lance U. Matthews

@Christos 嵌套的for语句是O(n*m)。Linq的Except要好得多。 - Eric J.

@EricJ。我同意。我的观点是，当你只有一个解决方案时，试图回答哪个更快是没有意义的。即使有两个解决方案，如果你不运行任何基准测试，任何猜测都可能毫无意义。 - Christos

去掉“没有LINQ”的条件，可能会重复Most efficient way to compare two lists and delete the same。与Find if listA contains any elements not in listB，Use LINQ to get items in one List<>, that are not in another List<>，或Difference between two lists并没有太大的不同。 - Lance U. Matthews

Answer 1

这个怎么样 - 没有linq，仍然很好，流畅，为正确的类型进行了编辑：

ObjectBList.RemoveAll(p => ObjectAList.Find(p2 => p2.Item == p.Item) != null ? true : false);

完整示例：

public class ObjectBase {
    public string Item;
    public int b;
}

public class ObjectA : ObjectBase{ }

public class ObjectB : ObjectBase { }

public List<ObjectB> Testing() {
    var list1 = new List<ObjectA> { new ObjectA { Item = "str1", b = 0 } };
    var list2 = new List<ObjectB> { new ObjectB { Item = "str1", b = 0 }, new ObjectB { Item = "str2", b = 1 } };

    // Key Line - Remove all from list2 found in list1
    list2.RemoveAll(p => list1.Find(p2 => p2.Item == p.Item) != null ? true : false);

    return list2;
}

- MrRobboto

---

这不会对OP在他的问题中提到的对象产生影响。 - Eric J.

是的，你需要使用IEqualityComparer<T>和Contains来使它在引用类型上工作，并仅检查一个属性进行比较。不过这并没有太大区别——RemoveAll()和Contains()是避免在这种情况下使用Linq的关键。我会尽快更新我的答案... - MrRobboto

编辑过了，我确实不得不做出一些更改。使用.Find()比使用包含比较器等更容易。 - MrRobboto

Answer 2

Linq的Except方法专为此目的而设计，速度非常快。但是，您有一个问题，即两个类具有兼容的字段但是是不同的对象。以下是一种处理方式：

class ObjectBase
{
    public string Item;
    public int b;
}

class ObjectA : ObjectBase
{

}

class ObjectB : ObjectBase
{

}

class ObjectComparer : IEqualityComparer<ObjectBase>
{
    public bool Equals(ObjectBase a, ObjectBase b)
    {
        return a?.Item == b?.Item; 
    }
    public int GetHashCode(ObjectBase o)
    {
        return o.?Item?.GetHashCode() ?? 0;
    }
}

// Very fast compared to your current approach. 1000x for my test case.

var newList = objectAList.Except(objectBList, new ObjectComparer()).ToList();

- Eric J.

Answer 3

你可以尝试这段代码：

public static void Main(string[] args)
{
  List<ObjectA> listA = new List<ObjectA>()
  {
    new ObjectA(){Item = "abc" },
    new ObjectA(){Item = "ab" },
  };
  List<ObjectB> listB = new List<ObjectB>()
  {
    new ObjectB(){Item = "abc" },
  };
  // loop backwards removing entry if it is found in the other list
  for (int i = listA.Count - 1; i >= 0; i--)
    if (listB.Find(e => e.Item == listA[i].Item) != null)
      listA.RemoveAt(i);
}

我分别运行了你的方法和我的方法五次，并得到了以下结果（每次在循环中重复算法，100000次迭代），以毫秒为单位：

我的方法：107 46 94 67 91

你的方法：108 267 171 138 173

这也可能是由于额外的ToList()调用和创建新对象newList导致的。

因此，总的来说，如果有任何改进，那么它非常微小，我不会为此牺牲由精美的LINQ方法提供的可读性。

此外，它们在内部被设计为尽可能快地工作，所以我会依靠它们 :)

- Michał Turczyn

---

RemoveAt操作相对较慢，因为它是一个O(N)的操作，并且您必须执行M次（其中M是要删除的交叉元素的数量），因此整个算法的时间复杂度为O(N*M)。 - Eric J.

Answer 4

更快的方法是：

var newList = objectAList.Select(a => a.Item).Except(objectBList.Select(b => b.Item));

是的，我知道这是Linq，但您要求一种更快的方法 ：）

希望对您有所帮助

- Canica

---

除非是必须要用Except，否则它只会给你Items，而不是实际的对象。 - Eric J.

Answer 5

从时间上来看，最快的方法是使用HashSet<>，特别是对于大型列表：

    private List<ObjectA> Find(List<ObjectA> list1, List<ObjectB> list2)
    {
        var list2HashSet = list2.Select(x => x.Item).ToHashSet();
        return list1.Where(x => !list2HashSet.Contains(x.Item)).ToList();
    }

注意：不要忘记将属性Item设置为公共的，否则它将无法工作！

- tgralex