12

（这个问题来自从这里开始的讨论）

我正在比较使用中查找值的时间与true手动循环的时间。List<bool>List.Contains()

我看到的结果与其他人报告的结果不同。我已经在几个系统上尝试过，在我尝试过的所有系统上，循环似乎快了 2 到 3.5 倍。这些系统的范围从运行 XP 和 .Net 4 的 5 年前的笔记本电脑到运行 Windows 8 和 .Net 4.5 的最新 PC。

其他人报告了不同的结果，即List.Contains()与循环速度大致相同或略快。

这是我的测试代码。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main()
        {
            int size = 10000000;
            int count = 10;
            List<bool> data = new List<bool>(size);

            for (int i = 0; i < size; ++i)
                data.Add(false);

            var sw = new Stopwatch();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaLoop(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    TestViaListContains(data);

                sw.Stop();
                Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()");
                Console.WriteLine();
            }
        }

        static bool TestViaLoop(List<bool> data)
        {
            for (int i = 0; i < data.Count; ++i)
                if (data[i])
                    return true;

            return false;
        }

        static bool TestViaListContains(List<bool> data)
        {
            return data.Contains(true);
        }
    }
}

要测试此代码，您应该将其编译为 x86 RELEASE 版本，并从调试器外部运行它。

这是我使用 .Net 4.5 框架从我的 Windows 8 x64 PC 得到的结果（尽管我使用 .Net 4 得到了类似的结果）：

Times are in milliseconds

126 TestViaLoop()
441 TestViaListContains()

122 TestViaLoop()
428 TestViaListContains()

131 TestViaLoop()
431 TestViaListContains()

138 TestViaLoop()
426 TestViaListContains()

122 TestViaLoop()
439 TestViaListContains()

如您所见，循环花费了我系统上大约 1/3 的时间。

现在，如果我们使用它Resharper来查看它的实现，List.Contains()它看起来像这样：

bool Contains(T item)
{
    if (item == null)
    {
        for (int j = 0x0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;
    for (int i = 0x0; i < this._size; i++)
    {
        if (comparer.Equals(this._items[i], item))
        {
            return true;
        }
    }
    return false;
}

虽然它正在使用Comparer.Equals()（这应该使它比循环慢）它也_items[]直接使用私有数组，这避免了将用于我的循环实现的索引范围检查。

我有三个问题：

  1. 其他人可以复制我看到的结果吗？（请记住在调试器之外运行发布版本。）
  2. 如果是这样，任何人都可以解释我的循环如何比 快得多List.Contains()吗？
  3. 如果没有，谁能解释为什么我看到我的循环更快？

这对我来说不仅仅是学术上的兴趣，因为我编写的代码可以处理大量数字数据并且需要尽可能快，这是我需要了解的事情。（注意：是的，我分析了一些东西，只尝试优化需要优化的东西......我知道过早优化的问题。）

[编辑]

我突然想到这可能与处理器有关。我尝试过的所有系统都有英特尔处理器，尽管型号非常不同，从 3.8GHz 的四核到 1.6GHz 的奔腾 M 单核......

对于那些看到循环运行速度较慢的人，您正在运行英特尔处理器吗？

4

2 回答 2

4

它使用了 GenericEqualityComparer，如果我们看一下 Equals 方法的实现是这样的：

public override bool Equals(T x, T y)
{
  if ((object) x != null)
  {
    if ((object) y != null)
      return x.Equals(y);
    else
      return false;
  }
  else
    return (object) y == null;
}

当它检查对象是否不等于 null 时，它会对它们进行装箱，并得到两个装箱操作。此 IL 代码显示了它的外观：

IL_0002: box !T
IL_0007: ldnull
IL_0008: ceq

由 280Z28 编辑：相同方法的 CIL 在 .NET 4.5 中略有不同。

public override bool Equals(T x, T y)
{
    if (x != null)
        return ((y != null) && x.Equals(y));

    if (y != null)
        return false;

    return true;
}

这里是IL。对于任何查看 Reflector 的人，请注意brfalse.s和brnull.s是相同的说明。

L_0000: ldarg.1 
L_0001: box !T
L_0006: brnull.s L_0021
...

基线 JIT 编译器不会优化框操作，但我没有检查 NGen 或优化编译器是否可以。

于 2013-04-17T14:32:17.223 回答
1

您的循环实现产生与 相同的输出Contains，但您不能在一般情况下使用它。即，您最终将不得不Equals对更复杂的对象进行比较。该Contains实现比您的实现执行更多的工作，所以我不明白为什么在这种情况下您应该期望它更快。

如果你有一个自定义Person对象的列表，并重写Equals方法来比较它们的Address Name SSNumberand DateOfBirth，那么循环将以几乎相同的性能成本执行。

我希望原始值，然后是循环迭代将优于 generic Contains，但这是一个过早的优化，你不会（基本上）比Contains更复杂的对象比较做得更好。

于 2013-04-17T14:41:18.873 回答