我有大约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));
    }
}

10-06 05:10
查看更多