2

我有一个包含超过 1 亿个对象的二进制文件，我使用BinaryReader并返回（Yield）对象读取文件（文件阅读器和IEnumerable实现在这里：IEnumerable 的性能比较和源中每个项目的引发事件？）

对象的属性之一指示对象等级（如A5）。假设我想top n根据属性获取排序的对象。

我看到了OrderBy函数的代码：它使用 QuickSort 算法。我尝试将IEnumerable结果与OrderBy和Take(n)函数一起排序，但出现OutOfMemory异常，因为OrderBy函数创建了一个具有总对象数大小的数组来实现快速排序。

实际上，我需要的总内存是n所以没有必要创建一个大数组。例如，如果我得到 Take(1000) 它将只返回 1000 个对象，它不依赖于整个对象的总数。

如何使用函数获得函数的OrderBy结果Take？换句话说，我需要一个有限或阻塞的排序列表，其容量由最终用户定义。

4

2 回答 2

1

如果您希望使用默认 LINQ 运算符从有序源中获得前 N 个，那么唯一的选择是将所有项目加载到内存中，对它们进行排序并选择前 N 个结果：

items.Sort(condition).Take(N) // Out of memory

如果您只想对前 N 个项目进行排序，那么只需先获取项目，然后对它们进行排序：

items.Take(N).Sort(condition)

更新您可以使用缓冲区来保存 N 最大订购项目：

public static IEnumerable<T> TakeOrdered<T, TKey>(
    this IEnumerable<T> source, int count, Func<T, TKey> keySelector)
{
    Comparer<T, TKey> comparer = new Comparer<T,TKey>(keySelector);
    List<T> buffer = new List<T>();
    using (var iterator = source.GetEnumerator())
    {
        while (iterator.MoveNext())
        {
            T current = iterator.Current;
            if (buffer.Count == count)
            {
                // check if current item is less than minimal buffered item
                if (comparer.Compare(current, buffer[0]) <= 0)
                    continue;

                buffer.Remove(buffer[0]); // remove minimual item
            }
            // find index of current item
            int index = buffer.BinarySearch(current, comparer);
            buffer.Insert(index >= 0 ? index : ~index, current);
        }
    }

    return buffer;
}

此解决方案还对项目使用自定义比较器（通过键比较它们）：

public class Comparer<T, TKey> : IComparer<T>
{
    private readonly Func<T, TKey> _keySelector;
    private readonly Comparer<TKey> _comparer = Comparer<TKey>.Default;

    public Comparer(Func<T, TKey> keySelector)
    {
        _keySelector = keySelector;
    }

    public int Compare(T x, T y)
    {
        return _comparer.Compare(_keySelector(x), _keySelector(y));
    }
}

示例用法：

string[] items = { "b", "ab", "a", "abcd", "abc", "bcde", "b", "abc", "d" };
var top5byLength = items.TakeOrdered(5, s => s.Length);
var top3byValue = items.TakeOrdered(3, s => s);
于 2013-11-08T12:23:24.410 回答
1

LINQ 没有内置类，可以让您在n不将整个集合加载到内存的情况下获取顶级元素，但您绝对可以自己构建它。

一种简单的方法是使用SortedDictionaryof 列表：不断向其中添加元素，直到达到n. 之后，检查您将要添加的每个元素以及您目前找到的最小元素（即dict.Keys.First()）。如果新元素较小，则丢弃；否则，删除最小的元素，并添加一个新元素。

在循环结束时，您的排序字典将最多n包含元素，并且它们将根据您在字典上设置的比较器进行排序。

于 2013-11-08T12:25:03.933 回答