JonasH已经发布了关于这个问题的实际答案。
但我对比使用Distinct()
或者线性搜索,想知道二分查找法是否更快(如果更快的话)。
这是我用来进行基准测试的代码:
using System;
using System.Linq;
using BenchmarkDotNet.Attributes;
namespace ConsoleApp1;
public class UnderTest
{
public UnderTest()
{
const int NUM_VALUES = 1_000_000;
const double PROBABLILITY_OF_CHANGE = 0.00001;
_data = new int[NUM_VALUES];
var rng = new Random(98891);
for (int value = 0, i = 0; i < NUM_VALUES; ++i)
{
_data[i] = value;
if (rng.NextDouble() <= PROBABLILITY_OF_CHANGE)
++value;
}
Console.WriteLine(usingBinarySearch(_data));
Console.WriteLine(usingDistinct (_data));
Console.WriteLine(usingLinearSearch(_data));
}
[Benchmark]
public void UsingBinarySearch()
{
usingBinarySearch(_data);
}
[Benchmark]
public void UsingDistinct()
{
usingDistinct(_data);
}
[Benchmark]
public void UsingLinearSearch()
{
usingLinearSearch(_data);
}
static int usingBinarySearch(int[] a)
{
int i = 0;
int count = 0;
while (i < a.Length)
{
i = nextIndex(a, i, a[i]);
count++;
}
return count;
}
static int nextIndex(int[] a, int l, int target)
{
int r = a.Length - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (a[mid] == target) l = mid + 1;
else r = mid - 1;
}
return r + 1;
}
static int usingDistinct(int[] a)
{
return a.Distinct().Count();
}
static int usingLinearSearch(int[] a)
{
int count = 1;
for (int i = 1; i < a.Length; i++)
{
count += a[i - 1] != a[i] ? 1 : 0;
}
return count;
}
readonly int[] _data;
}
在第一次测试中,我提供了一些数据,期望二分查找的速度明显更快:一个包含100万个整数的数组,每个元素值大于前一个元素的概率为0.00001
(PROBABLILITY_OF_CHANGE = 0.00001
)。
使用一个固定种子为98891
的随机数生成器,结果数组中只有7个不同的值,得出以下计时结果(使用.NET 6.0):
| Method | Mean | Error | StdDev |
|------------------ |---------------:|--------------:|--------------:|
| UsingBinarySearch | 251.0 ns | 4.93 ns | 12.64 ns |
| UsingDistinct | 9,341,067.8 ns | 185,888.76 ns | 294,839.27 ns |
| UsingLinearSearch | 1,607,222.2 ns | 51,565.50 ns | 146,282.75 ns |
在这种情况下,二分搜索的速度比线性搜索快得多。值得注意的是,与线性搜索相比,
Distinct()
非常慢。
但需要注意的是,这并不是一个公平的比较,因为
Distinct()
可以用于未排序的数据,而其他两个算法需要排序后才能使用。如果您有未排序的数据,则为其他算法排序的开销会使
Distinct()
成为更好的选择。这样的比较留给读者作为谚语式的练习...
现在让我们尝试使用
PROBABLILITY_OF_CHANGE = 0.001
(结果为919个不同的元素):
| Method | Mean | Error | StdDev |
|------------------ |------------:|-----------:|-----------:|
| UsingBinarySearch | 93.08 us | 1.787 us | 4.831 us |
| UsingDistinct | 9,944.12 us | 197.825 us | 356.718 us |
| UsingLinearSearch | 1,503.85 us | 28.239 us | 63.740 us |
二分搜索仍然显著更快。
现在,PROBABLILITY_OF_CHANGE = 0.1
(结果有100,058个不同的元素):
| Method | Mean | Error | StdDev |
|------------------ |----------:|----------:|----------:|
| UsingBinarySearch | 5.541 ms | 0.1096 ms | 0.1347 ms |
| UsingDistinct | 14.331 ms | 0.5516 ms | 1.6091 ms |
| UsingLinearSearch | 2.319 ms | 0.0422 ms | 0.0782 ms |
现在线性搜索比二分搜索更快。
这表明,Distinct()
不是解决此问题的好方法 - 线性搜索始终更好(主要是因为数据已经排序 - 如果没有排序,我们就必须对其进行排序,这将显着改变其他算法的时间)。
只有在不同值的数量相对于容器大小较低时,使用二分搜索才值得。
(请注意,这些运行由 Benchmark.Net 输出的不同单位 - ns、us 和 ms。我意识到后来我忘记了指定单位,所以它们被自动缩放到运行中最快的基准测试...)