Как избежать 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

Напишите метод, который выполняет итерацию по списку один раз и поддерживает набор из 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();

Если вы не возражаете против сортировки исходного списка, возможно, это наилучший баланс между использованием памяти и скоростью

Answer 3

Я бы сделал это, реализовав "половину" быстрой сортировки.

Рассмотрим исходный набор точек P, где вы ищете «верхние» N элементов по координате Z.

Выберите ось x в P.

Разбиение P на L = {y в P | y

Если N = | U | тогда все готово.

Если N <| U | затем повторить с P: = U. </strong>

В противном случае вам нужно добавить некоторые элементы в U: рекурсивно с N: = N - | U |, P: = L, чтобы добавить оставшиеся элементы.

Если вы выберете свою ось с умом (например, медиана, скажем, пяти случайных выборок), то она будет выполняться за O (n log n) времени.

Хмммм, подумав немного, вы можете вообще избежать создания новых наборов, поскольку по сути вы просто ищете O (n log n) способ найти N-й величайший элемент из исходного набора. Да, я думаю, что это сработает, поэтому вот предложение № 2:

Сделайте обход P, найдя наименьший и наибольший предметы, A и Z, соответственно.

Пусть M - среднее значение A и Z (помните, мы рассматриваем здесь только координаты Z).

Подсчитайте, сколько предметов находится в диапазоне [M, Z], назовите это Q.

Если Q

Если N

Повторять до тех пор, пока мы не найдем M такой, что Q = N.

Теперь пройдитесь по P, удалив все предметы больше или равные M.

Это определенно O (n log n) и не создает никаких дополнительных структур данных (кроме результата). Howzat

Answer 4

Если ваш список не является чрезвычайно большим, для меня гораздо более вероятно, что время процессора является вашим узким местом в производительности. Да, ваш OrderBy() может использовать много памяти, но обычно это память, которая в большинстве случаев бездействует. Время процессора - это действительно большая проблема.

Чтобы увеличить время процессора, самое очевидное здесь - это не использовать список . Вместо этого используйте IEnumerable. Вы делаете это, просто не вызывая .ToList() в конце вашего запроса where. Это позволит каркасу объединить все в одну итерацию списка, который выполняется только по мере необходимости. Это также улучшит использование памяти, поскольку позволяет избежать загрузки всего запроса в память сразу, а вместо этого откладывает загрузку только одного элемента за раз по мере необходимости. Также используйте .Take() вместо .ElementAt(). Это намного эффективнее.

double N = 0.05; // selecting only 5% of points
int count = (1-N) * pointList.Count;
var selectedPoints = pointList.OrderBy(p=>p.Z).Take(count);

Кстати, в трех случаях использование памяти может быть проблемой:

1. Ваша коллекция действительно настолько велика, что заполняет память. Для простой структуры Point в современной системе мы говорим о миллионах предметов. Это действительно маловероятно. Если у вас такая большая система, вы можете использовать реляционную базу данных, которая может относительно эффективно хранить эти элементы на диске.
2. У вас небольшой размер коллекции, но существуют внешние ограничения производительности, такие как необходимость совместного использования системных ресурсов со многими другими процессами, которые вы можете найти на веб-сайте asp.net. В этом случае ответом будет либо 1) снова поместить точки в реляционную базу данных или 2) разгрузить работу на клиентские машины.
3. Ваша коллекция достаточно велика, чтобы оказаться в куче больших объектов, а HashSet, используемый в вызове OrderBy (), также помещается в LOH. Теперь происходит то, что сборщик мусора не будет правильно сжимать память после вашего вызова OrderBy (), и со временем вы получите много памяти, которая не используется, но все еще зарезервирована вашей программой. В этом случае, к сожалению, решение состоит в том, чтобы разбить вашу коллекцию на несколько групп, каждая из которых по отдельности достаточно мала, чтобы не вызывать использование LOH.

Обновление:

Читая ваш вопрос еще раз, я вижу, что вы читаете очень большие файлы. В этом случае производительность best может быть получена путем написания собственного кода для анализа файлов. Если количество элементов хранится в верхней части файла, вы можете сделать намного лучше, или даже если вы можете оценить количество записей в зависимости от размера файла (предположите, что немного больше, чтобы быть уверенным , а затем обрезать все дополнения после окончания), вы можете построить свою окончательную коллекцию как прочитанное. Это значительно улучшит производительность процессора и использование памяти.

Answer 5

Если ваш список уже находится в памяти, я бы отсортировал его вместо того, чтобы сделать копию - если вам не понадобится повторная сортировка, то есть, в этом случае вам придется взвешивать две копии в памяти и загрузка снова из хранилища):

pointList.Sort((x,y) => y.Z.CompareTo(x.Z)); //this should sort it in desc. order

Также не уверен, насколько это поможет, но похоже, что вы просматриваете свой список дважды - один раз, чтобы найти значение отсечки, и еще раз, чтобы выбрать их. Я предполагаю, что вы делаете это, потому что вы хотите пропустить все связи, даже если это означает выбор более 5% баллов. Однако, поскольку они уже отсортированы, вы можете использовать это в своих интересах и остановиться, когда закончите.

double cutoffValue = pointlist[(int) pointList.Length * (1 - N)].Z;
List<point> selectedPoints = pointlist.TakeWhile(p => p.Z >= cutoffValue)
                                      .ToList();

Answer 6

Вы можете использовать Indexed LINQ , чтобы поместить индекс в данные, которые вы обрабатываете.Это может привести к заметным улучшениям в некоторых случаях.

Answer 7

Если вы объедините два, есть шанс, что будет выполнено немного меньше работы:

List<Point> selectedPoints =  pointList
    .OrderByDescending(p=> p.Z) // First bottleneck - creates sorted copy of all data
    .Take((int) pointList.Count * N);

Но в основном этот вид рейтинга требует сортировки, вашей самой большой стоимости.

Еще несколько идей:

• если вы используете класс Point (вместо struct Point), копирование будет гораздо меньше.
• Вы могли бы написать пользовательскую сортировку, которая беспокоит только перемещение верхних 5%. Что-то вроде (не смейтесь) BubbleSort.

Answer 8

int resultSize = pointList.Count * (1-N);
FixedSizedPriorityQueue<Point> q =
  new FixedSizedPriorityQueue<Point>(resultSize, p => p.Z);
q.AddEach(pointList);
List<Point> selectedPoints = q.ToList();

Теперь все, что вам нужно сделать, это реализовать FixedSizedPriorityQueue, который добавляет элементы по одному и отбрасывает самый большой элемент, когда он заполнен.

Answer 9

Вы написали, вы работаете с DataSet.Если это так, вы можете использовать DataView, чтобы отсортировать данные один раз и использовать их для всех будущих обращений к строкам.

Только что попробовал 50000 строк и 100 раз обращался к 30% из них.Мои результаты производительности:

1. Сортировка с помощью Linq: 5,3 секунды
2. Использование DataViews: 0,01 секунды

Попробуйте.

   [TestClass]
   public class UnitTest1 {
      class MyTable : TypedTableBase<MyRow> {
         public MyTable() {
            Columns.Add("Col1", typeof(int));
            Columns.Add("Col2", typeof(int));
         }

         protected override DataRow NewRowFromBuilder(DataRowBuilder builder) {
            return new MyRow(builder);
         }
      }

      class MyRow : DataRow {
         public MyRow(DataRowBuilder builder) : base(builder) {
         }

         public int Col1 { get { return (int)this["Col1"]; } }
         public int Col2 { get { return (int)this["Col2"]; } }
      }

      DataView _viewCol1Asc;
      DataView _viewCol2Desc;
      MyTable _table;
      int _countToTake;

      [TestMethod]
      public void MyTestMethod() {
         _table = new MyTable();


         int count = 50000;
         for (int i = 0; i < count; i++) {
            _table.Rows.Add(i, i);
         }

         _countToTake = _table.Rows.Count / 30;
         Console.WriteLine("SortWithLinq");
         RunTest(SortWithLinq);
         Console.WriteLine("Use DataViews");
         RunTest(UseSoredDataViews);
      }

      private void RunTest(Action method) {
         int iterations = 100;
         Stopwatch watch = Stopwatch.StartNew();
         for (int i = 0; i < iterations; i++) {
            method();
         }
         watch.Stop();
         Console.WriteLine("   {0}", watch.Elapsed);
      }

      private void UseSoredDataViews() {
         if (_viewCol1Asc == null) {
            _viewCol1Asc = new DataView(_table, null, "Col1 ASC", DataViewRowState.Unchanged);
            _viewCol2Desc = new DataView(_table, null, "Col2 DESC", DataViewRowState.Unchanged);
         }

         var rows = _viewCol1Asc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row);
         IterateRows(rows);
         rows = _viewCol2Desc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row);
         IterateRows(rows);
      }

      private void SortWithLinq() {
         var rows = _table.OrderBy(row => row.Col1).Take(_countToTake);
         IterateRows(rows);
         rows = _table.OrderByDescending(row => row.Col2).Take(_countToTake);
         IterateRows(rows);
      }

      private void IterateRows(IEnumerable<MyRow> rows) {
         foreach (var row in rows)
            if (row == null)
               throw new Exception("????");
      }
   }

Answer 10

Если вам нужен небольшой процент точек, упорядоченных по какому-либо критерию, вам лучше будет использовать структуру данных Priority queue ;создайте очередь с ограниченным размером (с размером, установленным на любое количество элементов), а затем просто просмотрите список, вставляя каждый элемент.После сканирования вы можете извлекать результаты в отсортированном порядке.
Преимущество этого параметра в том, что O(n log p) вместо O(n log n), где p - это количество баллов, которое вы хотите, и дополнительная стоимость хранениязависит от вашего размера вывода вместо всего списка.