c# - Eficiencia de colecciones muy grandes; iteración y clasificación

sorting sortedset

Question

Tengo un analizador csv que se lee en más de 15 millones de filas (con muchos duplicados), y una vez analizado en estructuras, es necesario agregarlo a una colección. Cada estructura tiene propiedades Key (int), A (datetime) y B (int) (y otras que no son relevantes aquí).

Requisito A: la colección necesita imponer la singularidad mediante una clave.

Requisito B: en un paso posterior, necesito la colección ordenada por las propiedades A (timestamp) y luego B (int).

Restricción: las estructuras eventualmente necesitan ser atravesadas en orden, una por una, con referencias a los vecinos (una LinkedList presenta la solución más limpia aquí); el objetivo de esta operación es dividir el conjunto. Supongamos que esta es la primera vez que puede producirse la partición (es decir, no puede ser particionada en la etapa de análisis sintáctico).

He descubierto que SortedSet funciona bastante bien para el Requisito A, y también es bastante eficiente, aunque las inserciones O (log n) son mucho más lentas que con HashSet<T> ''s O (1), aunque no lo hago No importa clasificar la llave. HashSet<T> se empantana cuando la colección se vuelve enorme, lo que aparentemente es un problema conocido, mientras que SortedSet<T> no sufre este inconveniente.

El problema: cuando llego al paso para el Requisito B, ordenar la colección (un SortedSet<T> pasado a un método como IEnumerable<T> ) toma una cantidad prohibitiva de tiempo (más de 20 minutos de molienda, todo en la memoria, sin uso de archivo de página).

La pregunta: ¿Qué colección (s) es (son) más adecuada para abordar este problema? Una idea es usar dos colecciones: una para imponer la singularidad (como un HashSet<int> u SortedSet<int> de claves), y un segundo SortedSet<T> para manejar la ordenación en la etapa de análisis (es decir, tan rápido como sea posible ) Pero la aplicación ya consume mucha memoria, y las penalizaciones de rendimiento de necesitar el archivo de paginación son prohibitivas.
¿Qué opciones me dejan para una única colección que impone la singularidad por una característica, pero ordena por otras características no relacionadas? SortedSet<T> usa IComparer<T> (pero no tanto IComparer<T> e IEquitable<T> ), por lo que si se basa en CompareTo para imponer la exclusividad, entonces no parece ajustarse a mis requisitos. Está subclasando SortedSet el camino a seguir?

Editar: el código de clasificación:

SortedSet<Dto> parsedSet = {stuff};
var sortedLinkedStructs = new LinkedList<Dto>(parsedSet.OrderBy(t => t.Timestamp).ThenBy(i => i.SomeInt));

La estructura

public readonly struct Dto: IEquatable<Dto>, IComparer<Dto>, IComparable<Dto>
{
     public readonly datetime Timestamp;
     public readonly int SomeInt;
     public readonly int Key;

     ctor(ts, int, key){assigned}

     public bool Equals(Dtoother) => this.Key == other.Key;
     public override int GetHashCode() => this.Key.GetHashCode();
     public int Compare(Dto x, Dto y) =>  x.Key.CompareTo(y.Key);
     public int CompareTo(Dto other) => this.Key.CompareTo(other.Key);
}

Answer 1

Puede que esta no sea una respuesta directa, pero es una forma que utilicé con éxito para un sistema similar de escala similar. Esto es para el "motor de etiquetas" que maneja las listas de preguntas aquí en ; Esencialmente, tengo un:

struct Question {
    // basic members - score, dates, id, etc - no text
}

y básicamente una Question[] gran tamaño Question[] (de hecho, uso una Question* en la memoria no administrada, pero eso se debe a que necesito poder compartirla con algún código de GPU por razones no relacionadas). Llenar los datos es solo sacar filas sucesivas en la Question[] . Esta información nunca se ordena, se deja solo como datos de origen, con solo agregar (nueva clave) o sobrescribir (la misma clave); en el peor de los casos , podríamos necesitar reasignar y bloquear-copiar los datos a una nueva matriz si alcanzamos la capacidad máxima.

Ahora, en lugar de ordenar esos datos, guardo por separado int[] (en realidad int* por la misma razón que antes, pero ... meh), donde cada valor en el int[] es el índice de los datos reales en el Question[] . Así que inicialmente puede ser 0, 1, 2, 3, 4, 5, ... (aunque prefiltro esto, entonces solo contiene las filas que quiero mantener - eliminando "borrado", etc.).

usando un quicksort modificador paralelo (ver http://.com/questions/1897458/parallel-sort-algorithm ) o un "tipo introspectivo" modificado (como here ) - así que al final del género, podría tener 0, 3, 1, 5, ...

Ahora: para iterar a través de los datos, simplemente recorro el int[] y lo uso como una búsqueda de los datos reales en la Question[] . Esto minimiza la cantidad de movimiento de datos durante una clasificación, y me permite mantener múltiples géneros separados (quizás con diferentes filtros previos) de manera muy eficiente. Solo se requieren milisegundos para ordenar los datos de 15M (lo que ocurre aproximadamente cada minuto para incluir nuevas preguntas en Desbordamiento de pila, o para observar cambios en las preguntas existentes).

Para hacer la clasificación lo más rápido posible, trato de escribir mi código de ordenación de modo que una ordenación compuesta se pueda representar mediante un solo valor entero, lo que permite un ordenamiento muy efectivo (utilizable por tipo introspectivo). Por ejemplo, aquí está el código para el tipo de "última fecha de actividad, luego ID de pregunta":

public override bool SupportsNaturallySortableUInt64 => true;
public override unsafe ulong GetNaturallySortableUInt64(Question* question)
{
    // compose the data (MSB) and ID (LSB)
    var val = Promote(question->LastActivityDate) << 32
        | Promote(question->Id);
    return ~val; // the same as ulong.MaxValue - val (which reverses order) but much cheaper
}

Esto funciona tratando el LastActivityDate como un entero de 32 bits, desplazándolo a la izquierda por 32 bits y formándolo con el Id como un entero de 32 bits, lo que significa que podemos comparar la fecha y el id en una sola operación.

O para "puntaje, luego puntaje de respuesta, luego id":

public override unsafe ulong GetNaturallySortableUInt64(Question* question)
{
    // compose the data
    var val = Promote(question->Score) << 48
        | Promote(question->AnswerScore) << 32
        | Promote(question->Id);
    return ~val; // the same as ulong.MaxValue - val (which reverses order) but much cheaper
}

Tenga en cuenta que GetNaturallySortableUInt64 solo se llama una vez por elemento, en un área de trabajo de un ulong[] (sí, en realidad un ulong* ) del mismo tamaño, por lo que inicialmente los dos espacios de trabajo son algo así como:

int[]    ulong[]
0        34243478238974
1        12319388173
2        2349245938453
...      ...

Ahora puedo hacer todo el género mirando solo a un int[] y un ulong[] , de modo que el vector ulong[] termine en el orden ordenado, y el int[] contiene los índices de los ítems a observar.