Cómo evitar OrderBy - problemas de uso de memoria

Question

Supongamos que tenemos una larga lista de puntos List<Point> pointList (ya almacenados en la memoria) donde cada Point contiene coordenadas X, Y y Z.

Ahora, me gustaría seleccionar, por ejemplo, N% de puntos con los mayores valores Z de todos los puntos almacenados en pointList. En este momento lo estoy haciendo así:

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

Pero tengo aquí dos cuellos de botella en uso de memoria: por primera vez durante OrdenarPor (más importante) y segundo durante la selección de los puntos (esto es menos importante, ya que por lo general quieren seleccione solo una pequeña cantidad de puntos).

¿Hay alguna forma de reemplazar OrderBy (o tal vez otra forma de encontrar este punto de corte) con algo que utiliza menos memoria?

El problema es bastante importante, porque LINQ copia todo el conjunto de datos y para los archivos grandes que estoy procesando a veces alcanza unos pocos cientos de MB.

Answer 1

Puede ordenar la lista en su lugar, utilizando List<T>.Sort, que utiliza el algoritmo Quicksort. Pero, por supuesto, de su lista original sería solucionado, que tal vez no sea lo que quiere ...

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

Si no te importa la lista original sea clasificado, este es probablemente el mejor equilibrio entre el uso de memoria y velocidad

Answer 2

Si se combinan los dos hay una oportunidad se hará un poco menos de trabajo:

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

Pero básicamente este tipo de clasificación requiere la clasificación, su mayor costo.

algunas ideas más:

• si utiliza una clase de punto (en lugar de un punto struct) habrá mucho menos copiado.
• puede escribir una ordenación personalizada que solo molesta mover el 5% superior. Algo así como (no te rías) BubbleSort.

Answer 3

se usa algo como esto:

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

Answer 4

puede utilizar Indexed LINQ poner índice en los datos que se va a procesar. Esto puede resultar en mejoras notables en algunos casos.

Answer 5

Si desea un pequeño porcentaje de puntos ordenados por algún criterio, se lo servirá mejor utilizando una estructura de datos Priority queue; cree una cola de tamaño limitado (con el tamaño establecido para todos los elementos que desee) y luego simplemente explore la lista insertando cada elemento. Después del escaneo, puede extraer sus resultados en orden ordenado.
Esto tiene la ventaja de ser O(n log p) en lugar de O(n log n) donde p es el número de puntos que desea, y el costo de almacenamiento adicional también depende del tamaño de su salida en lugar de toda la lista.

Answer 6

Escriba un método que itere por la lista una vez y mantenga un conjunto de los M elementos más grandes. Cada paso solo requerirá el trabajo O (log M) para mantener el conjunto, y puede tener memoria O (M) y O (N log M) en tiempo de ejecución.

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

que incluirá más de count elementos si hay lazos, ya que su aplicación hace ahora.

Answer 7

Si su lista ya está en la memoria, la ordenaría en lugar de hacer una copia, a menos que la necesite sin clasificar nuevamente, es decir, en cuyo caso tendrá que pesar dos copias en la memoria vs carga de nuevo desde el almacenamiento):

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

Además, no está seguro de cuánto va a ayudar, pero parece como si se va a través de su lista dos veces - una vez para encontrar el valor de corte, y una vez más para seleccionar ellos. Supongo que está haciendo eso porque quiere dejar pasar todos los vínculos, incluso si eso significa seleccionar más del 5% de los puntos. Sin embargo, dado que ya están clasificados, puedes usar eso para tu beneficio y detenerte cuando hayas terminado.

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

Answer 8

A menos que su lista es muy grande, es mucho más probable para mí que el tiempo de CPU es el cuello de botella. Sí, es posible que tu OrderBy() use mucha memoria, pero en general es memoria que, en general, permanece inactiva. El tiempo de la CPU realmente es la mayor preocupación.

Para mejorar el tiempo de CPU, lo más obvio aquí es no usar una lista. Use un IEnumerable en su lugar. Para ello, simplemente no llame al .ToList() al final de su consulta. Esto permitirá que el marco combine todo en una iteración de la lista que se ejecuta solo según sea necesario. También mejorará el uso de la memoria, ya que evita cargar toda la consulta en la memoria de una vez, y en su lugar solo la espera para cargar un elemento a la vez según sea necesario. Además, use .Take() en lugar de .ElementAt(). Es mucho más eficiente.

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

que fuera del camino, hay tres casos en los que el uso de memoria en realidad podría ser un problema:

1. Su colección realmente es tan grande como para llenar la memoria. Para una estructura de puntos simple en un sistema moderno estamos hablando de millones de elementos. Esto es realmente poco probable. Si tiene un sistema tan grande, su solución es usar una base de datos relacional, que puede mantener estos elementos en el disco de manera relativamente eficiente.
2. Tiene una colección de tamaño moderado, pero tiene limitaciones de rendimiento externo, como la necesidad de compartir recursos del sistema con muchos otros procesos, como puede encontrar en un sitio web asp.net. En este caso, la respuesta es 1) poner nuevamente los puntos en una base de datos relacional o2) descargar el trabajo a las máquinas del cliente.
3. Su colección es lo suficientemente grande como para terminar en el Montículo de objetos grandes, y el HashSet utilizado en la llamada OrderBy() también se coloca en el LOH. Ahora lo que sucede es que el recolector de basura no compactará la memoria correctamente después de su llamada a OrderBy(), y con el tiempo obtendrá mucha memoria que no se usa pero que aún está reservada por su programa. En este caso, la solución es, desafortunadamente, dividir su colección en múltiples grupos, cada uno de los cuales es lo suficientemente pequeño como para no activar el uso de LOH.

Actualización:

lectura a través de su pregunta de nuevo, veo que estás leyendo archivos muy grandes. En ese caso, el mejor rendimiento de puede obtenerse escribiendo su propio código para analizar los archivos. Si el recuento de elementos se almacena cerca de la parte superior del archivo, puede hacer mucho mucho más, o incluso si puede estimar el número de registros en función del tamaño del archivo (adivinar un poco alto para estar seguro, y luego truncar cualquier extras después de terminar), puede construir su colección final como su lectura. Esto mejorará en gran medida el rendimiento de la CPU y el uso de la memoria.

Answer 9

Usted escribió, usted está trabajando con un DataSet. Si es así, puede usar DataView para ordenar sus datos una vez y usarlos para todos los futuros accesos a las filas.

Acabo de probar con 50,000 filas y 100 veces accediendo al 30% de ellas. Mis resultados de rendimiento son:

1. Ordenar Con LINQ: 5,3 segundos
2. Uso DataViews: 0.01 segundos

Darle una oportunidad.

[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

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

Ahora todo lo que tiene que hacer es poner en práctica un FixedSizedPriorityQueue que añade elementos de uno en uno y descarta el elemento más grande cuando está lleno.

Answer 11

Lo haría implementando "medio" un quicksort.

Considere su conjunto original de puntos, P, donde está buscando los elementos N "superiores" por coordenada Z.

Elija un pivote x en P.

partición P en L = {y en P | y < x} y U = {y en P | x < = y}.

If N = | U | entonces has terminado.

If N < | U | luego recurse con P: = U.

De lo contrario, debe agregar algunos elementos a U: recurse con N: = N - | U |, P: = L para agregar los elementos restantes.

Si elige su pivote sabiamente (por ejemplo, la mediana de, digamos, cinco muestras aleatorias), esto se ejecutará en el tiempo O (n log n).

Hmmmm, pensando un poco más, puede evitar crear conjuntos nuevos por completo, ya que básicamente solo busca una forma O (n log n) de encontrar el N ° elemento más grande del conjunto original. Sí, creo que esto funcionaría, así que aquí está la sugerencia número 2:

Realice un recorrido de P, encontrando los elementos menos y más grandes, A y Z, respectivamente.

Deje que M sea la media de A y Z (recuerde, solo estamos considerando las coordenadas Z aquí).

contar el número de elementos que hay en el rango [M, Z], llamar a este P.

Si Q < N, entonces el mayor número de ítems en P está en algún lugar [A, M) . Pruebe M: = (A + M)/2.

Si N < Q, entonces el N ° elemento más grande en P está en alguna parte en [M, Z]. Pruebe M: = (M + Z)/2.

Repetir hasta que nos encontramos con un M tal que Q = N.

P Ahora travesía, la eliminación de todos los elementos superior o igual a M.

Eso es definitivamente O (n log n) y no crea estructuras de datos adicionales (a excepción del resultado). Howzat?