为什么列表＆lt; t＆gt; .contains（）太慢了？

Question

我有一个对象列表，我想通过删除某些具有ids的对象来过滤列表，即单独的列表中，即

List<Vehicle> vehicles;  //All Vehicles List (260 vehicles data)
List<int> vehiclesIds;  //Ids List to remove from Original List (Length < 260)

现在使用removeall（） >它采用Asound 25到30秒。

vehicles.RemoveAll(e => vehiclesIds.Contains(e.Id));

但是，如果我将用于循环，则仅需8至20毫秒。

foreach (var vehiclesId in vehiclesIds)
{
    vehicles.RemoveAll(e=> vehiclesId == e.Id);
}

我多次运行此代码，并在使用stopwatch list.contains（）是进行缓慢处理的原因。

Answer 1

这两个版本之间的逻辑不同。

第一个版本首先循环车辆，寻找ID中的比赛。 包含使用默认比较，这可能是一种缓慢的比较方式，因为它使用了接口。

您可以使用hashset＆lt;查找匹配ID来改进此版本。这应该更快（即使它也使用包含），因为它可以内部使用HashTable。

List<Vehicle> vehicles;  //All Vehicles List (260 vehicles data)
HashSet<int> vehiclesIds;  //Ids List to remove from Original List (Length < 260)

vehicles.RemoveAll(e => vehiclesIds.Contains(e.Id));

第二个版本首先循环较小的ID列表。您可以通过使用字典为车辆来改进此版本，

Dictionary<int, Vehicle> vehicles;  //All Vehicles List (260 vehicles data)
List<int> vehiclesIds;  //Ids List to remove from Original List (Length < 260)

foreach (var vehiclesId in vehiclesIds)
{
    vehicles.Remove(vehiclesId);
}

我想这是最后一个版本是最快的。

Answer 2

TLDR：您问题的答案“为什么list.contains（）太慢？”是：不是。您没有向我们展示的其他地方一定有问题。

更长的答案：

第一个版本应该更快，因为它仅在列表中删除一次而不是多次删除元素。 （事实并不能更快地指向其他地方的某些问题。）

但是，第一个版本确实调用了eartilesIds.contains（e.id）（e.id） 每辆车一次，这是O（n）手术。

您可以通过从车辆ID中创建HashSet＆gt;来改进它，然后将其用于查找。

我尝试了三种方法（您的两种方法hashset One）：

using System;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace Demo;

static class Program
{
    public static void Main()
    {
        var summary = BenchmarkRunner.Run<UnderTest>();
    }
}

sealed class Vehicle
{
    public int Id { get; set; }
}

public class UnderTest
{
    public UnderTest()
    {
        var rng = new Random(34655);

        for (int i = 0; i < NUM_IDS; ++i)
            _vehicleIds.Add(rng.Next(0, MAX_ID));

        _idsHash = _vehicleIds.ToHashSet();
    }

    [IterationSetup]
    public void IterationSetup()
    {
        Console.WriteLine("IterationSetup");
        createVehicleList();
    }

    [Benchmark]
    public void RemoveItemsUsingRemoveAll()
    {
        _vehicles.RemoveAll(e => _vehicleIds.Contains(e.Id));
    }

    [Benchmark]
    public void RemoveItemsUsingLoop()
    {
        foreach (int vehiclesId in _vehicleIds)
        {
            _vehicles.RemoveAll(e => vehiclesId == e.Id);
        }
    }

    [Benchmark]
    public void RemoveItemsUsingHashSet()
    {
        _vehicles.RemoveAll(e => _idsHash.Contains(e.Id));
    }

    void createVehicleList()
    {
        _vehicles.Clear();
        var rng = new Random(78712);

        for (int i = 0; i < NUM_VEHICLES; ++i)
        {
            _vehicles.Add(new Vehicle {Id = rng.Next(MAX_ID)});
        }
    }

    const int NUM_VEHICLES = 200_000;
    const int MAX_ID       = 800_000;
    const int NUM_IDS      =   1_000;

    readonly List<int>     _vehicleIds = new ();
    readonly List<Vehicle> _vehicles   = new ();
    readonly HashSet<int>  _idsHash;
}

我在PC上获得的结果如下：

|                     Method |       Mean |      Error |     StdDev |     Median |
|--------------------------- |-----------:|-----------:|-----------:|-----------:|
|  RemoveItemsUsingRemoveAll |  68.360 ms |  1.4030 ms |  4.0926 ms |  67.828 ms |
|       RemoveItemsUsingLoop | 625.148 ms | 19.4181 ms | 56.3354 ms | 607.409 ms |
|    RemoveItemsUsingHashSet |   5.293 ms |  0.2643 ms |  0.7626 ms |   5.323 ms |    

如您所见，使用第一个版本明显比第二个版本要快得多。版本（我预期），但是使用HashSet甚至更快。

我们必须得出的结论是，您看到的放缓是由于您没有向我们展示的代码。