IDK si le sorting externe avec fusion par comptage des doublons a été étudié. J’ai trouvé un article de 1983 (voir ci-dessous). Habituellement, les algorithmes de sorting sont conçus et étudiés en supposant que les objects sont sortingés par clé, de sorte que les clés en double ont des objects différents. Il existe peut-être de la littérature sur ce sujet, mais c’est un problème très intéressant. Il s’agit probablement d’une application de dictionnaires compacts combinée à un sorting par fusion externe.

Dictionnaires efficaces pour stocker de grandes quantités de chaînes dans peu de mémoire est un problème très bien étudié. La plupart des structures de données utiles peuvent inclure des données auxiliaires pour chaque mot (dans notre cas, un nombre de doublons).

---

TL: DR résumé des idées utiles, car je me suis beaucoup trop détaillé sur beaucoup de choses dans le corps de cette réponse:

• Limites de lot lorsque la taille de votre dictionnaire atteint un seuil, et non après un nombre fixe de fichiers d’entrée. S’il y avait beaucoup de doublons dans un groupe de 5 000 chaînes, vous n’utiliseriez toujours pas beaucoup de mémoire. Vous pouvez ainsi trouver beaucoup plus de doublons lors du premier passage.

• Les lots sortingés accélèrent la fusion. Vous pouvez et devriez fusionner plusieurs -> un au lieu d’une fusion binary. Utilisez une PriorityQueue pour déterminer le fichier d’entrée contenant la ligne suivante.

• Pour éviter une utilisation intensive de la mémoire lors du sorting des clés dans une table de hachage, utilisez un dictionnaire capable d’effectuer un parcours dans l’ordre des clés. (c.-à-d. sortingez à la volée.) Il existe SortedDictionary (basé sur un arbre binary). Cela entrelace également l’utilisation du processeur pour le sorting avec les E / S en attente d’obtention des chaînes d’entrée.

• Triez radicalement chaque lot en sorties par premier caractère (az, non alphabétique sortingé avant A et non alphabétique sortingé après z ). Ou un autre choix de seau qui dissortingbue bien vos clés. Utilisez des dictionnaires distincts pour chaque compartiment de base et ne videz que les plus gros fichiers d’un lot lorsque vous atteignez le plafond de votre mémoire. (Une heuristique d’éviction plus sophistiquée que “la plus grosse” peut en valoir la peine.)

• étranglez les E / S (en particulier lors de la fusion) et vérifiez la charge du processeur et la pression de la mémoire du système. Adaptez le comportement en conséquence pour ne pas causer d’impact lorsque le serveur est le plus occupé.

• Pour les fichiers temporaires plus petits au coût du temps processeur, utilisez un codage à préfixe commun, ou peut-être lz4.

• Un dictionnaire peu encombrant autorisera des tailles de lot plus grandes (et donc une plus grande fenêtre de recherche de doublons) pour la même limite de mémoire supérieure. Un Trie (ou mieux, Radix Trie ) peut être idéal, car il stocke les caractères dans les nœuds d’arborescence, avec les préfixes communs stockés une seule fois. Les graphes de mots acycliques dirigés sont encore plus compacts (recherche de la redondance entre des sous-chaînes communes qui ne sont pas des préfixes). En utiliser un comme dictionnaire est délicat mais probablement possible (voir ci-dessous).

• Tirez parti du fait qu’il n’est pas nécessaire de supprimer des nœuds d’arborescence ou des chaînes avant de vider l’ensemble du dictionnaire. Utilisez un tableau de noeuds pouvant être développé et un autre tableau de caractères pouvant être développé qui regroupe les chaînes de bout en bout. (Utile pour un Radrie Trie (nœuds à plusieurs caractères), mais pas pour un Trie standard où chaque nœud est un seul caractère.)

• Selon la manière dont les doublons sont dissortingbués, il est possible que vous ne puissiez pas en trouver beaucoup au premier passage. Cela a des implications, mais cela ne change pas vraiment la façon dont vous finissez par fusionner.

---

Je suppose que vous avez une idée de traversée de répertoire en tête, qui peut efficacement fournir votre code avec un stream de chaînes à identifier et à compter. Je vais donc simplement dire “chaînes” ou “clés”, pour parler des entrées.

Éliminez autant de caractères inutiles que possible (par exemple, perdez le .xml s’ils sont tous au .xml ).

---

Il peut être utile d’effectuer le travail gourmand en ressources processeur / mémoire sur une machine distincte, en fonction du matériel dont vous disposez et d’une connexion réseau rapide à votre serveur de production critique.

Vous pouvez exécuter un programme simple sur le serveur qui envoie les noms de fichiers via une connexion TCP à un programme exécuté sur un autre ordinateur, où il est possible d’utiliser beaucoup plus de mémoire en toute sécurité. Le programme sur le serveur peut toujours créer de petits lots de dictionnaires et les stocker simplement sur un système de fichiers distant.

---

Et maintenant, comme aucune des autres réponses ne rassemble vraiment tous les éléments, voici ma réponse:

Une limite supérieure sur l’utilisation de la mémoire est facile. Ecrivez votre programme pour utiliser un plafond de mémoire constante, quelle que soit la taille de l’entrée. Des entrées plus importantes conduiront à plus de phases de fusion, pas plus d’utilisation de la mémoire à aucun moment.

La meilleure estimation de l’espace de stockage temporaire que vous pouvez faire sans regarder l’entrée est une limite très conservasortingce qui suppose que chaque chaîne d’entrée est unique. Vous avez besoin d’un moyen d’estimer le nombre de chaînes d’entrée. (La plupart des systèmes de fichiers savent combien de fichiers ils contiennent, sans avoir à parcourir l’arborescence et les compter.)

Vous pouvez faire des hypothèses sur la dissortingbution des doublons pour mieux deviner.

Si le nombre de fichiers de travail, et non leur taille, pose problème, vous pouvez stocker plusieurs lots dans le même fichier de sortie, l’un après l’autre. Soit vous placez des en-têtes de longueur au début de chaque pour autoriser le saut par lot, soit vous écrivez des décalages d’octets dans un stream de données séparé. Si la taille est également importante, voyez mon paragraphe sur l’utilisation de la compression préfcode-préfixe de style frcode.

---

Comme Ian Mercer le souligne dans sa réponse, le sorting de vos lots rendra leur fusion beaucoup plus efficace. Si vous ne le faites pas, vous risquez soit de heurter un mur où votre algorithme ne peut pas avancer, soit de charger un lot, d’parsingr un autre lot pour rechercher les entrées qui se trouvent dans le premier et de réécrire le deuxième lot avec seulement les quelques entrées correspondantes potentiellement supprimées.

Si vous ne sortingez pas vos lots, la complexité temporelle de la première passe est O (N) complexe, mais vous devez sortinger à un moment ultérieur, ou les étapes ultérieures ont une limite pire, bien pire. Vous voulez que votre sortie soit sortingée globalement, donc à part les approches RadixSort, il n’est pas possible d’éviter un O (N log N) quelque part.

Avec une taille de lot limitée, des étapes de fusion O (log N) sont attendues. Votre parsing initiale a donc manqué la complexité de votre approche en ignorant ce qui doit se passer après l’écriture des lots de la phase 1.

---

Les choix de conception appropriés varient beaucoup selon que notre plafond de mémoire est suffisamment grand pour détecter de nombreux doublons dans un même lot. Si même une structure de données compacte complexe telle qu’un Trie ne vous aide pas beaucoup, le fait de placer les données dans un Trie et de les rediffuser pour écrire un lot est une perte de temps de calcul.

Si, de toute façon, vous ne pouvez pas éliminer beaucoup de doublons dans chaque lot, vous devez optimiser la mise en parallèle des clés éventuellement correspondantes pour l’étape suivante. Votre première étape peut regrouper les chaînes d’entrée par premier octet, dans un maximum de 252 fichiers de sortie (toutes les valeurs ne sont pas nécessairement des caractères de nom de fichier légaux), ou dans environ 27 fichiers de sortie (alphabet + misc), ou 26 + 26 + 1. pour majuscules / minuscules + non alphabétique. Les fichiers temporaires peuvent omettre le préfixe commun de chaque chaîne.

Ensuite, la plupart de ces lots de première étape devraient avoir une densité de duplicata beaucoup plus élevée. En réalité, cette dissortingbution Radix des entrées dans les compartiments de sortie est utile dans tous les cas, voir ci-dessous.

Vous devez tout de même sortinger vos sorties de premier étage en morceaux, pour donner au prochain passage une fenêtre beaucoup plus grande dup-find pour la même RAM.

---

Je vais passer plus de temps sur le domaine où vous pouvez trouver une quantité utile de doublons dans le stream initial, avant d’utiliser environ 100 Mo de RAM, ou ce que vous choisissez comme limite supérieure.

Évidemment, nous ajoutons des chaînes à une sorte de dictionnaire pour rechercher et comptabiliser les doublons à la volée, tout en ne nécessitant qu’un espace de stockage suffisant pour l’ensemble de chaînes uniques. Le simple fait de stocker des chaînes, puis de les sortinger serait nettement moins efficace, car nous atteindrions notre limite de RAM beaucoup plus tôt sans détection des doublons à la volée.

Pour minimiser le travail en phase2, phase1 doit rechercher et compter autant de doublons que possible, réduisant ainsi la taille totale des données p2. Réduire le travail de fusion pour la phase 2 est également une bonne chose. Des lots plus volumineux vous aident avec les deux facteurs . Il est donc très utile de vous rapprocher du plafond de votre mémoire autant que vous le pourrez en toute sécurité dans la phase 1. Au lieu d’écrire un lot après un nombre constant de chaînes d’entrée, faites-le lorsque votre consommation de mémoire approche du plafond que vous avez choisi. Les doublons sont comptés et jetés et ne nécessitent aucun stockage supplémentaire.

Une alternative à la comptabilité de mémoire précise est le suivi des chaînes uniques de votre dictionnaire, ce qui est facile (et effectué pour vous par la mise en œuvre de la bibliothèque). L’accumulation de la longueur des chaînes ajoutées peut vous donner une bonne estimation de la mémoire utilisée pour stocker les chaînes. Ou faites simplement une hypothèse sur la dissortingbution de longueur de chaîne. Définissez initialement la taille de votre table de hachage de manière à ce qu’elle n’ait pas besoin de croître lorsque vous ajoutez des éléments. Par conséquent, vous arrêtez lorsqu’elle est pleine à 60% (facteur de charge) ou quelque chose du genre.

---

Une structure de données peu encombrante pour le dictionnaire augmente notre fenêtre de recherche de dup pour une limite de mémoire donnée. Les tables de hachage deviennent très inefficaces lorsque leur facteur de charge est trop élevé, mais la table de hachage elle-même ne doit stocker que des pointeurs sur les chaînes. C’est le dictionnaire le plus familier et a une implémentation de bibliothèque.

Nous soaps que nous allons vouloir que notre lot soit sortingé une fois que nous aurons vu suffisamment de clés uniques. Il serait donc logique d’utiliser un dictionnaire pouvant être parcouru dans l’ordre. Le sorting à la volée est logique car les clés entreront lentement , limitées par les entrées / sorties du disque car nous lisons des métadonnées de système de fichiers. Un inconvénient est que si la plupart des clés que nous voyons sont des doublons, nous effectuons beaucoup de recherches O (log batchsize) plutôt que beaucoup de recherches O (1). Et il est plus probable qu’une clé soit un doublon lorsque le dictionnaire est volumineux. La plupart de ces requêtes O (log batchsize) auront donc une taille de lot proche de max et non uniformément répartie entre 0 et max. Une arborescence paie le temps système O (log n) de sorting pour chaque recherche, que la clé soit unique ou non. Une table de hachage ne paie que le coût de sorting à la fin après la suppression des doublons. Donc, pour un arbre, c’est O (total_keys * log unique_keys), table de hachage est O (unique_keys * log unique_keys) pour sortinger un lot.

Une table de hachage avec un facteur de charge maximal défini à 0,75 ou quelque chose d’assez dense, mais le fait de sortinger les KeyValuePair avant d’écrire un lot met probablement un frein à l’utilisation de Dictionnaire standard. Vous n’avez pas besoin de copies des chaînes, mais vous finirez probablement par copier tous les pointeurs (refs) afin de supprimer de l’espace pour un sorting non sur place, et peut-être aussi lors de leur sortie de la table de hachage avant le sorting. (Ou au lieu de simples pointeurs, KeyValuePair, pour éviter de devoir revenir en arrière et rechercher chaque chaîne dans la table de hachage). Si de courtes pointes de grande consommation de mémoire sont tolérables et ne vous obligent pas à permuter / page sur disque, tout ira bien. Cela est évitable si vous pouvez effectuer un sorting à la place dans la mémoire tampon utilisée par la table de hachage, mais je doute que cela puisse arriver avec les conteneurs de bibliothèques standard.

Il est probablement préférable d’utiliser un nombre constant de ressources processeur pour conserver le dictionnaire sortingé lorsque les clés de vitesse sont disponibles. De plus, des rafales peu fréquentes d’utilisation du processeur permettent de sortinger toutes les clés d’un lot, en plus de la consommation de mémoire en rafale.

La bibliothèque standard .NET a SortedDictionary , qui selon la documentation est implémentée avec une arborescence binary. Je n’ai pas vérifié si cette fonction avait une fonction de rééquilibrage ou si elle utilisait un arbre rouge-noir pour garantir les performances dans les cas les plus défavorables. Je ne suis pas sûr de la surcharge de mémoire qu’il aurait. S’il s’agit d’une tâche ponctuelle, je vous recommande vivement de l’utiliser pour la mettre en œuvre rapidement et facilement. Et aussi pour une première version d’un design plus optimisé pour une utilisation répétée. Vous trouverez probablement que c’est assez bon, à moins que vous ne trouviez une belle implémentation de bibliothèque de Tries.

---

Structures de données pour dictionnaires sortingés à mémoire efficace

Plus le dictionnaire utilisé est efficace en termes de mémoire, plus nous pouvons trouver de pièges avant d’écrire un lot et de supprimer le dictionnaire. De plus, s’il s’agit d’un dictionnaire sortingé, plus nos lots peuvent être volumineux même lorsqu’ils ne peuvent pas trouver de doublons.

Un impact secondaire du choix de la structure de données est la quantité de trafic mémoire générée lors de l’exécution sur le serveur critique. Un tableau sortingé (avec le temps de recherche O (log n) (recherche binary) et le temps d’insertion O (n) (lecture aléatoire des éléments pour libérer de l’espace) serait compact. Cependant, cela ne serait pas simplement lent, cela saturerait la bande passante mémoire avec memmove la plupart du temps. Une utilisation à 100% du processeur aurait ainsi un impact plus important sur les performances du serveur que l’utilisation à 100% du processeur dans la recherche d’un arbre binary. Il ne sait pas où charger le prochain nœud tant qu’il n’a pas chargé le nœud actuel. Il ne peut donc pas créer de pipeline de demandes de mémoire. Les prédictions erronées des twigs dans la recherche dans l’arborescence aident également à modérer la consommation de la bande passante mémoire partagée par tous les cœurs. (C’est vrai, certains programmes d’utilisation à 100% de -CPU sont pires que d’autres!)

C’est bien si vider notre dictionnaire ne laisse pas la mémoire fragmentée quand on le vide. Les nœuds d’arborescence ayant une taille constante, un ensemble de trous dispersés sera utilisable pour les allocations futures de nœuds d’arborescence. Toutefois, si nous avons des dictionnaires distincts pour plusieurs compartiments de base (voir ci-dessous), les chaînes de clés associées à d’autres dictionnaires peuvent être mélangées à des nœuds d’arborescence. Cela pourrait rendre difficile pour malloc de réutiliser toute la mémoire libérée, ce qui augmenterait potentiellement l’utilisation réelle de la mémoire visible par le système d’exploitation. (À moins que la récupération de place du runtime C # effectue le compactage, auquel cas la fragmentation est prise en charge.)

Etant donné que vous n’avez jamais besoin de supprimer des nœuds avant de vider le dictionnaire et de tous les supprimer, vous pouvez stocker vos nœuds d’arborescence dans un tableau évolutif. Ainsi, la gestion de la mémoire ne doit garder trace que d’une seule grosse allocation, réduisant ainsi les frais généraux de comptabilité par rapport à malloc de chaque noeud séparément. Au lieu de véritables pointeurs, les pointeurs enfants gauche / droit pourraient être des index de tableau. Cela vous permet d’utiliser uniquement 16 ou 24 bits. (Un tas est un autre type d’arbre binary stocké dans un tableau, mais il ne peut pas être utilisé efficacement comme dictionnaire. C’est un arbre, mais pas un arbre de recherche ).

L’enregistrement des clés de chaîne pour un dictionnaire devrait normalement s’effectuer avec chaque chaîne en tant qu’object alloué séparément, avec des pointeurs sur un tableau. Comme il est de nouveau nécessaire de supprimer, d’agrandir ou même de modifier un élément tant que vous n’êtes pas prêt à tous les supprimer, vous pouvez les ranger dans un tableau de caractères, avec un zéro octet de fin à la fin de chacun. Cela économise à nouveau beaucoup de comptabilité et facilite également le suivi de la quantité de mémoire utilisée par les chaînes de clés, ce qui vous permet de vous rapprocher en toute sécurité de la limite supérieure de votre mémoire choisie.

Trie / DAWG pour un stockage encore plus compact

Pour un stockage encore plus dense d’un ensemble de chaînes, nous pouvons éliminer la redondance consistant à stocker tous les caractères de chaque chaîne, car il existe probablement de nombreux préfixes communs.

Un Trie stocke les chaînes dans l’arborescence, vous donnant une compression de préfixe commun. Il peut être parcouru dans un ordre sortingé afin qu’il soit sortingé à la volée. Chaque nœud a autant d’enfants qu’il y a de caractères suivants différents dans le jeu, donc ce n’est pas un arbre binary. Une implémentation partielle AC # Trie (suppression non écrite) peut être trouvée dans cette réponse SO , à une question similaire à celle-ci mais ne nécessitant pas de traitement par lots / sorting externe.

Les noeuds sortingés doivent potentiellement stocker de nombreux pointeurs enfants afin que chaque noeud puisse être volumineux. Ou chaque nœud peut être de taille variable, contenant la liste des paires nextchar: ref à l’intérieur du nœud, si C # le permet. Ou, comme le dit l’article de Wikipedia, un nœud peut en réalité être une liste chaînée ou un arbre de recherche binary, afin d’éviter de gaspiller de l’espace dans les nœuds avec peu d’enfants. (Les niveaux inférieurs d’une arborescence en auront beaucoup.) Des marqueurs / nœuds de fin de mot sont nécessaires pour distinguer les sous-chaînes qui ne sont pas des entrées de dictionnaire distinctes de celles qui le sont. Notre champ de comptage peut servir à cette fin. Count = 0 signifie que la sous-chaîne se terminant ici n’est pas dans le dictionnaire. count> = 0 signifie que c’est le cas.

Un arbre plus compact est l’ arbre Radix, ou arbre PATRICIA , qui stocke plusieurs caractères par nœud.

Une autre extension de cette idée est l’ automate déterministe à états finis acycliques (DAFSA) , parfois appelé graphe de mots acyclique dirigé (DAWG), mais notez que l’ article de DAWG dans wikipedia traite d’une chose différente portant le même nom. Je ne suis pas sûr qu’un DAWG puisse être parcouru dans un ordre sortingé pour obtenir toutes les clés à la fin, et comme le fait remarquer wikipedia, le stockage des données associées (comme un nombre de doublons) nécessite une modification. Je ne suis pas sûr non plus qu’elles puissent être construites progressivement, mais je pense que vous pouvez effectuer des recherches sans les compacter. Les entrées nouvellement ajoutées seront stockées comme un Trie, jusqu’à ce qu’une étape de compactage toutes les 128 nouvelles clés les fusionne dans le DAWG. (Ou exécutez le compactage moins fréquemment pour les groupes de travail plus importants, de sorte que vous ne le fassiez pas trop, comme doubler la taille d’une table de hachage lorsqu’elle doit croître, au lieu de croître linéairement, pour amortir l’opération coûteuse.)

Vous pouvez rendre un DAWG plus compact en stockant plusieurs caractères dans un seul nœud lorsqu’il n’y a pas de twigment / convergent. Cette page mentionne également une approche de codage de Huffman pour compacter des DAWG, et contient d’autres liens et citations d’articles.

L’implémentation DAWG (en C) de JohnPaul Adamovsky est satisfaisante et décrit certaines optimisations qu’elle utilise. Je n’ai pas examiné avec soin pour voir s’il peut mapper des chaînes à des comptes. Il est optimisé pour stocker tous les nœuds d’un tableau.

Cette réponse aux mots du nombre de doublons dans 1 To de question de texte suggère des groupes de travail, et comporte quelques liens, mais je ne suis pas sûr de son utilité.

---

Ecrire des lots: Radix sur le premier caractère

Vous pouvez utiliser votre RadixSort et conserver des dictionnaires distincts pour chaque caractère de départ (ou pour un z, un alphabet non alphabétique qui sortinge avant un, un alphabet non alphabétique sortingant après z). Chaque dictionnaire écrit dans un fichier temporaire différent. Si vous avez plusieurs nœuds de calcul disponibles pour une approche MapReduce, ce serait le moyen de répartir le travail de fusion entre les nœuds de calcul.

Cela permet une modification intéressante: au lieu d’écrire tous les seaux radix en même temps, écrivez uniquement le plus grand dictionnaire sous forme de lot . Cela évite que de petites quantités entrent dans des seaux à chaque fois. Cela réduira la largeur de la fusion au sein de chaque compartiment, accélérant la phase 2.

Avec un arbre binary, cela réduit la profondeur de chaque arbre d’environ log2 (num_buckets), ce qui accélère les recherches. Avec un Trie, cela est redondant ( chaque nœud utilise le caractère suivant comme base pour ordonner les arbres enfants). Avec un DAWG, cela nuit effectivement à votre efficacité en termes d’espace, car vous perdez le sens de la redondance entre des chaînes avec des débuts différents mais des parties partagées ultérieures.

Cela risque de mal se comporter s’il y a quelques seaux peu touchés qui continuent de croître, mais ne finissent généralement pas par être les plus grands. Ils pourraient utiliser une grande partie de votre mémoire totale, ce qui permettrait d’obtenir de petites quantités à partir des seaux couramment utilisés. Vous pouvez implémenter un algorithme d’éviction plus intelligent qui enregistre la dernière vidange d’un compartiment (dictionnaire). Le score NeedsEptptying pour un seau correspond à un produit de taille et d’âge. Ou peut-être une fonction d’âge, comme sqrt (age). Il serait également utile d’enregistrer le nombre de doublons trouvés par chaque compartiment depuis la dernière vidange. Si vous êtes à un endroit de votre stream d’entrée où il y a beaucoup de répétitions pour l’un des compartiments, la dernière chose que vous voulez faire est de le vider fréquemment. Peut-être que chaque fois que vous trouvez un doublon dans un compartiment, incrémentez un compteur. Regardez le rapport âge / dups trouvés. Il sera facile de trouver les seaux à faible utilisation qui retiennent la RAM des autres seaux, lorsque leur taille commencera à augmenter. Les seaux de grande valeur peuvent être conservés même s’ils sont les plus gros actuels, s’ils trouvent beaucoup de doublons.

Si vos structures de données permettant de suivre l’âge et les doublons trouvés sont des structures de tableaux, la (last_emptied[bucket] - current_pos) / (float)dups_found[bucket] peut être effectuée efficacement avec une virgule flottante vectorielle. Une division entière est plus lente qu’une division FP. Une division de PF a la même vitesse que 4 divisions de FP, et les compilateurs peuvent, espérons-le, s’auto-vectoriser si vous leur facilitez la tâche de la sorte.

Il y a beaucoup de travail à faire entre les seaux qui se remplissent, alors la division serait un petit hoquet, à moins que vous utilisiez beaucoup de seaux.

choisir comment seau

Avec un bon algorithme d’expulsion, un choix idéal de compartiment permettra de regrouper les clés qui ont rarement des doublons dans certains compartiments et les compartiments qui ont beaucoup de doublons dans d’autres compartiments. Si vous êtes au courant de l’existence de modèles dans vos données, ce serait un moyen de les exploiter. Le fait que certains compartiments soient pour la plupart bas-dup signifie que toutes ces clés uniques n’enlèvent pas les précieuses clés dans un lot de sortie. Un algorithme d’expulsion qui examine la valeur d’un seau en termes de doublons trouvés par clé unique déterminera automatiquement quels seaux sont précieux et valent la peine d’être conservés, même si leur taille augmente lentement.

Il existe de nombreuses façons de fondre vos cordes dans des seaux. Certains veilleront à ce que chaque élément d’un compartiment soit inférieur à celui de tous les autres compartiments, de sorte qu’il est facile de produire une sortie entièrement sortingée. Certains ne veulent pas, mais ont d’autres avantages. Il y aura des compromis entre les choix de compartiments, qui dépendent tous de données:

• bon pour trouver beaucoup de doublons lors du premier passage (par exemple, en séparant les motifs à haute duplication des motifs à faible dupe)
• répartit le nombre de lots de manière uniforme entre les compartiments (ainsi, aucun compartiment ne contient un nombre énorme de lots nécessitant une fusion en plusieurs étapes en phase2), et peut-être d’autres facteurs.
• produit un mauvais comportement lorsqu’il est combiné avec votre algorithme d’expulsion sur votre dataset.
• quantité de fusion entre compartiments nécessaire pour produire une sortie sortingée de manière globale. L’importance de cette échelle dépend du nombre total de chaînes uniques, pas du nombre de chaînes d’entrée.

Je suis sûr que les personnes intelligentes ont réfléchi aux bonnes manières de placer des cordes devant moi, donc cela vaut probablement la peine de rechercher si l’approche évidente du by-first-character n’est pas idéale. Ce cas d’utilisation particulier (sortinger tout en éliminant / comptant les doublons) n’est pas typique. Je pense que la plupart des travaux de sorting ne prennent en compte que les sortings préservant les doublons. Il est donc possible que vous ne trouviez pas grand-chose qui aide à choisir un bon algorithme de compartimentage pour un sorting externe comptant le dup. Dans tous les cas, cela dépendra des données.

Voici quelques options concrètes pour le compartimentage: Base = deux premiers octets ensemble (toujours en combinant des majuscules / minuscules et des caractères non alphabétiques). Ou Radix = le premier octet du code de hachage. (Nécessite une fusion globale pour produire une sortie sortingée.) Ou Radix = (str[0]>>2) << 6 + str[1]>>2 . c’est-à-dire ignorer les 2 bits les plus bas des 2 premiers caractères, pour mettre ensemble [abcd][abcd].* , [abcd][efgh].* , etc. Cela nécessiterait également une certaine fusion des résultats sortingés entre seaux. Par exemple, daxxx serait dans le premier seau, mais aexxx serait dans le second. Mais seuls les compartiments avec les mêmes bits de poids fort en premier caractère doivent être fusionnés pour produire la sortie finale sortingée.

Une idée pour gérer un choix de compartiment qui donne une excellente recherche de doublons mais nécessite un sorting par fusion: lors de l’écriture de la sortie phase2, définissez le seau avec le premier caractère comme radix pour produire l’ordre de sorting souhaité. Chaque compartiment phase1 diffuse la sortie dans des compartiments phase2 dans le cadre du sorting global. Une fois que tous les lots de phase1 pouvant inclure des chaînes commençant par a ont été traités, effectuez la fusion du compartiment phase2 dans la sortie finale et supprimez ces fichiers temporaires.

Radix = les 2 premiers octets (combinant des caractères non alphabétiques) permettraient 28 ² = 784 seaux. Avec 200 Mo de RAM, la taille moyenne du fichier de sortie n’est que de ~ 256 Ko. Vider un seau à la fois en ferait le minimum, et vous obtiendrez généralement des lots plus gros, pour que cela fonctionne. (Votre algorithme d’expulsion risque de poser des problèmes pathologiques qui l’ont obligé à conserver beaucoup de gros seaux et à écrire une série de minuscules lots pour les nouveaux seaux. Il existe des risques pour une heuristique intelligente si vous ne testez pas soigneusement).

Plusieurs lots regroupés dans le même fichier de sortie sont probablement plus utiles avec de nombreux petits compartiments. Vous aurez par exemple 784 fichiers de sortie, chacun contenant une série de lots. Espérons que votre système de fichiers dispose de suffisamment d’espace libre et qu’il soit assez intelligent pour ne pas trop fragmenter lors de la dispersion d’écritures de petite taille dans de nombreux fichiers.

---

Fusion:

Dans les étapes de fusion, avec des lots sortingés, nous n’avons pas besoin d’un dictionnaire. Prenez juste la ligne suivante du lot qui a le plus bas, en combinant les doublons au fur et à mesure que vous les trouvez.

MergeSort fusionne généralement des paires, mais lors du sorting externe (par exemple, disque -> disque) , une entrée beaucoup plus large est commune pour éviter la lecture et la réécriture de la sortie souvent. Avoir 25 fichiers d’entrée ouverts à fusionner en un seul fichier de sortie ne devrait pas poser de problème. Utilisez l’implémentation de bibliothèque PriorityQueue (généralement implémentée en tant que tas) pour choisir l’élément d’entrée suivant dans de nombreuses listes sortingées. Peut-être append des lignes d’entrée avec la chaîne comme priorité, et le nombre et le numéro de fichier d’entrée comme charge utile.

Si vous avez utilisé radical dissortingbution-par-premier-caractère dans la première passe, fusionnez tous les lots a dans le fichier de sortie final (même si ce processus nécessite plusieurs étapes de fusion), puis tous les lots b , etc. Il est nécessaire de vérifier l’un des lots du début avec a godet par rapport aux lots d’un autre seau , ce qui évite beaucoup de travail de fusion, en particulier. si vos clés sont bien dissortingbuées par le premier caractère.

---

Réduction de l’impact sur le serveur de production:

Limitez les E / S de disque lors de la fusion afin d’éviter de placer votre serveur à genoux si la prélecture de disque génère une grande quantité de lectures dans la queue d’E / S. Limiter votre E / S, plutôt que de fusionner plus étroitement, est probablement un meilleur choix. Si le serveur est occupé par son travail normal, il ne fera pas beaucoup de grandes lectures séquentielles, même si vous ne lisez que quelques fichiers.

Vérifiez la charge du système de temps en temps pendant le fonctionnement. Si le temps est élevé, dormez pendant 1 seconde avant de travailler et de vérifier à nouveau. Si le niveau est vraiment élevé, ne travaillez plus tant que la charge moyenne n’est pas réduite (30 secondes de sumil entre les vérifications).

Vérifiez également l’utilisation de la mémoire système et réduisez votre seuil de lot si la mémoire est saturée sur le serveur de production. (Ou si c’est vraiment serré, effacez votre lot partiel et dormez jusqu’à ce que la mémoire diminue.)

Si la taille du fichier temporaire pose un problème, vous pouvez utiliser une compression de préfixe commun telle que frcode de updatedb / local pour réduire de manière significative la taille du fichier des listes de chaînes sortingées. Utilisez probablement le sorting sensible à la casse dans un lot, mais la radix indifférente à la casse. Ainsi, chaque lot dans le seau aura tous les A , puis tous les A Ou même LZ4 les compresse / décompresse à la volée. Utilisez hex pour les comptes, pas décimal. C’est plus court et plus rapide à encoder / décoder.

Utilisez un séparateur qui n’est pas un caractère de nom de fichier légal, tel que / , entre key et count. L’parsing de chaîne peut prendre beaucoup de temps de calcul lors de la fusion, il est donc intéressant d’envisager. Si vous pouvez laisser des chaînes dans des mémoires tampons d’entrée par fichier et que vous y dirigez votre PQueue, c’est peut-être une bonne chose. (Et vous dire de quel fichier d’entrée provient une chaîne, sans la stocker séparément.)

---

l’optimisation des performances:

Si les chaînes non sortingées initiales étaient disponibles très rapidement, alors une table de hachage avec de petits lots correspondant au dictionnaire dans le cache L3 de la CPU pourrait être gagnante, à moins qu’une fenêtre plus grande puisse inclure une fraction beaucoup plus grande de clés et trouver plus de doublons. Cela dépend du nombre de répétitions typiques dans des fichiers de 100 000 $. Construisez de petits lots sortingés dans la RAM au fur et à mesure de la lecture, puis fusionnez-les en un lot de disques. Cela peut être plus efficace que de faire un sorting rapide en mémoire, car vous n’avez pas d’access aléatoire à l’entrée tant que vous ne l’avez pas lue initialement.

Etant donné que les E / S seront probablement la limite, les gros lots qui ne rentrent pas dans le cache de données de la CPU sont probablement gagnants pour trouver plus de doublons et (considérablement?) Réduire la quantité de travail de fusion à effectuer.

It might be convenient to check the hash table size / memory consumption after every chunk of filenames you get from the OS, or after every subdirectory or whatever. As long as you choose a conservative size bound, and you make sure you can’t go for too long without checking, you don’t need to go nuts checking every iteration.

---

This paper from 1983 examines external merge-sorting eliminating duplicates as they’re encountered, and also suggests duplicate elimination with a hash function and a bitmap. With long input ssortingngs, storing MD5 or SHA1 hashes for duplicate-elimination saves a lot of space.

I’m not sure what they had in mind with their bitmap idea. Being collision-resistant enough to be usable without going back to check the original ssortingng would require a hash code of too many bits to index a reasonable-size bitmap. (eg MD5 is a 128bit hash).

How do you “merge the group files” in your approach? In worst case every line had a different name template so each group file had 5,000 lines in it and each merge doubles the number of lines until you overflow memory.

Your friend is closer to the answer, those intermediate files need to be sorted so you can read them line by line and merge them to create new files without having to hold them all in memory. This is a well-known problem, it’s an external sort . Once sorted you can count the results.

A jolly good problem.

Considering that you intend to process the results in batches of 5000 , I don’t believe memory optimisations will be of particular importance so we could probably ignore that aspect like a bad Adam Sandler film and move onto the more exciting stuff. Besides, just because some computation uses more RAM does not necessarily imply it’s a bad algorithm. No one ever complained about look-up tables.

However, I do agree computationally the dictionary approach is better because it’s faster . With respect to the alternative, why perform an unnecessary sort even if its quick? The latter, with its “O(m log m)” is ultimately slower than “O(m)”.

The Real Problem?

With RAM out of the equation, the problem is essentially that of computation . Any “performance problem” in the algorithm will arguably be insignificant to the time it takes to traverse the file system in the first place .

That’s arguably where the real challenge will be. A problem for another time perhaps?

EDIT : displayName makes a good point about using Hadoop – quite ideal for concurrent jobs and compute

Bonne chance!

Your problem is a very good candidate for Map-Reduce . Great news: You don’t need to move from C# to Java (Hadoop) as Map-Reduce is possible in .NET framework!

Through LINQs you have the basic elements of execution in place already for performing Map Reduce in C#. This might be one advantage over going for External Sort though there is no question about the observation behind External Sort. This link has the ‘Hello World!’ of Map-Reduce already implemented in C# using LINQs and should get you started.

---

If you do move to Java, one of the most comprehensive tutorial about it is here . Google about Hadoop and Map-Reduce and you will get plenty of information and numerous good online video tutorials.

Further, if you wish to move to Java, your requirements of:

• Sorted results
• critical RAM usage

will surely be met as they are inbuilt fulfillments you get from a Map-Reduce job in Hadoop.