Last active
June 27, 2021 15:43
-
-
Save slavanap/739950702afdd5afc9295b75fd66ece7 to your computer and use it in GitHub Desktop.
List Extensions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
// * Summary * | |
BenchmarkDotNet=v0.13.0, OS=Windows 10.0.19042.1052 (20H2/October2020Update) | |
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores | |
.NET SDK=6.0.100-preview.4.21255.9 | |
[Host] : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT | |
DefaultJob : .NET 6.0.0 (6.0.21.25307), X64 RyuJIT | |
| Method | Mean | Error | StdDev | | |
|------------------ |------------:|----------:|----------:| | |
| WrapperArr | 58.19 ns | 0.954 ns | 0.796 ns | | |
| WrapperList | 56.58 ns | 1.151 ns | 0.898 ns | | |
| WrapperImmutable | 149.55 ns | 2.326 ns | 2.176 ns | | |
| ExplicitArr | 171.86 ns | 2.950 ns | 2.615 ns | | |
| ExplicitList | 1,925.37 ns | 30.796 ns | 27.300 ns | | |
| ExplicitImmutable | 2,468.93 ns | 37.708 ns | 35.272 ns | | |
| GeneralArr | 123.16 ns | 2.436 ns | 2.607 ns | | |
| GeneralList | 118.84 ns | 2.306 ns | 2.368 ns | | |
| GeneralImmutable | 517.53 ns | 10.105 ns | 9.452 ns | | |
// * Hints * | |
Outliers | |
Program.WrapperArr: Default -> 2 outliers were removed (67.58 ns, 68.52 ns) | |
Program.WrapperList: Default -> 3 outliers were removed (63.15 ns..71.78 ns) | |
Program.WrapperImmutable: Default -> 1 outlier was detected (146.24 ns) | |
Program.ExplicitArr: Default -> 1 outlier was removed (203.42 ns) | |
Program.ExplicitList: Default -> 1 outlier was removed, 2 outliers were detected (1.86 us, 1.99 us) | |
// * Legends * | |
Mean : Arithmetic mean of all measurements | |
Error : Half of 99.9% confidence interval | |
StdDev : Standard deviation of all measurements | |
1 ns : 1 Nanosecond (0.000000001 sec) | |
// ***** BenchmarkRunner: End ***** | |
// ** Remained 0 benchmark(s) to run ** | |
Run time: 00:02:24 (144.17 sec), executed benchmarks: 9 | |
Global total time: 00:02:28 (148.55 sec), executed benchmarks: 9 | |
*/ | |
using System; | |
using System.Collections.Generic; | |
using System.Collections.Immutable; | |
using System.Linq; | |
using BenchmarkDotNet.Attributes; | |
using BenchmarkDotNet.Running; | |
#nullable enable | |
namespace MyBenchmarks { | |
public class ListExtensions<T> { | |
public readonly IList<T> List; | |
public delegate int FBinarySearch(int index, int count, T value, IComparer<T>? comparer); | |
public readonly FBinarySearch BinarySearch; | |
public delegate void FRemoveRange(int index, int count); | |
public readonly FRemoveRange RemoveRange; | |
public ListExtensions(IList<T> list) { | |
List = list; | |
FBinarySearch? binarySearch = null; | |
if (list is Array arr) { | |
binarySearch = (index, count, value, cmp) => Array.BinarySearch(arr, index, count, value, cmp is null ? null : Comparer<T>.Create(cmp.Compare)); | |
} | |
else { | |
var func = list.GetType().GetMethod("BinarySearch", new Type[] { typeof(int), typeof(int), typeof(T), typeof(IComparer<T>) }); | |
if (func != null) | |
binarySearch = (FBinarySearch?)Delegate.CreateDelegate(typeof(FBinarySearch), list, func, throwOnBindFailure: false); | |
} | |
if (binarySearch == null) | |
binarySearch = (index, count, value, cmp) => GeneralBinarySearch(list, index, count, value, cmp); | |
BinarySearch = binarySearch; | |
FRemoveRange? removeRange = null; | |
{ | |
var func = list.GetType().GetMethod("RemoveRange", new Type[] { typeof(int), typeof(int) }); | |
if (func != null) | |
removeRange = (FRemoveRange?)Delegate.CreateDelegate(typeof(FRemoveRange), list, func, throwOnBindFailure: false); | |
} | |
if (removeRange == null) | |
removeRange = (index, count) => GeneralRemoveRange(list, index, count); | |
RemoveRange = removeRange; | |
} | |
public static int GeneralBinarySearch(IList<T> list, int index, int lenght, T value, IComparer<T>? comparer = null) { | |
comparer ??= Comparer<T>.Default; | |
int lower = index; | |
int upper = index + lenght - 1; | |
while (lower <= upper) { | |
int middle = lower + (upper - lower) / 2; | |
int comparisonResult = comparer.Compare(value, list[middle]); | |
if (comparisonResult == 0) | |
return middle; | |
else if (comparisonResult < 0) | |
upper = middle - 1; | |
else | |
lower = middle + 1; | |
} | |
return ~lower; | |
} | |
public static void GeneralRemoveRange(IList<T> list, int index, int count) { | |
while (count-- > 0) | |
list.RemoveAt(index + count); | |
} | |
} | |
public class Program { | |
const int NumElements = 100000; | |
readonly Random _rand = new(); | |
readonly int[] _arr = new int[NumElements]; | |
readonly List<int> _list; | |
readonly ImmutableList<int> _imm; | |
readonly ListExtensions<int> _extArr, _extList, _extImm; | |
readonly int _lookupValue; | |
public Program() { | |
for (int i = 0; i < NumElements; ++i) | |
_arr[i] = _rand.Next(); | |
Array.Sort(_arr); | |
_list = _arr.ToList(); | |
_imm = _arr.ToImmutableList(); | |
_extArr = new ListExtensions<int>(_arr); | |
_extList = new ListExtensions<int>(_list); | |
_extImm = new ListExtensions<int>(_imm); | |
_lookupValue = _arr[1]; | |
} | |
[Benchmark] public int WrapperArr() => _extArr.BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int WrapperList() => _extList.BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int WrapperImmutable() => _extImm.BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int ExplicitArr() => new ListExtensions<int>(_arr).BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int ExplicitList() => new ListExtensions<int>(_list).BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int ExplicitImmutable() => new ListExtensions<int>(_imm).BinarySearch(0, NumElements, _lookupValue, null); | |
[Benchmark] public int GeneralArr() => ListExtensions<int>.GeneralBinarySearch(_arr, 0, NumElements, _lookupValue, null); | |
[Benchmark] public int GeneralList() => ListExtensions<int>.GeneralBinarySearch(_list, 0, NumElements, _lookupValue, null); | |
[Benchmark] public int GeneralImmutable() => ListExtensions<int>.GeneralBinarySearch(_imm, 0, NumElements, _lookupValue, null); | |
public static void Main() => | |
BenchmarkRunner.Run<Program>(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment