如何使我的函数像ArrayList上的"Contains"一样快速运行？

Question

我无法弄清楚Contains方法在a中找到元素所ArrayList花费的时间与我编写的小函数执行相同操作所花费的时间之间的差异.文档声明Contains执行线性搜索,因此它应该是,O(n)而不是任何其他更快的方法.但是,虽然确切的值可能不相关,但该Contains方法在00:00:00.1087087我的函数采用时以秒为单位返回00:00:00.1876165.它可能不会太多,但在处理更大的阵列时,这种差异会变得更加明显.我错过了什么,我应该如何编写我的功能以匹配其Contains表现？

我在.NET 3.5上使用C#.

public partial class Window1 : Window
{
    public bool DoesContain(ArrayList list, object element)
    {
        for (int i = 0; i < list.Count; i++)
            if (list[i].Equals(element)) return true;

        return false;
    }

    public Window1()
    {
        InitializeComponent();

        ArrayList list = new ArrayList();
        for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);

        Stopwatch sw = new Stopwatch();
        sw.Start();

        //Console.Out.WriteLine(list.Contains("zzz 9000000") + " " + sw.Elapsed);
        Console.Out.WriteLine(DoesContain(list, "zzz 9000000") + " " + sw.Elapsed);
    }
}

编辑:

好的,现在,小伙子,看:

public partial class Window1 : Window
{
    public bool DoesContain(ArrayList list, object element)
    {
        int count = list.Count;
        for (int i = count - 1; i >= 0; i--)
            if (element.Equals(list[i])) return true;

        return false;
    }


    public bool DoesContain1(ArrayList list, object element)
    {
        int count = list.Count;
        for (int i = 0; i < count; i++)
            if (element.Equals(list[i])) return true;

        return false;
    }

    public Window1()
    {
        InitializeComponent();

        ArrayList list = new ArrayList();
        for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);

        Stopwatch sw = new Stopwatch();
        long total = 0;
        int nr = 100;

        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            DoesContain(list,"zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);


        total = 0;
        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            DoesContain1(list, "zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);


        total = 0;
        for (int i = 0; i < nr; i++)
        {
            sw.Reset();
            sw.Start();
            list.Contains("zzz");
            total += sw.ElapsedMilliseconds;
        }
        Console.Out.WriteLine(total / nr);
    }
  }

我为我的两个版本的函数(前向和后向循环)和默认Contains函数平均运行了100次.我有时间136和 133我的功能和一个遥远的赢家毫秒87的Contains版本.那么现在,如果你之前认为数据稀缺并且我将我的结论建立在第一次孤立的运行之前,你对这个测试有什么看法？并非只是平均Contains表现更好,但它在每次运行中都能获得始终如一的更好结果.那么,这里的第三方功能是否存在某种劣势,或者是什么？

Answer 1

首先,你没有多次运行它并比较平均值.

其次,你的方法在实际运行之前不会被jitted.因此,及时编译时间会被添加到其执行时间中.

真正的测试会每次多次运行并对结果取平均值(任何数量的事情都可能导致运行X中的一个或另一个在总Y中变慢),并且应该使用ngen.exe对程序集进行预处理.

Answer 2

当您使用.NET 3.5时,为什么要使用ArrayList它,而不是List<string>？

一些事情要尝试:

• 您可以看到使用foreach而不是for循环有助于

• 你可以缓存计数:

  public bool DoesContain(ArrayList list, object element)
  {
      int count = list.Count;
      for (int i = 0; i < count; i++)
      {
          if (list[i].Equals(element))
          {
              return true;
          }
          return false;
      }
  }
  

• 你可以改变比较:

  if (element.Equals(list[i]))
  

虽然我不希望其中任何一个产生显着的(积极的)差异,但它们是我接下来要尝试的东西.

你需要不止一次进行这种遏制测试吗？如果是这样,您可能想要构建HashSet<T>并重复使用它.

Answer 3

使用下面的代码，我能够相对一致地获得以下计时（在几毫秒内）：
1: 190msDoesContainRev
2: 198msDoesContainRev1
3: 188msDoesContainFwd
4: 203msDoesContainFwd1
5: 199msContains

这里有几点需要注意。

1. 这是通过命令行发布编译代码来运行的。许多人在 Visual Studio 调试环境中对代码进行基准测试时犯了错误，并不是说这里有人犯过，但需要小心。

2. 看起来list[i].Equals(element)比 慢一点element.Equals(list[i])。

   using System;
   using System.Diagnostics;
   using System.Collections;
   
   
   namespace ArrayListBenchmark
   {
   class Program
   {
       static void Main(string[] args)
       {
           Stopwatch sw = new Stopwatch();
           const int arrayCount = 10000000;
           ArrayList list = new ArrayList(arrayCount);
           for (int i = 0; i < arrayCount; i++) list.Add("zzz " + i);
       sw.Start();
       DoesContainRev(list, "zzz");
       sw.Stop();
       Console.WriteLine(String.Format("1: {0}", sw.ElapsedMilliseconds));
       sw.Reset();
   
       sw.Start();
       DoesContainRev1(list, "zzz");
       sw.Stop();
       Console.WriteLine(String.Format("2: {0}", sw.ElapsedMilliseconds));
       sw.Reset();
   
       sw.Start();
       DoesContainFwd(list, "zzz");
       sw.Stop();
       Console.WriteLine(String.Format("3: {0}", sw.ElapsedMilliseconds));
       sw.Reset();
   
       sw.Start();
       DoesContainFwd1(list, "zzz");
       sw.Stop();
       Console.WriteLine(String.Format("4: {0}", sw.ElapsedMilliseconds));
       sw.Reset();
   
       sw.Start();
       list.Contains("zzz");
       sw.Stop();
       Console.WriteLine(String.Format("5: {0}", sw.ElapsedMilliseconds));
       sw.Reset();
   
       Console.ReadKey();
   }
   public static bool DoesContainRev(ArrayList list, object element)
   {
       int count = list.Count;
       for (int i = count - 1; i >= 0; i--)
           if (element.Equals(list[i])) return true;
   
       return false;
   }
   public static bool DoesContainFwd(ArrayList list, object element)
   {
       int count = list.Count;
       for (int i = 0; i < count; i++)
           if (element.Equals(list[i])) return true;
   
       return false;
   }
   public static bool DoesContainRev1(ArrayList list, object element)
   {
       int count = list.Count;
       for (int i = count - 1; i >= 0; i--)
           if (list[i].Equals(element)) return true;
   
       return false;
   }
   public static bool DoesContainFwd1(ArrayList list, object element)
   {
       int count = list.Count;
       for (int i = 0; i < count; i++)
           if (list[i].Equals(element)) return true;
   
       return false;
   }
            }
           }