为什么C#Array.BinarySearch这么快?

本文介绍了为什么C#Array.BinarySearch这么快?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我已经在C#中实现了非常简单的 binarySearch实现，用于在整数数组中查找整数:

I have implemented a very simple binarySearch implementation in C# for finding integers in an integer array:

static int binarySearch(int[] arr, int i) { int low = 0, high = arr.Length - 1, mid; while (low <= high) { mid = (low + high) / 2; if (i < arr[mid]) high = mid - 1; else if (i > arr[mid]) low = mid + 1; else return mid; } return -1; }

将其与C#的本机Array.BinarySearch()进行比较时，我发现Array.BinarySearch()每次都比我的函数快两倍以上.

When comparing it to C#'s native Array.BinarySearch() I can see that Array.BinarySearch() is more than twice as fast as my function, every single time.

MSDN" rel ="nofollow noreferrer"> Array.BinarySearch :

MSDN on Array.BinarySearch:

使用由Array的每个元素和指定对象实现的IComparable通用接口，在整个一维排序数组中搜索特定元素.

Searches an entire one-dimensional sorted array for a specific element, using the IComparable generic interface implemented by each element of the Array and by the specified object.

是什么使这种方法如此快速?

What makes this approach so fast?

using System; using System.Diagnostics; class Program { static void Main() { Random rnd = new Random(); Stopwatch sw = new Stopwatch(); const int ELEMENTS = 10000000; int temp; int[] arr = new int[ELEMENTS]; for (int i = 0; i < ELEMENTS; i++) arr[i] = rnd.Next(int.MinValue,int.MaxValue); Array.Sort(arr); // Custom binarySearch sw.Restart(); for (int i = 0; i < ELEMENTS; i++) temp = binarySearch(arr, i); sw.Stop(); Console.WriteLine($"Elapsed time for custom binarySearch: {sw.ElapsedMilliseconds}ms"); // C# Array.BinarySearch sw.Restart(); for (int i = 0; i < ELEMENTS; i++) temp = Array.BinarySearch(arr,i); sw.Stop(); Console.WriteLine($"Elapsed time for C# BinarySearch: {sw.ElapsedMilliseconds}ms"); } static int binarySearch(int[] arr, int i) { int low = 0, high = arr.Length - 1, mid; while (low <= high) { mid = (low+high) / 2; if (i < arr[mid]) high = mid - 1; else if (i > arr[mid]) low = mid + 1; else return mid; } return -1; } }

测试结果

+------------+--------------+--------------------+ | Attempt No | binarySearch | Array.BinarySearch | +------------+--------------+--------------------+ | 1 | 2700ms | 1099ms | | 2 | 2696ms | 1083ms | | 3 | 2675ms | 1077ms | | 4 | 2690ms | 1093ms | | 5 | 2700ms | 1086ms | +------------+--------------+--------------------+

推荐答案

在Visual Studio外部运行时，您的代码更快:

Your code is faster when run outside Visual Studio:

您与Array的对比:

From VS - Debug mode: 3248 vs 1113 From VS - Release mode: 2932 vs 1100 Running exe - Debug mode: 3152 vs 1104 Running exe - Release mode: 559 vs 1104

Array的代码可能已经在框架中进行了优化，但是比您的版本进行了更多的检查(例如，如果arr.Length大于int.MaxValue / 2，则您的版本可能会溢出)，并且如上所述种类繁多，而不仅仅是int[].

Array's code might be already optimized in the framework but also does a lot more checking than your version (for instance, your version may overflow if arr.Length is greater than int.MaxValue / 2) and, as already said, is designed for a wide range of types, not just int[].

因此，基本上，只有在调试代码时，它才会变慢，因为Array的代码始终在 release 中运行，并且幕后控制较少.

So, basically, it's slower only when you are debugging your code, because Array's code is always run in release and with less control behind the scenes.