Skip to content

Instantly share code, notes, and snippets.

@cameronism
Created February 27, 2019 01:48
Show Gist options
  • Save cameronism/b9aeb18e6602fcb6431245f6c00e570a to your computer and use it in GitHub Desktop.
Save cameronism/b9aeb18e6602fcb6431245f6c00e570a to your computer and use it in GitHub Desktop.
Take top n items from IEnumerable<> efficiently
public static IReadOnlyCollection<T> TakeDescending<T, TKey>(IEnumerable<T> source, Func<T, TKey> keySelector, int count)
where TKey : IComparable<TKey>
{
var index = 0;
var keys = new TKey[count];
var values = new T[count];
TKey min = default;
var minIndex = 0;
foreach (var item in source)
{
var key = keySelector(item);
if (index < keys.Length)
{
keys[index] = key;
values[index] = item;
if (index == 0)
{
min = key;
}
else
{
if (key.CompareTo(min) < 0)
{
min = key;
minIndex = index;
}
}
index++;
}
else if (key.CompareTo(min) > 0)
{
keys[minIndex] = key;
values[minIndex] = item;
// sequential search for new min
min = key;
for (var i = 0; i < keys.Length; i++)
{
if (keys[i].CompareTo(min) < 0)
{
min = keys[i];
minIndex = i;
}
}
}
}
if (index < values.Length)
{
Array.Resize(ref values, index);
}
return values;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment