我已经在C#中实现了一个非常简单的binarySearch实现,用于在整数数组中查找整数:
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()
是两倍以上的速度作为我的功能,每一次。
Array.BinarySearch上的MSDN :
使用Array的每个元素和指定对象实现的IComparable通用接口,在整个一维排序数组中搜索特定元素。
是什么使这种方法如此之快?
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外部运行时,您的代码会更快:
您与阵列的:
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的代码始终在发行版中运行,并且幕后控制较少。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句