Eficiencia de colecciones muy grandes; iteración y clasificación
Tengo un analizador csv que lee en más de 15 millones de filas (con muchos duplicados), y una vez analizado en estructuras, debe agregarse a una colección. Cada estructura tiene propiedades Clave (int), A(datetime) y B(int) (y otras que no son relevantes aquí).
Requisito A: La colección necesita imponer la unicidad mediante una Clave.
Requisito B: En un paso posterior, necesito la colección ordenada por propiedades A (marca de tiempo) entonces B (int).
Restricción: Las estructuras eventualmente necesitan ser recorridas en orden, una por una, con referencias a vecinos (una lista de enlaces presenta la solución más limpia aquí); el objetivo de esta operación es particionar el conjunto. Por favor, asuma que esto es lo más temprano que puede ocurrir la partición (es decir, no se puede particionar en la etapa de análisis).
He encontrado que el SortedSet funciona bastante bien para el requisito A, y es bastante performant, así, a pesar de que el O(log n) las inserciones son mucho más lentas que con HashSet<T>'s O (1), aunque no me importa ordenar la clave. 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 (a SortedSet<T> pasado a un método como IEnumerable<T>) toma una cantidad de tiempo prohibitiva (más de 20 minutos de molienda, todo en memoria, sin uso de archivos de página).
La pregunta: ¿Qué colección es la más adecuada para abordar este problema? Una idea es usar dos colecciones: una para imponer la unicidad (como un HashSet<int> o SortedSet<int> de claves), y una segunda SortedSet<T> para manejar la ordenación en la etapa de análisis (es decir, lo más arriba posible). Pero la aplicación ya consume mucha memoria, y las penalizaciones de rendimiento de necesitar el pagefile son prohibitivas.
¿Qué opciones me deja para una sola colección que haga cumplir ¿unicidad por una característica,pero clases por otras características no relacionadas? SortedSet<T> usa IComparer<T> (pero no tanto IComparer<T> como IEquitable<T>), por lo que si se basa en compareTo para hacer cumplir la unicidad, entonces no parece ajustarse a mis requisitos. ¿Es la subclase 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);
}
1 answers
Esto podría no ser una respuesta directa, pero : es una forma que he utilizado con éxito para un sistema similar de escala similar. Esto es para el "motor de etiquetas" que impulsa las listas de preguntas aquí en Stack Overflow; Esencialmente, tengo un:
struct Question {
// basic members - score, dates, id, etc - no text
}
Y básicamente un Question[] sobredimensionado (en realidad uso un Question* en memoria no administrada, pero eso es porque necesito poder compartirlo con algún código de GPU por razones no relacionadas). Rellenar los datos es simplemente sacar filas sucesivas en el Question[]. Estos datos nunca se ordenan - se dejan solos como los datos de origen-con solo anexar (nueva clave) o sobrescribir (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, yo por separado mantener un 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 pre-filtre esto, por lo que solo contiene las filas que quiero mantener - eliminando "eliminado", etc.).
Usando ya sea un modificador paralelo quicksort (ver http://stackoverflow.com/questions/1897458/parallel-sort-algorithm ) o una "ordenación introspectiva" modificada (como aquí) - así que al final de la ordenación, podría tener 0, 3, 1, 5, ....
Ahora: para iterar a través de los datos, simplemente iterar a través de la int[], y utilizar que como una búsqueda a la datos reales en el Question[]. Esto minimiza la cantidad de movimiento de datos durante una ordenación, y me permite mantener varias ordenaciones separadas (tal vez con diferentes pre-filtros) de manera muy eficiente. Solo se necesitan milisegundos para ordenar los datos de 15M (lo que sucede cada minuto más o menos para traer nuevas preguntas al Desbordamiento de la pila, o para anotar los cambios en las preguntas existentes).
Para hacer la ordenación lo más rápida posible, trato de escribir mi código de ordenación de tal manera que una ordenación compuesta pueda ser representada por un único valor entero, permitiendo una ordenación muy efectiva (utilizable por la ordenación introspectiva). Por ejemplo, aquí está el código para la clasificación "fecha de la última actividad, luego id de la 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, cambiando a la izquierda por 32 bits y componié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 "puntuación, luego puntuación 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 es 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 tipo, justo en un int[] y a ulong[], tales que ulong[] vector termina en el orden, y la int[] contiene los índices de los elementos a la vista.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-19 17:13:49