Efficacité des très grandes collections; itération et tri

Question

J'ai un fichier csv analyseur qui lit dans+ de 15 millions de lignes (avec de nombreux doublons), et une fois analysée dans les structures, doivent être ajoutés à la collection. Chaque structure a des propriétés de Clé (int), Un(datetime), et B(int) (et d'autres qui ne sont pas pertinentes ici).

Exigence: La collecte des besoins pour renforcer l'unicité par une Clé.

Condition B: Dans une étape ultérieure, j'ai besoin de la collection triés par les propriétés d'Un(timestamp) alors B(int).

Contrainte: Les structures éventuellement besoin d'être parcourus dans l'ordre, un par un, avec des références à des voisins (une LinkedList présente la solution la plus propre ici); le but de cette opération est de partitionner l'ensemble. Veuillez supposer que c'est le plus ancien que le partitionnement peut se produire (c'est à dire, il ne peut pas être partitionné à l'analyse de la scène).

J'ai trouvé que la SortedSet fonctionne très bien pour un besoin d'Un, et c'est assez performant ainsi, même si l'O(log n) insertions sont beaucoup plus lentement qu'avec HashSet<T>s'O(1), bien que je ne se soucient pas de tri sur la touche. HashSet<T> s'enlise lors de la collecte obtient un énorme, qui, apparemment, est un problème connu, tandis que l' SortedSet<T> ne souffre pas de cet inconvénient.

Le problème: Quand j'arrive à l'étape de l'Exigence B, le tri de la collection ( SortedSet<T> passés à une méthode qu' IEnumerable<T>) prend un montant prohibitif de temps (+de 20 minutes de broyage, tous en mémoire, pas d'utilisation de fichier de page).

La question: quel(s) est(sont) le mieux adapté pour résoudre ce problème? Une idée est d'utiliser deux collections: l'une pour renforcer l'unicité (comme un HashSet<int> ou SortedSet<int> de clés), et un second SortedSet<T> pour gérer le tri à l'analyse de la scène (c'est à dire, le plus en amont possible). Mais l'application est déjà beaucoup de mémoire, et de l'exécution des peines d'avoir besoin du fichier d'échange est prohibitif.
Quelles sont les options qui me laissent pour une collection unique qui assure l'unicité par une caractéristique, mais trie par d'autres sans rapport avec les caractéristiques? SortedSet<T> utilise IComparer<T> (mais pas les deux IComparer<T> et IEquitable<T>), de sorte que si elle s'appuie sur CompareTo pour renforcer l'unicité, alors il ne semble pas pour l'adapter à mes besoins. Est-classement SortedSet le chemin à parcourir?

Edit: Le code de tri:

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

La structure:

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

Ce ne serait pas une réponse directe, mais : c'est un moyen que j'ai utilisé avec succès pour un système similaire d'ampleur similaire. C'est pour le "tag moteur qui entraîne les listes de question, ici, sur un Débordement de Pile; en gros, j'ai un:

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

et , fondamentalement, d'une immense Question[] (en fait j'utilise un Question* dans une mémoire non managée, mais c'est parce que j'ai besoin d'être en mesure de partager avec certains de code GPU pour des raisons non liées). Le remplissage de données est juste prendre les lignes successives de l' Question[]. Ces données n'est jamais trié - il est laissé seul en tant que source de données avec juste append (nouvelles clés) ou remplacer (même clé); au pire, nous pourrions avoir besoin de réaffecter et bloc-copier les données sur un nouveau tableau si nous atteignons la capacité max.

Maintenant, au lieu de trier les données, je séparément garder un int[] (en fait, int* pour la même raison que précédemment, mais... meh), où chaque valeur en int[] est l' indice de la réelle des données dans l' Question[]. Donc, au départ, il peut être 0, 1, 2, 3, 4, 5, ... (bien que je l'ai pré-filtre, de sorte qu'il ne contient que les lignes je tiens à garder - retrait "supprimé", etc).

en utilisant soit un modificateur parallèle quicksort (voir http://stackoverflow.com/questions/1897458/parallel-sort-algorithm) ou une version modifiée de "introspective de tri" (comme ici) - donc, à la fin de la sorte, j'aurais 0, 3, 1, 5, ....

Maintenant: pour itérer sur les données, je viens de parcourir l' int[], et de l'utiliser comme une recherche de la réelle des données dans l' Question[]. Cela réduit la quantité de mouvement de données lors d'un tri, et me permet de conserver plusieurs sortes distinctes (peut-être avec différents pré-filtres) de manière très efficace. Il ne prend que quelques millisecondes seulement pour trier les 15M de données (ce qui arrive chaque minute ou deux afin de mettre en place de nouvelles questions dans un Débordement de Pile ou de noter les changements apportés à certaines questions).

Pour faire le tri aussi vite que possible, j'essaie d'écrire mon code tel qu'un composite tri peut être représenté par une unique valeur d'entier, permettant très efficace de tri (utilisable par l'introspection de tri). Pour exemple, voici le code pour la "dernière date de l'activité, puis la question de l'id de" trier:

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
}

Cela fonctionne par le traitement de l' LastActivityDate comme un entier de 32 bits, à gauche décalage de 32 bits et de la composer avec l' Id comme un entier de 32 bits, ce qui signifie que nous pouvons comparer la date et l'id en une seule opération.

Ou pour "le score, puis répondre à score, puis 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
}

Notez que GetNaturallySortableUInt64 n'est appelée qu'une fois par élément dans une zone de travail d'un ulong[] (oui, en fait, un ulong*) de la même taille, donc, au départ, les deux espaces de travail sont quelque chose comme:

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

Maintenant, je peux faire toute sorte juste à un int[] et ulong[], de telle sorte que l' ulong[] vecteur finit dans l'ordre de tri, et l' int[] contient les indices des éléments à regarder.