c# - 大きなコレクションとOrderByを使用したOutOfMemoryException？

Question

trends私は約30kkの要素を持つコレクションを持っています。linqpadで次のコードを実行しようとしているとき

trends.Take(count).Dump();

それは大丈夫です。

しかし、並べ替えを追加すると、次のようになります。

 trends.OrderByDescending(x => x.Item2).Take(count).Dump();

System.OutOfMemoryExceptionが発生します

私は何を間違っていますか？

Answer 1

OrderByDescending（またはOrderBy）最初の要素をフェッチしようとすると、シーケンス全体が具体化されます。そうしないと、最初の要素を知ることができない可能性があります。並べ替えるには、シーケンスのコピー（通常はもちろん参照の束）を作成する必要があるため、元のシーケンスがメモリ内のコレクションである場合は、2つのコピーになります。おそらく、そのための十分なメモリがありません。

Answer 2

コレクション全体をソートする必要はありません。コレクションcountから上位の要素を取得するだけです。このhttps://codereview.stackexchange.com/a/9777/11651の解決策は次のとおりです。

この回答の要点はIt doesn't require all items to be kept in memory(for sorting)

リンクの回答のコメントから再び：

アイデアは次のとおりです。リストの最大（または最小）アイテムをO（n）時間で見つけることができます。このアイデアを m アイテム (問題では 5) に拡張すると、リストを並べ替えるよりも上位 (または下位) の m アイテムを高速に取得できます (リストの 1 回のパス + 並べ替えられた 5 つのアイテムを維持するコスト)。

Answer 3

元の LINQ よりもうまく機能する可能性のある別の拡張方法を次に示します (たとえば、少数の選択されたアイテムに対して爆発しないようにする必要があります)。LB のソリューションと同様に、それは 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));
    }
}