Как избежать 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 копирует весь набор данных, а для больших файлов, которые я обрабатываю, иногда он достигает нескольких сотен МБ.

Answer 1

Вы можете использовать что-то вроде этого:

pointList.Sort(); // Use you own compare here if needed

// Skip OrderBy because the list is sorted (and not copied)
double cutoffValue = pointList.ElementAt((int) pointList.Length * (1 - N)).Z; 

// Skip ToList to avoid another copy of the list
IEnumerable<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue);