我做了一些关于 List.Contains、Array.Contains、IEnumerable.Contains、ICollection.Contains 和 IList.Contains 的基准测试。
结果是:
array pure 00:00:45.0052754 // 45 sec, slow
array as IList 00:00:02.7900305
array as IEnumerable 00:00:46.5871087 // 45 sec, slow
array as ICollection 00:00:02.7449889
list pure 00:00:01.9907563
list as IList 00:00:02.6626009
list as IEnumerable 00:00:02.9541950
list as ICollection 00:00:02.3341203
我发现直接调用Array.Contains会很慢(相当于调用IEnumerable)
另外，我觉得 MSDN 数组页面没有在扩展方法部分列出的 contains 方法很奇怪。
示例代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace arrayList
{
class Program
{
static void Main(string[] args)
{
Stopwatch watch = new Stopwatch();
Int64 n = 100000000;
Int64[] myarray = new Int64[] { 1, 2, 3 };
List<Int64> mylist = new List<Int64>(myarray);
watch.Start();
for (Int64 j = 0; j < n; j++)
{
bool i = myarray.Contains(2);
}
watch.Stop();
Console.WriteLine("array pure {0}", watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (myarray as IList<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("array as IList {0}",watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (myarray as IEnumerable<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("array as IEnumerable {0}",watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (myarray as ICollection<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("array as ICollection {0}",watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = mylist.Contains(2);
}
watch.Stop();
Console.WriteLine("list pure {0}", watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (mylist as IList<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("list as IList {0}", watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (mylist as IEnumerable<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("list as IEnumerable {0}", watch.Elapsed);
watch.Restart();
for (Int64 j = 0; j < n; j++)
{
bool i = (mylist as ICollection<Int64>).Contains(2);
}
watch.Stop();
Console.WriteLine("list as ICollection {0}", watch.Elapsed);
Console.ReadKey();
}
}
}
最佳答案
您为这些计时的方式是不够的。您需要大得多的输入才能获得代表算法的时间。是的 Contains() 会比简单的线性搜索慢(你已经省略了)但是不同的调用不会像你所显示的那样有时间。当转换为不同的类型时，您可能看不到对 Contains() 的调用之间有任何差异，因为我们很可能会为所有类型调用相同的实现。
尝试使用此代码确定大小:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
const int iterations = 1000000;
const long target = 7192;
var arr = Enumerable.Range(0, 10000).Select(i => (long)i).ToArray();
var list = arr.ToList();
bool result;
var arr0 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = LinearSearchArr(arr, target);
}
arr0.Stop();
var arr1 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
// actually Enumerable.Contains()
result = arr.Contains(target);
}
arr1.Stop();
var arr2 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((IList<long>)arr).Contains(target);
}
arr2.Stop();
var arr3 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((IEnumerable<long>)arr).Contains(target);
}
arr3.Stop();
var arr4 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((ICollection<long>)arr).Contains(target);
}
arr4.Stop();
var list0 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = LinearSearchList(list, target);
}
list0.Stop();
var list1 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = list.Contains(target);
}
list1.Stop();
var list2 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((IList<long>)list).Contains(target);
}
list2.Stop();
var list3 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((IEnumerable<long>)list).Contains(target);
}
list3.Stop();
var list4 = Stopwatch.StartNew();
for (var i = 0; i < iterations; i++)
{
result = ((ICollection<long>)list).Contains(target);
}
list4.Stop();
Console.WriteLine("array linear {0} ({1})", arr0.Elapsed, arr0.ElapsedTicks);
Console.WriteLine("array pure {0} ({1})", arr1.Elapsed, arr1.ElapsedTicks);
Console.WriteLine("array as IList {0} ({1})", arr2.Elapsed, arr2.ElapsedTicks);
Console.WriteLine("array as IEnumerable {0} ({1})", arr3.Elapsed, arr3.ElapsedTicks);
Console.WriteLine("array as ICollection {0} ({1})", arr4.Elapsed, arr4.ElapsedTicks);
Console.WriteLine("list linear {0} ({1})", list0.Elapsed, list0.ElapsedTicks);
Console.WriteLine("list pure {0} ({1})", list1.Elapsed, list1.ElapsedTicks);
Console.WriteLine("list as IList {0} ({1})", list2.Elapsed, list2.ElapsedTicks);
Console.WriteLine("list as IEnumerable {0} ({1})", list3.Elapsed, list3.ElapsedTicks);
Console.WriteLine("list as ICollection {0} ({1})", list4.Elapsed, list4.ElapsedTicks);
}
static bool LinearSearchArr(long[] arr, long target)
{
for (var i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return true;
}
}
return false;
}
static bool LinearSearchList(List<long> list, long target)
{
for (var i = 0; i < list.Count; i++)
{
if (list[i] == target)
{
return true;
}
}
return false;
}
}
}
规范:
Windows 7 专业版 64 位
英特尔酷睿 2 四核 Q9550 @ 2.83GHz
4x1GiB Corsair Dominator DDR2 1066 (PC2-8500)
针对 x64 的默认 .NET 4.0 控制台应用发布构建:
array linear 00:00:07.7268891 (21379939) array pure 00:00:12.1703848 (33674883) array as IList 00:00:12.1764948 (33691789) array as IEnumerable 00:00:12.5377771 (34691440) array as ICollection 00:00:12.1827855 (33709195) list linear 00:00:17.9288343 (49608242) list pure 00:00:25.8427338 (71505630) list as IList 00:00:25.8678260 (71575059) list as IEnumerable 00:00:25.8500101 (71525763) list as ICollection 00:00:25.8423424 (71504547)
关于c# - Array.Contains 运行速度非常慢，有人能解释一下吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7458803/