Quel est le moyen le plus rapide de compter les éléments uniques dans une liste de milliards d'éléments?

Question

Mon problème n'est pas d'habitude. Imaginons quelques milliards de cordes. Les chaînes sont généralement moins de 15 caractères. Dans cette liste j'ai besoin de savoir le nombre d'éléments uniques.

Tout d'abord, quel objet dois-je utiliser? Vous ne devriez pas oublier si j'ajoute un nouvel élément, je dois vérifier si il est déjà existant dans la liste. Ce n'est pas un problème au début, mais après quelques millions de mots qu'il peut vraiment ralentir le processus.

C'est pourquoi j'ai pensé que la table de hachage serait l'idéal pour cette tâche, car la vérification de la liste est idéalement seul journal(1). Malheureusement, un seul objet .net peut être seulement 2 GO.

La prochaine étape sera de mettre en œuvre une coutume de table de hachage qui contient une liste de 2 go de tables de hachage.

Je suis vous vous demandez peut-être certains d'entre vous le savent trouver une meilleure solution. (L'ordinateur a de très haute spécification.)

Answer 1

Je sauterais l'exercice sur les structures de données et utiliserais simplement une base de données SQL. Pourquoi écrire une autre structure de données personnalisée que vous devez analyser et déboguer, utilisez simplement une base de données. Ils sont vraiment bons pour répondre à des questions comme celle-ci.

Answer 2

Je considérerais un Trie ou un graphique de mots acyclique dirigé qui devrait être plus économe en espace qu'une table de hachage. Le test d'appartenance à une chaîne serait O (len) où len est la longueur de la chaîne d'entrée, qui est probablement la même chose qu'une fonction de hachage de chaîne.

Answer 3

Ce problème peut être résolu dans le pire des cas O(n) le temps en utilisant la base de tri avec le comptage de tri un tri stable pour chaque position de caractère. C'est théoriquement mieux que d'utiliser une table de hachage (en O(n) prévu, mais pas garanti) ou mergesort (O(n log n)). À l'aide d'un trie pourraient également entraîner, dans le pire des cas O(n) en temps de la solution (constante de temps de recherche plus de n clés, puisque toutes les chaînes ont une longueur délimitée c'est une petite constante), ce qui est comparable. Je ne suis pas sûr de savoir comment ils se comparent dans la pratique. Radix de tri est également assez facile à mettre en œuvre et il y a beaucoup d'implémentations existantes.

Si toutes les chaînes sont d caractères ou plus courte, et le nombre de caractères distincts est k, alors radix de tri prend O(d (n + k)) temps de faire le tri n touches. Après le tri, vous pouvez parcourir la liste triée en O(n) le temps et incrémenter un compteur à chaque fois que vous arrivez à une nouvelle chaîne de caractères. Ce serait le nombre de chaînes distinctes. Puisque d est ~15 et k est relativement petit par rapport à n (un milliard), le temps d'exécution n'est pas trop mauvais.

Il utilise O(dn) de l'espace bien (pour tenir chaque chaîne), il est donc moins efficace que la tente.

Answer 4

Si les éléments sont des chaînes de caractères, ce qui est comparable... alors je suggère d'abandonner l'idée d'une table de hachage et d'aller avec quelque chose de plus comme un Arbre de Recherche Binaire. Il existe plusieurs implémentations dans C# (aucun de ceux qui viennent construit dans le Cadre). Assurez-vous d'obtenir un qui est équilibré, comme un Rouge Noir Arbre ou un Arbre AVL.

L'avantage est que chaque objet dans l'arbre est relativement petit (contient de l'objet, et un lien vers sa mère et de deux feuilles), de sorte que vous pouvez avoir toute une série d'entre eux.

Aussi, parce que c'est trié, l'extraction et l'insertion sont à la fois O log(n).

Answer 5

Puisque vous spécifiez qu'un seul objet ne peut pas contenir toutes les chaînes, je suppose que vous disposez des chaînes sur le disque ou dans une autre mémoire externe. Dans ce cas, j'irais probablement avec le tri. À partir d'une liste triée, il est simple d'extraire les éléments uniques. Le tri par fusion est populaire pour les tris externes et n'a besoin que d'une quantité d'espace supplémentaire égale à celle dont vous disposez. Commencez par diviser l'entrée en morceaux qui tiennent dans la mémoire, triez-les, puis commencez à fusionner.