Skip to content

Instantly share code, notes, and snippets.

@ptupitsyn
Created June 20, 2021 11:03
Show Gist options
  • Save ptupitsyn/71eefbdb607ce3f9ddfae2f5e099184e to your computer and use it in GitHub Desktop.
Save ptupitsyn/71eefbdb607ce3f9ddfae2f5e099184e to your computer and use it in GitHub Desktop.
.NET SortedDictionary vs OrderBy vs List.Sort
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
namespace SortedDictPerf
{
/// <summary>
/// | Method | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
/// |------------ |---------:|---------:|---------:|-------:|------:|------:|----------:|
/// | Dict | 361.7 ns | 7.07 ns | 7.26 ns | 0.1554 | - | - | 488 B |
/// | DictOrderBy | 499.9 ns | 9.66 ns | 9.04 ns | 0.2651 | - | - | 832 B |
/// | SortedDict | 943.7 ns | 18.26 ns | 22.42 ns | 0.2241 | - | - | 704 B |
/// </summary>
[MemoryDiagnoser]
public class Program
{
private static readonly List<(int Price, int Quantity)> Data = new()
{
(1, 2),
(1, 3),
(1, 4),
(2, 4),
(2, 2),
(3, 5),
(7, 5),
(8, 5),
(9, 5),
(9, 15)
};
static void Main()
{
BenchmarkRunner.Run<Program>();
}
[Benchmark]
public List<KeyValuePair<int, int>> Dict()
{
var result = new Dictionary<int, int>();
foreach (var entry in Data)
{
if (result.TryGetValue(entry.Price, out var res))
{
result[entry.Price] = res + entry.Quantity;
}
else
{
result[entry.Price] = entry.Quantity;
}
}
var list = result.ToList();
list.Sort((x, y) => x.Key - y.Key);
return list;
}
[Benchmark]
public List<KeyValuePair<int, int>> DictOrderBy()
{
var result = new Dictionary<int, int>();
foreach (var entry in Data)
{
if (result.TryGetValue(entry.Price, out var res))
{
result[entry.Price] = res + entry.Quantity;
}
else
{
result[entry.Price] = entry.Quantity;
}
}
return result.OrderBy(x => x.Key).ToList();
}
[Benchmark]
public List<KeyValuePair<int, int>> SortedDict()
{
var result = new SortedDictionary<int, int>();
foreach (var entry in Data)
{
if (result.TryGetValue(entry.Price, out var res))
{
result[entry.Price] = res + entry.Quantity;
}
else
{
result[entry.Price] = entry.Quantity;
}
}
return result.ToList();
}
}
}
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFramework>net5.0</TargetFramework>
</PropertyGroup>
<ItemGroup>
<PackageReference Include="BenchmarkDotNet" Version="0.13.0" />
</ItemGroup>
</Project>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment