Tại sao C# Array.BinarySearch quá nhanh?

Question

Tôi vừa thực hiện một rất đơn giản thuật toán binarySearch trong C# cho việc tìm kiếm số nguyên trong một mảng số nguyên:

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

Khi so sánh nó với C# 's mẹ đẻ Array.BinarySearch() Tôi có thể thấy rằng Array.BinarySearch() là nhanh hơn gấp hai lần làm chức năng của tôi, mỗi lần duy nhất.

MSDN trên Array.BinarySearch:

tìm kiếm một mảng được sắp xếp một chiều toàn bộ cho một yếu tố cụ thể, sử dụng giao diện chung IComparable thực hiện bởi mỗi phần tử của mảng và đối tượng quy định.

Điều gì làm cho cách tiếp cận này quá nhanh? kết quả

mã kiểm tra

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

thử nghiệm

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

Answer 1

Mã của bạn là nhanh hơn khi chạy bên ngoài Visual Studio:

Yours vs Array Avatar của:

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 

Mã của Array có thể đã được tối ưu hóa trong khung nhưng cũng kiểm tra nhiều hơn phiên bản của bạn (ví dụ, phiên bản của bạn có thể tràn nếu arr.Length lớn hơn int.MaxValue/2) và, như đã nói, được thiết kế cho nhiều loại , không chỉ int[].

Vì vậy, về cơ bản, nó chậm hơn chỉ khi bạn đang gỡ lỗi mã của bạn, bởi vì mã Array Avatar của luôn luôn chạy trong phát hành và có ít quyền kiểm soát đằng sau hậu trường.