为什么 C# Array.BinarySearch 这么快？

Question

我已经在 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() 比我的函数快 两倍多，每一次。

MSDN Array.BinarySearch:

Searches an entire one-dimensional sorted array for a specific element, using the IComparable generic interface implemented by each element of the Array and by the specified object.

是什么让这种方法如此之快？

测试代码

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

Answer 1

当运行在 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 的代码在发布中始终是运行，并且幕后控制较少。

为什么 C# Array.BinarySearch 这么快？

Why is C# Array.BinarySearch so fast?

c#

performance

search

icomparable

二进制搜索

测试代码

测试结果