Как избежать OrderBy - проблемы с использованием памяти

Ответ 1

Вы можете отсортировать список на месте, используя List<T>.Sort, который использует алгоритм Quicksort. Но, конечно, ваш первоначальный список будет отсортирован, что, возможно, не то, что вы хотите...

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

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

Ответ 2

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

Ответ 3

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

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

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

Несколько идей:

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

Ответ 4

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

Ответ 5

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

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();

Ответ 6

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

Чтобы улучшить время процессора, самое очевидное здесь - не использовать список. Вместо этого используйте IEnumerable. Вы делаете это, просто не вызывая .ToList() в конце вашего запроса. Это позволит структуре объединить все в одну итерацию списка, который работает только по мере необходимости. Это также улучшит использование вашей памяти, поскольку оно позволяет одновременно загружать весь запрос в память и вместо этого откладывает его на загрузку только одного элемента за раз по мере необходимости. Кроме того, используйте .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);

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

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

Update:

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

Ответ 7

Я бы сделал это, выполнив "половину" quicksort.

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

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

Разделение P на L = {y в P | y < x} и U = {y в P | x <= y}.

Если N = | U | то вы закончили.

Если N < | U | затем рекурсия с P: = U.

В противном случае вам нужно добавить некоторые элементы в U: recurse с 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, то N-й наибольший элемент в P находится где-то в [A, M). Попробуйте M: = (A + M)/2.

Если N < Q, то N-й наибольший элемент в P находится где-то в [M, Z]. Попробуйте M: = (M + Z)/2.

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

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

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

Ответ 8

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

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); 

Ответ 9

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

Ответ 10

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

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

Ответ 11

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

Просто попробовал с 50 000 строк и 100 раз обращался к 30% из них. Мои результаты:

• Сортировка с Linq: 5,3 секунды
• Использовать 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("????");
      }
   }