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

Question

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

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

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。

Answer 1

编写一个迭代列表一次并维护一组 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 个元素，就像您现在的实现一样。