Skip to content

Instantly share code, notes, and snippets.

@atifaziz
Last active November 17, 2023 17:43
Show Gist options
  • Save atifaziz/b72d4239145428638910aad8a19edb9c to your computer and use it in GitHub Desktop.
Save atifaziz/b72d4239145428638910aad8a19edb9c to your computer and use it in GitHub Desktop.
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup>
<OutputType>Exe</OutputType>
<TargetFrameworks>net8.0;net7.0;net6.0</TargetFrameworks>
<ImplicitUsings>enable</ImplicitUsings>
<Nullable>enable</Nullable>
</PropertyGroup>
<ItemGroup>
<PackageReference Include="BenchmarkDotNet" Version="0.13.10" />
<PackageReference Include="morelinq" Version="4.0.0" />
</ItemGroup>
</Project>
using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using MoreLinq;
BenchmarkRunner.Run<Benchmarks>();
[SimpleJob(RuntimeMoniker.Net60)]
[SimpleJob(RuntimeMoniker.Net70)]
[SimpleJob(RuntimeMoniker.Net80)]
[MemoryDiagnoser]
public class Benchmarks
{
readonly List<int> list = new();
[GlobalSetup]
public void Setup()
{
for (var i = 0; i < 15000; i++)
{
list.Add(i % 1000);
}
}
[Benchmark(Baseline = true)]
public void Duplicates_With_Two_HashSet()
{
foreach (var _ in list.Duplicates()) { }
}
[Benchmark]
public void Duplicates_With_Dictionary()
{
foreach (var _ in list.DuplicatesWithDictionary(null)) { }
}
[Benchmark]
public void Duplicates_Via_ScanBy()
{
foreach (var _ in list.ScanDuplicates(null)) { }
}
[Benchmark]
public void Duplicates_Using_Ref_Count()
{
foreach (var _ in list.DuplicatesWithRefCount(null)) { }
}
[Benchmark]
public void Duplicates_With_Opt_Count()
{
foreach (var _ in list.DuplicatesWithOptCount(null)) { }
}
}
static class MoreEnumerable
{
/// <summary>
/// Returns all duplicated elements of the given source.
/// </summary>
/// <param name="source">source sequence.</param>
/// <typeparam name="T">The type of the elements in the source sequence.</typeparam>
/// <returns>all elements that are duplicated.</returns>
public static IEnumerable<T> Duplicates<T>(this IEnumerable<T> source) => Duplicates(source, null);
/// <summary>
/// Returns all duplicated elements of the given source, using the specified element equality comparer
/// </summary>
/// <param name="source">source sequence.</param>
/// <param name="comparer">The equality comparer to use to determine whether or not keys are equal.
/// If null, the default equality comparer for <c>TSource</c> is used.</param>
/// <typeparam name="TSource">Type of the source sequence</typeparam>
/// <returns>all elements of the source sequence that are duplicated, based on the provided equality comparer</returns>
/// <exception cref="ArgumentNullException"><paramref name="source"/> is null.</exception>
public static IEnumerable<TSource> Duplicates<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
{
if (source is null) throw new ArgumentNullException(nameof(source));
return GetDuplicates();
IEnumerable<TSource> GetDuplicates()
{
var keySet = new HashSet<TSource>(comparer);
var yieldSet = new HashSet<TSource>(comparer);
foreach (var element in source)
{
if (!keySet.Add(element) && yieldSet.Add(element))
{
yield return element;
}
}
}
}
public static IEnumerable<TSource> ScanDuplicates<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
{
if (source is null) throw new ArgumentNullException(nameof(source));
return from e in source.ScanBy(static e => e,
static _ => 0,
static (count, _, _) => unchecked(Math.Min(count + 1, 3)),
comparer)
where e.Value is 2
select e.Key;
}
/// <summary>
/// Returns all duplicated elements of the given source, using the specified element equality comparer
/// </summary>
/// <param name="source">source sequence.</param>
/// <param name="comparer">The equality comparer to use to determine whether or not keys are equal.
/// If null, the default equality comparer for <c>TSource</c> is used.</param>
/// <typeparam name="TSource">Type of the source sequence</typeparam>
/// <returns>all elements of the source sequence that are duplicated, based on the provided equality comparer</returns>
/// <exception cref="ArgumentNullException"><paramref name="source"/> is null.</exception>
public static IEnumerable<TSource> DuplicatesWithDictionary<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
where TSource : notnull
{
if (source is null) throw new ArgumentNullException(nameof(source));
return GetDuplicates();
IEnumerable<TSource> GetDuplicates()
{
var counts = new Dictionary<TSource, int>(comparer);
foreach (var element in source)
{
if (!counts.TryGetValue(element, out var count))
count = 0;
if (count == 1)
yield return element;
counts[element] = count + 1;
}
}
}
public static IEnumerable<TSource> DuplicatesWithRefCount<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
where TSource : notnull
{
if (source is null) throw new ArgumentNullException(nameof(source));
return GetDuplicates();
IEnumerable<TSource> GetDuplicates()
{
var counts = new Dictionary<TSource, int>(comparer);
foreach (var element in source)
{
int CountElement()
{
ref var count = ref CollectionsMarshal.GetValueRefOrAddDefault(
counts,
element,
out var _);
return ++count;
}
if (CountElement() == 2)
yield return element;
}
}
}
public static IEnumerable<TSource> DuplicatesWithOptCount<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource>? comparer)
where TSource : notnull
{
if (source is null) throw new ArgumentNullException(nameof(source));
return GetDuplicates();
IEnumerable<TSource> GetDuplicates()
{
var counts = new Dictionary<TSource, int>(comparer);
foreach (var element in source)
{
if (counts.TryGetValue(element, out var count))
{
if (count == 1)
{
yield return element;
counts[element] = 2;
}
}
else
{
counts[element] = 1;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment