Warum ist C# Array.BinarySearch so schnell?

Question

Ich habe implementiert nur ein sehr einfach binarysearch Algorithmus in C# für ganze Zahlen in einer Integer-Array zu finden:

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; 
} 

Beim Vergleich nach C# 's nativen Array.BinarySearch() kann ich sehen, dass Array.BinarySearch() ist mehr als doppelt so schnell als meine Funktion, jedes einzelne Mal.

MSDN auf Array.BinarySearch:

Suchen ein ganzes eindimensionales sortiertes Array für ein bestimmtes Element, die IComparable generische Schnittstelle von jedem Elemente des Arrays und von dem angegebenen Objekt implementiert.

Was macht diesen Ansatz so schnell?

Prüfregeln

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; 
    } 
} 

Testergebnisse

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

Answer 1

Ihr Code schneller ist, wenn sie außerhalb von Visual Studio ausgeführt:

Yours vs Array ist:

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 

Der Array-Code ist möglicherweise bereits im Framework optimiert, prüft aber auch wesentlich mehr als Ihre Version (z. B. ist Ihre Version möglicherweise übergelaufen, wenn arr.Length größer als ist) und ist, wie bereits erwähnt, für eine Vielzahl von Typen ausgelegt , nicht nur int[].

Also, es ist im Grunde nur langsamer, wenn Sie Ihren Code debuggen, weil Array-Code immer in Release und mit weniger Kontrolle hinter den Kulissen ausgeführt wird.