Właśnie wdrożyliśmy bardzo prosty binarySearch algorytm w C# dla znalezienia liczb całkowitych w tablicy liczb całkowitych:Dlaczego C# Array.BinarySearch jest tak szybki?
Binary Search
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;
}
Porównując go do C# 's natywny Array.BinarySearch()
widzę, że Array.BinarySearch()
jest więcej niż dwa razy szybsze jako moja funkcja, za każdym razem.
MSDN Array.BinarySearch:
przeszukuje całą jednowymiarowy posortowanej tablicy dla określonego elementu, wykorzystując IComparable ogólnego interfejsu realizowany przez każdy element tablicy i określonego obiektu.
Co sprawia, że takie podejście jest tak szybkie?
kod testowy
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;
}
}
Wyniki testów
+------------+--------------+--------------------+
| Attempt No | binarySearch | Array.BinarySearch |
+------------+--------------+--------------------+
| 1 | 2700ms | 1099ms |
| 2 | 2696ms | 1083ms |
| 3 | 2675ms | 1077ms |
| 4 | 2690ms | 1093ms |
| 5 | 2700ms | 1086ms |
+------------+--------------+--------------------+
Możesz [przyjrzeć się] (http://referencesource.microsoft.com/#mscorlib/system/array.cs,b92d187c91d4c9a9) u źródła wskazówek. – Blorgbeard
Czy wykonałeś test w wersji Release poza VS? –
Po prostu zrobiłem, a na mojej maszynie twoje 'binarySearch' jest około 2,5 razy ** szybsze ** niż' tablica'. –