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

Question

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

现在,我想选择N%的点,其中存储的所有点的Z值最大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.

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如果存在关系,那将包括多个元素,正如您的实现现在所做的那样.

Answer 2

您可以使用 就地对列表进行排序List<T>.Sort，它使用快速排序算法。但是，当然，您的原始列表将被排序，这可能不是您想要的......

pointList.Sort((a, b) => b.Z.CompareTo(a.Z));
var selectedPoints = pointList.Take((int)(pointList.Count * N)).ToList();

如果您不介意对原始列表进行排序，这可能是内存使用和速度之间的最佳平衡