如何使我的函数像ArrayList上的“Contains”一样快速运行?

使用下面的代码,我能够相对一致地获得以下计时(在几毫秒内):

2:198ms DoesContainRev1
3:188ms DoesContainFwd

这里有几点需要注意。

1. 这是使用命令行中的版本编译代码运行的。很多人都犯了在VisualStudio调试环境中对代码进行基准测试的错误,这里不是说有人这样做了,而是要小心。

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;
   }
            }
           }
   

第二,在方法实际运行之前,它不会被JIT。因此,即时编译时间被添加到其执行时间中。

一个真正的测试将每次运行多次并平均结果(任何数量的事情都可能导致一个或另一个在总共Y次运行X时变慢),并且您的程序集应该使用 ngen.exe .

当您使用.NET3.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> 反复使用。

我不确定是否允许发布Reflector代码,但是如果您打开使用Reflector的方法,您可以看到它本质上是相同的 (有一些针对空值的优化,但是您的测试工具不包括空值)。

我能看到的唯一区别就是 list[i] 边界检查吗 i

用一个 好的优化器应该没有任何区别,因为语义似乎是相同的。然而 优化器可以优化您的功能,但不如硬编码的 Contains 是优化的。优化的一些要点:

1. 每次与属性进行比较可能比向下计数并与0进行比较慢
2. 函数调用本身有其性能损失
3. 使用迭代器而不是显式索引可以更快( foreach for )

首先,如果您使用的是提前知道的类型,我建议您使用泛型。所以用列表代替ArrayList。在引擎盖下面,ArrayList.Contains实际上比您正在做的要多一些。以下是来自反射器的信息:

public virtual bool Contains(object item)
{
    if (item == null)
    {
        for (int j = 0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    for (int i = 0; i < this._size; i++)
    {
        if ((this._items[i] != null) && this._items[i].Equals(item))
        {
            return true;
        }
    }
    return false;
}

您确定您正在处理完全编译的代码吗?也就是说,当您的代码第一次运行时,它得到了JIT编译,而框架显然已经编译好了。

编辑之后,我复制了代码并对其进行了一些改进。

要查看此信息,请将跑步更改为以下表格:

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

我猜想ArrayList是用C++编写的,可以利用一些微优化(注意:这是猜测)。

例如,在C++中,可以使用指针算术(特别是增加指针来重复数组),比使用索引更快。

否则,您应该使用集合。

阅读评论后修订:

Hash-alogorithm

使用 SortedList<TKey,TValue> Dictionary<TKey, TValue> System.Collections.ObjectModel.KeyedCollection<TKey, TValue> 用于基于密钥的快速访问。

var list = new List<myObject>(); // Search is sequential
var dictionary = new Dictionary<myObject, myObject>(); // key based lookup, but no sequential lookup, Contains fast
var sortedList = new SortedList<myObject, myObject>(); // key based and sequential lookup, Contains fast

KeyedCollection<TKey, TValue> 它也很快,允许索引查找,但是,它需要继承,因为它是抽象的。因此,您需要一个特定的集合。但是,通过以下操作,您可以创建一个泛型 KeyedCollection .

public class GenericKeyedCollection<TKey, TValue> : KeyedCollection<TKey, TValue> {
   public GenericKeyedCollection(Func<TValue, TKey> keyExtractor) {
      this.keyExtractor = keyExtractor;
   }

   private Func<TValue, TKey> keyExtractor;

   protected override TKey GetKeyForItem(TValue value) {
      return this.keyExtractor(value);
   }
}

使用KeyedCollection的优点是Add方法不需要指定键。