如何避免 OrderBy - 内存使用问题

假设我们有一个很大的点列表List<Point> pointList（已存储在内存中）其中每个Point包含 X、Y 和 Z 坐标。

现在，我想选择存储在中的所有点中具有最大 Z 值的 N% 点pointList。现在我正在这样做：

N = 0.05; // selecting only 5% of points
double cutoffValue = pointList
    .OrderBy(p=> p.Z) // First bottleneck - creates sorted copy of all data
    .ElementAt((int) pointList.Count * (1 - N)).Z;

List<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue).ToList();

但我这里有两个内存使用瓶颈：第一个是在 OrderBy 期间（更重要），第二个是在选择点期间（这不太重要，因为我们通常只想选择少量的点）。

有没有什么方法可以用使用更少内存的东西替换 OrderBy （或者可能是找到这个截止点的其他方法）？

这个问题非常重要，因为 LINQ 复制整个数据集，对于我正在处理的大文件，有时会达到数百 MB。

编写一个方法，迭代列表一次并维护一组 M 个最大元素。每个步骤只需要 O(log M) 工作来维护集合，并且您可以拥有 O(M) 内存和 O(N log M) 运行时间。

public static IEnumerable<TSource> TakeLargest<TSource, TKey>
    (this IEnumerable<TSource> items, Func<TSource, TKey> selector, int count)
{
    var set = new SortedDictionary<TKey, List<TSource>>();
    var resultCount = 0;
    var first = default(KeyValuePair<TKey, List<TSource>>);
    foreach (var item in items)
    {
        // If the key is already smaller than the smallest
        // item in the set, we can ignore this item
        var key = selector(item);
        if (first.Value == null ||
            resultCount < count ||
            Comparer<TKey>.Default.Compare(key, first.Key) >= 0)
        {
            // Add next item to set
            if (!set.ContainsKey(key))
            {
                set[key] = new List<TSource>();
            }
            set[key].Add(item);
            if (first.Value == null)
            {
                first = set.First();
            }

            // Remove smallest item from set
            resultCount++;
            if (resultCount - first.Value.Count >= count)
            {
                set.Remove(first.Key);
                resultCount -= first.Value.Count;
                first = set.First();
            }
        }
    }
    return set.Values.SelectMany(values => values);
}

这将包括超过count元素（如果存在联系），就像您现在的实现一样。