我已经在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 1104Array的代码可能已经在框架中进行了优化,但是比您的版本进行了更多的检查(例如,如果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.
更多推荐
为什么C#Array.BinarySearch这么快?
发布评论