过滤 List .NET C# - 最佳性能 - 奇怪的结果

Question

所以我试图在 c# .NET5 中过滤一个列表，我想关注进程的性能。目前该程序正在为此使用 ForEach 循环，这很糟糕。

不管怎样，这就是例子，我得到了一个字符串列表，它可以包含任何类型的字符串，包括 null 或 empty。有 10k 个条目。

我找到了使用 LINQ 的过滤方法，例如.Where 或 .RemoveAll，随你喜欢过滤。

首先我认为最好和最快的方法是制作一个哈希集并使用 List.RemoveAll(i => hashset.Contains(i)) 因为我所有的研究都指出使用 hashset.Contains 迭代列表是最快的方法。我还认为 RemoveAll 会更快，因为 Contains-Method 的检查可以在 returns 一个“真实”情况下立即停止。

我做了一个 fiddle 来对所有这些方法进行基准测试，但事实是，我得到了这些结果：

.Where & HashSet contains: 0.7018 MS
.RemoveAll & HashSet contains: 0.4803 MS
.Where & List contains: 0.0072 MS
.RemoveAll & List contains: 0.4504 MS
.Where 0.1234 MS
.RemoveAll 0.0006 MS
ForEach 41.8379 MS

这些结果提出了新的问题，希望我能得到解释或明确的答案。

问题：

正如预期的那样，.RemoveAll & HashSet 比 .Where & HashSet 快，但这不适用于 List.Contains，为什么？
为什么 List.Contains 的结果比两种 HashSet 方法都快？特别是 .Where & List
为什么总是检查 4 个语句是否为真的常规 List.Where 比两种 HashSet 方法更快？
我预计 List.RemoveAll 会很快，但我没想到会那么快...我查找的大部分搜索和问题，人们总是建议使用 HashSet 这样的一个案例。

我希望有人能解释，至少解释一部分。

编辑：

我想通了，最后一个 .RemoveAll 方法是我做的一个错误，我用了 .Where 而不是 .RemoveAll，现在事情变得更清楚了。我还删除了 ForEach 循环中的 .ToLower 函数

现在我得到了这些结果：

.Where & HashSet contains: 0.6769 MS
.RemoveAll & HashSet contains: 0.4603 MS
.Where & List contains: 0.0052 MS
.RemoveAll & List contains: 0.449 MS
.Where 0.1103 MS
.RemoveAll 0.305 MS
ForEach 0.4445 MS

但我还是想问，为什么在使用.Where 时HashSet 比List 花费的时间长。还有为什么在使用 HashSet 时 RemoveAll 比 Where 快，而 List 却相反？

Answer 1

我认为你在这里比较的数字完全错误。

Where 什么也没做，真的。它创建一个 IEnumerable 实例，该实例将在需要时调用过滤器函数，即迭代集合时。因为您的 fiddle 不会迭代集合，所以过滤器谓词从未真正执行过。
RemoveAll 和 foreach 实现也意味着比较苹果和橘子，因为您的 foreach 实现使用 ToLower，这是一个非常昂贵的函数。删除 ToLower 方法调用，foreach 是最快的。特别是，将项目添加到 List 大致为 O(1)，而从列表中删除项目为 O(n)，因此很明显 RemoveAll 比 foreach 慢。
我相信列表中的 foreach 仍会创建枚举器的实例。您可以使用 for 循环来省略它。这将“更快”，但肯定不会解决任何问题。
你为什么还要问？ 10k 项目真的不是那么多。我宁愿专注于使过滤器谓词正确，而不是考虑如何调用它。除非您确实有高性能需求，否则差异可以忽略不计。

Answer 2

在我看来，您的测试具有误导性。您在 for each 循环（2x ToLower）中进行更昂贵的比较，并且在大多数 Linq 语句中您甚至不执行查询（它们处于 deferred/unexecuted 状态）。

在这种情况下列表击败哈希集的原因是它们都只包含几个元素 (5)，而且您比较的列表将只包含 5 个不同的值。所以大多数时候你调用 List.Contains 你将有少于 3 次迭代 - 在这种情况下你至少要为每个元素额外调用 GetHashCode 的情况下，这比在散列中要走的步骤更少。

如果我重构您的测试，ForEach 会比 Where 高出大约 1% 到 10%。如果我改变不同元素的数量，HashSet 远远胜过 List（快 5 倍）！我没有使用 RemoveAll，因为它是一个不同的操作。

/*

Result of Benchmark.RunAllTests():

Test 'where hashset' took 42,71700 msec
Test 'where list' took 285,44390 msec
Test 'foreach hashset' took 41,99030 msec
Test 'foreach list' took 277,24130 msec

*/
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp1
{
    class Benchmark
    {
        Random _random = new Random();

        public void RunAllTests() {

            var hs = Enumerable.Range(0, 100).Select(i => _random.Next(0, i).ToString()).ToHashSet();
            var ls    = new List<string>(hs);

            var bigList = FillList(1_000_000, ls);

            //warmup, let all assemblies load
            RunTest(() => bigList.Take(100).Where(s => !hs.Contains(s)).ToList(), "", true);
            RunTest(() => bigList.Take(100).Where(s => !ls.Contains(s)).ToList(), "", true);
            //exec real tests
            RunTest(() => bigList.Where(s => !hs.Contains(s)).ToList(), "where hashset");
            RunTest(() => bigList.Where(s => !ls.Contains(s)).ToList(), "where list");
            RunTest(() => ForEach(hs).ToList(),                         "foreach hashset");
            RunTest(() => ForEach(ls).ToList(),                         "foreach list");

            IEnumerable<string> ForEach(ICollection<string> coll) {
                foreach (var s in bigList) {
                    if (!coll.Contains(s))
                        yield return s;
                }
            }
        }

        private List<string> FillList(int totalCount, IList<string> elementsToUse)
        {
            var input = new List<string>();
            
            for (var i = 0; i < totalCount; i++)
            {
                var n = _random.Next(0, elementsToUse.Count);
                input.Add(elementsToUse[n]);
            }

            return input;
        }

        private void RunTest(Func<IList<string>> test, string name, bool silent = false) {
            var watch = new Stopwatch();
            watch.Start();
            var list = test.Invoke();

            if (silent) {
                return;
            }
            var ms = watch.Elapsed.TotalMilliseconds;
            watch.Stop();
            Console.WriteLine("Test '{0:-20}' took {1:N5} msec", name, ms);
        }
    }
}

过滤 List .NET C# - 最佳性能 - 奇怪的结果

Filtering a List .NET C# - best performance - strange results

c#

linq

collections

performance

.net-5