Dlaczego C# Array.BinarySearch jest tak szybki?

Question

Właśnie wdrożyliśmy bardzo prosty binarySearch algorytm w C# dla znalezienia liczb całkowitych w tablicy liczb całkowitych:

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    | 
+------------+--------------+--------------------+ 

Answer 1

Twój kod jest szybszy, gdy prowadzony poza Visual Studio:

Yours vs 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 

Kod Array może być już zoptymalizowany w ramach, ale sprawdza się znacznie więcej niż twoja wersja (na przykład twoja wersja może się przepełnić, jeśli arr.Length jest większa niż int.MaxValue/2) i, jak już wspomniano, jest przeznaczona dla szerokiej gamy typów , nie tylko int[].

Zasadniczo jest wolniejszy tylko podczas debugowania kodu, ponieważ kod Array jest zawsze uruchamiany w wydanie i mniej kontroli za kulisami.