我有大约30kk元素的集合trends
。当我尝试在linqpad中执行以下代码
trends.Take(count).Dump();
它工作正常。
但是,如果我添加排序:
trends.OrderByDescending(x => x.Item2).Take(count).Dump();
我得到System.OutOfMemoryException
我做错了什么?
最佳答案
这是另一种扩展方法,可能比原始的LINQ更好(例如,对于少数选定的项目,它不应该炸掉)。像L.B.的解决方案一样,它应该是O(n),并且不能将所有项目都保留在内存中:
public static class Enumerables
{
public static IEnumerable<T> TopN<T, TV>(this IEnumerable<T> value, Func<T, TV> selector, Int32 count, IComparer<TV> comparer)
{
var qCount = 0;
var queue = new SortedList<TV, List<T>>(count, comparer);
foreach (var val in value)
{
var currTv = selector(val);
if (qCount >= count && comparer.Compare(currTv, queue.Keys[0]) <= 0) continue;
if (qCount == count)
{
var list = queue.Values[0];
if (list.Count == 1)
queue.RemoveAt(0);
else
list.RemoveAt(0);
qCount--;
}
if (queue.ContainsKey(currTv))
queue[currTv].Add(val);
else
queue.Add(currTv, new List<T> {val});
qCount++;
}
return queue.SelectMany(kvp => kvp.Value);
}
public static IEnumerable<T> TopN<T, TV>(this IEnumerable<T> value, Func<T, TV> selector, Int32 count)
{
return value.TopN(selector, count, Comparer<TV>.Default);
}
public static IEnumerable<T> BottomN<T, TV>(this IEnumerable<T> value, Func<T, TV> selector, Int32 count, IComparer<TV> comparer)
{
return value.TopN(selector, count, new ReverseComparer<TV>(comparer));
}
public static IEnumerable<T> BottomN<T, TV>(this IEnumerable<T> value, Func<T, TV> selector, Int32 count)
{
return value.BottomN(selector, count, Comparer<TV>.Default);
}
}
// Helper class
public class ReverseComparer<T> : IComparer<T>
{
private readonly IComparer<T> _comparer;
public int Compare(T x, T y)
{
return -1*_comparer.Compare(x, y);
}
public ReverseComparer()
: this(Comparer<T>.Default)
{ }
public ReverseComparer(IComparer<T> comparer)
{
if (comparer == null) throw new ArgumentNullException("comparer");
_comparer = comparer;
}
}
和一些测试:
[TestFixture]
public class EnumerablesTests
{
[Test]
public void TestTopN()
{
var input = new[] { 1, 2, 8, 3, 6 };
var output = input.TopN(n => n, 3).ToList();
Assert.AreEqual(3, output.Count);
Assert.IsTrue(output.Contains(8));
Assert.IsTrue(output.Contains(6));
Assert.IsTrue(output.Contains(3));
}
[Test]
public void TestBottomN()
{
var input = new[] { 1, 2, 8, 3, 6 };
var output = input.BottomN(n => n, 3).ToList();
Assert.AreEqual(3, output.Count);
Assert.IsTrue(output.Contains(1));
Assert.IsTrue(output.Contains(2));
Assert.IsTrue(output.Contains(3));
}
[Test]
public void TestTopNDupes()
{
var input = new[] { 1, 2, 8, 8, 3, 6 };
var output = input.TopN(n => n, 3).ToList();
Assert.AreEqual(3, output.Count);
Assert.IsTrue(output.Contains(8));
Assert.IsTrue(output.Contains(6));
Assert.IsFalse(output.Contains(3));
}
[Test]
public void TestBottomNDupes()
{
var input = new[] { 1, 1, 2, 8, 3, 6 };
var output = input.BottomN(n => n, 3).ToList();
Assert.AreEqual(3, output.Count);
Assert.IsTrue(output.Contains(1));
Assert.IsTrue(output.Contains(2));
Assert.IsFalse(output.Contains(3));
}
}