logo标签列表

包含、存在和任意的性能基准测试

c#performancebenchmarking
89
我一直在寻找一个性能基准，来比较 List<T> 中提供的 Contains、Exists 和 Any 方法之间的差异。我想了解这些方法之间的区别，因为我经常对它们感到困惑。许多 Stack Overflow 上的问题描述了这些方法的定义，比如：

  1. LINQ Ring: Any() vs Contains() for Huge Collections
  2. Linq .Any VS .Exists - Whats the difference?
  3. LINQ extension methods - Any() vs. Where() vs. Exists()

所以我决定自己来做一下。我把它作为答案添加了进来。如果对结果有更多的见解，欢迎分享。我还为数组做了这个基准测试，以了解结果。

3个回答
102

最快的方法是使用 HashSet。 对于 HashSet 的 Contains 是 O(1)。

我拿了你的代码，并为 HashSet<int> 添加了基准测试。 HashSet<int> set = new HashSet<int>(list); 的性能成本几乎为零。

代码

void Main()
{
    ContainsExistsAnyVeryShort();
    
    ContainsExistsAnyShort();

    ContainsExistsAny();
}

private static void ContainsExistsAny()
{
    Console.WriteLine("***************************************");
    Console.WriteLine("********* ContainsExistsAny ***********");
    Console.WriteLine("***************************************");

    List<int> list = new List<int>(6000000);
    Random random = new Random();
    for (int i = 0; i < 6000000; i++)
    {
        list.Add(random.Next(6000000));
    }
    int[] arr = list.ToArray();
    HashSet<int> set = new HashSet<int>(list);

    find(list, arr, set, (method, stopwatch) => $"{method}: {stopwatch.ElapsedMilliseconds}ms");

}

private static void ContainsExistsAnyShort()
{
    Console.WriteLine("***************************************");
    Console.WriteLine("***** ContainsExistsAnyShortRange *****");
    Console.WriteLine("***************************************");

    List<int> list = new List<int>(2000);
    Random random = new Random();
    for (int i = 0; i < 2000; i++)
    {
        list.Add(random.Next(6000000));
    }
    int[] arr = list.ToArray();
    HashSet<int> set = new HashSet<int>(list);

    find(list, arr, set, (method, stopwatch) => $"{method}: {stopwatch.ElapsedMilliseconds}ms");

}

private static void ContainsExistsAnyVeryShort()
{
    Console.WriteLine("*******************************************");
    Console.WriteLine("***** ContainsExistsAnyVeryShortRange *****");
    Console.WriteLine("*******************************************");

    List<int> list = new List<int>(10);
    Random random = new Random();
    for (int i = 0; i < 10; i++)
    {
        list.Add(random.Next(6000000));
    }
    int[] arr = list.ToArray();
    HashSet<int> set = new HashSet<int>(list);

    find(list, arr, set, (method, stopwatch) => $"{method}: {stopwatch.ElapsedTicks} ticks");

}

private static void find(List<int> list, int[] arr, HashSet<int> set, Func<string, Stopwatch, string> format)
{
    Random random = new Random();
    int[] find = new int[10000];
    for (int i = 0; i < 10000; i++)
    {
        find[i] = random.Next(6000000);
    }

    Stopwatch watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        list.Contains(find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("List/Contains", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        list.Exists(a => a == find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("List/Exists", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        list.Any(a => a == find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("List/Any", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        arr.Contains(find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("Array/Contains", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        Array.Exists(arr, a => a == find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("Array/Exists", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        Array.IndexOf(arr, find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("Array/IndexOf", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        arr.Any(a => a == find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("Array/Any", watch));

    watch = Stopwatch.StartNew();
    for (int rpt = 0; rpt < 10000; rpt++)
    {
        set.Contains(find[rpt]);
    }
    watch.Stop();
    Console.WriteLine(format("HashSet/Contains", watch));
}

结果

*******************************************
***** ContainsExistsAnyVeryShortRange *****
*******************************************
List/Contains: 1067 ticks
List/Exists: 2884 ticks
List/Any: 10520 ticks
Array/Contains: 1880 ticks
Array/Exists: 5526 ticks
Array/IndexOf: 601 ticks
Array/Any: 13295 ticks
HashSet/Contains: 6629 ticks
***************************************
***** ContainsExistsAnyShortRange *****
***************************************
List/Contains: 4ms
List/Exists: 28ms
List/Any: 138ms
Array/Contains: 6ms
Array/Exists: 34ms
Array/IndexOf: 3ms
Array/Any: 96ms
HashSet/Contains: 0ms
***************************************
********* ContainsExistsAny ***********
***************************************
List/Contains: 11504ms
List/Exists: 57084ms
List/Any: 257659ms
Array/Contains: 11643ms
Array/Exists: 52477ms
Array/IndexOf: 11741ms
Array/Any: 194184ms
HashSet/Contains: 3ms

编辑（2021年8月25日）

我添加了对于非常短的集合（10项）的比较，并且添加了Array.Contains和Array.IndexOf。你可以看到在这种小范围内，Array.IndexOf是最快的。这是因为如@lucky-brian所说，n在这里非常小，因此for-loop的性能优于稍微复杂的搜索算法。不过，我仍建议尽可能使用HashSet<T>，因为它更好地反映了仅具有唯一值的意图，而对于小集合的差异低于1ms。

1
我正好在寻找这样的东西。当我看到HashSet/Contains的性能时，我就像“哇塞”一样。肯定会在我的1000..5000个项目的环境中尝试一下。 - Matthis Kohli
1
在这里看到一个HashMap的性能表现也会很不错。 - Matthis Kohli
你知道 HashSet 的 Any 是否也是 O(1) 吗？ - David Létourneau
HashSet<T> 中不存在 Any 方法，但它是 IEnumerable<T> 的扩展方法，如果没有谓词，则时间复杂度为 O(1)，如果有谓词，则时间复杂度为 O(n)。以下是源代码链接：https://github.com/Microsoft/referencesource/blob/master/System.Core/System/Linq/Enumerable.cs#L1288 - wertzui
1
"Arrays do not have Exists"？Array.Exists( https://learn.microsoft.com/en-us/dotnet/api/system.array.exists?view=netframework-4.7.2 - Mark Schultheiss
1
只是一个小提示，拥有O(1)的顺序并不一定意味着算法很快，它只是意味着其速度不取决于应用它的元素数量。它仍然可能需要很长时间才能完成。 - DrMcCleod
83
根据文档:
List.Exists (对象方法)
确定List(T)是否包含符合指定谓词条件的元素。
IEnumerable.Any (扩展方法)
确定序列中是否有任何元素满足条件。
List.Contains (对象方法)
确定一个元素是否在List中。
基准测试:
CODE:
    static void Main(string[] args)
    {
        ContainsExistsAnyShort();

        ContainsExistsAny();
    }
    
    private static void ContainsExistsAny()
    {
        Console.WriteLine("***************************************");
        Console.WriteLine("********* ContainsExistsAny ***********");
        Console.WriteLine("***************************************");

        List<int> list = new List<int>(6000000);
        Random random = new Random();
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(random.Next(6000000));
        }
        int[] arr = list.ToArray();

        find(list, arr);
    }

    private static void ContainsExistsAnyShort()
    {
        Console.WriteLine("***************************************");
        Console.WriteLine("***** ContainsExistsAnyShortRange *****");
        Console.WriteLine("***************************************");

        List<int> list = new List<int>(2000);
        Random random = new Random();
        for (int i = 0; i < 2000; i++)
        {
            list.Add(random.Next(6000000));
        }
        int[] arr = list.ToArray();

        find(list, arr);
    }

    private static void find(List<int> list, int[] arr)
    {
        Random random = new Random();
        int[] find = new int[10000];
        for (int i = 0; i < 10000; i++)
        {
            find[i] = random.Next(6000000);
        }

        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 10000; rpt++)
        {
            list.Contains(find[rpt]);
        }
        watch.Stop();
        Console.WriteLine("List/Contains: {0:N0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 10000; rpt++)
        {
            list.Exists(a => a == find[rpt]);
        }
        watch.Stop();
        Console.WriteLine("List/Exists: {0:N0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 10000; rpt++)
        {
            list.Any(a => a == find[rpt]);
        }
        watch.Stop();
        Console.WriteLine("List/Any: {0:N0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 10000; rpt++)
        {
            arr.Contains(find[rpt]);
        }
        watch.Stop();
        Console.WriteLine("Array/Contains: {0:N0}ms", watch.ElapsedMilliseconds);

        Console.WriteLine("Arrays do not have Exists");

        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 10000; rpt++)
        {
            arr.Any(a => a == find[rpt]);
        }
        watch.Stop();
        Console.WriteLine("Array/Any: {0:N0}ms", watch.ElapsedMilliseconds);
    }

结果

***************************************
***** ContainsExistsAnyShortRange *****
***************************************
List/Contains: 96ms
List/Exists: 146ms
List/Any: 381ms
Array/Contains: 34ms
Arrays do not have Exists
Array/Any: 410ms
***************************************
********* ContainsExistsAny ***********
***************************************
List/Contains: 257,996ms
List/Exists: 379,951ms
List/Any: 884,853ms
Array/Contains: 72,486ms
Arrays do not have Exists
Array/Any: 1,013,303ms
1
请记住，虽然Contains似乎是最快的，但LINQ 2 SQL在列表中有约2100个对象的限制，因此适用于较短的列表。 - Giannis Paraskevopoulos
@jyparask，即使对于更大的列表，Contains 也是一个不错的选择。不过，我已经更新了代码和短列表的计时。结果与您预测的一样。 - harshit
我运行了你的基准测试，并得出List.Exists实际上比List.Contains稍微快一些，分别为45毫秒和55毫秒。其余结果与你的测试结果一致。在32位Release模式下，使用Visual Studio 2013测试.NET 4.5，并进行了优化。 - Asik
2
你是什么意思：“数组没有Exists”？我认为它有Exists()方法：https://dev59.com/a2Yr5IYBdhLWcg3w8-vA#22928748 - 123iamking
4
"Arrays do not have Exists" 可以翻译为“数组没有Exists”。Array.Exists()是一个C#中的方法，用于在数组中查找满足指定条件的元素，并返回布尔值表示是否存在这样的元素。 - Mark Schultheiss
将这些表现与传统的循环搜索（for或foreach）进行比较，会很有趣。 - Ishikawa
5
值得一提的是，这种比较有点不公平，因为Array类没有拥有Contains()方法。它通过一个连续的Enumerator使用IEnumerable<T>的扩展方法，因此并非针对Array实例进行了优化。而另一方面，HashSet<T>具有自己的实现，完全针对所有大小进行了优化。
要进行公平的比较，可以使用静态方法int Array.IndexOf()，该方法为Array实例实现，即使它使用了一个for循环，效率略高于一个Enumerator。
使用公平的比较算法，对于小于5个元素的小集合，HashSet<T>.Contains()的性能与Array.IndexOf()相似，但对于大型集合来说更加高效。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接