Je dois modifier un programme C et je dois inclure un ensemble d'ensembles d'entier non signé. C'est-à-dire que j'ai des millions d'ensembles d'entiers (chacun de ces ensembles entier contient entre 3 et 100 entiers), et je dois les stocker dans une structure, appelez-le dans le répertoire, qui peut dans le temps logarithmique me dire si une personne donnée Integer Set existe déjà dans le répertoire. Les seules opérations à définir sur le répertoire sont les recherches et l'insertion.
Ce serait facile dans des langues avec une prise en charge intégrée pour les structures de données utiles, mais je suis un étranger à C et à regarder autour de Google (surprenante) ne répond pas à ma question de manière satisfaisante. Ce projet ressemble à peu près à droite:
http://uthash.sourceforge.net/
Mais je devrais proposer mon propre générateur de clés de hachage.
Ceci est un problème standard et simple, alors j'espère qu'il y a une solution standard et simple.
4 Réponses :
Implémentez vous-même une simple table de hachage. Il vous fera un meilleur programmeur lorsque vous savez comment implémenter une seule.
Il est peut-être vrai que cela me ferait un meilleur programmeur pour la mettre en œuvre moi-même. Cependant, ce n'est pas une bonne réponse. Si je voulais simplement devenir un meilleur programmeur, il y a probablement de meilleurs exercices que je pourrais passer mon temps. De plus, il est peu probable que je voudrais mettre en œuvre une solution qui fonctionne de manière optimale, et il est probable qu'une solution à haute performance me prenne beaucoup de temps à mettre en œuvre. Je trouve étrange qu'il n'y a pas de bibliothèque comme C ++ 'S STL qui me donnerait une solution simple, et cela au lieu de cela, j'ai besoin de réinventer (ou de réapprouiller) la roue.
Vous ne répondez pas vraiment à la question
EDIT: strong> Désolé, j'ai commencé à répondre comme il est C ++ et non C. Oui, vous devez trouver votre fonction Hash et le code par vous-même .. Puisque vous connaissez déjà la dimension moyenne d'un ensemble Pas si difficile, choisissez simplement une bonne fonction de hachage! Mais vous devrez codifier un ensemble complet dans un seul numéro si vous souhaitez vérifier si un répertoire est déjà là. Vous pouvez essayer en hachage de manière itérative le nombre unique de l'ensemble: P> #include <set>
int nums[6] = {1,6,34,2,67,41};
set<int> numbers;
for( int i = 0; i < 6; ++i ) numbers.insert(nums[i]);
for( set<int>::const_iterator iter = numbers.begin(); iter != numbers.end(); ++iter )
cout << *iter << ' ';
L'OP a posé une question sur un programme C et la STL est purement c ++.
STL est pour C ++, il s'agit de la question est étiquetée comme "C"
oui, désolé, je l'ai édité :) vient de me réveiller .. toujours un peu flou
Si je vous comprends correctement, vous voulez représenter un ensemble d'ensembles d'entier que je ne pense pas est particulièrement trivial.
Le premier point est de représenter un ensemble d'entiers. Le moyen le plus simple serait d'utiliser une matrice de taille variable comme ceci: p> que vous pouvez créer un nouveau jeu (avec un nombre fixe d'éléments) avec P> intset *newset(int size)
{
intset *set;
set = malloc(sizeof(intset) + sizeof(int)*(size-1));
if (set) set->size = size;
return set;
}
Je suis surpris d'entendre que ce n'est pas trivial, car dans d'autres langues (même le similaire C ++ avec son stl), ce serait trivial. Les valeurs entier sont non signées et dans une certaine plage fixe (comme dans la plage est connue au moment de l'exécution, ne compilez pas l'heure), dans la plupart des cas entre 0 et 10 millions, bien que dans certains cas entre 0 et jusqu'à 100 millions. Si j'utilise utiliser une table de hachage, toutes les fonctions de hachage me viennent à l'esprit? Le hachage de zoboriste serait-il approprié ici?
Cela dépend de ce que vous allez faire avec les données. Mais peut-être TSearch fait déjà ce que vous voulez. Vous pouvez également créer une matrice triée pour chaque ensemble et rechercher les valeurs avec BSearch, bien que la performance puisse souffrir pendant l'insertion.
Edit: Si vous recherchez une bibliothèque (externe), vous trouverez une comparaison de certaines implémentation de la table de hachage C ++ ici . L'auteur de l'article a écrit une implémentation d'en-tête générique appelée KHASH . Donc, vous êtes compilé binaire, vous n'avez aucune dépendance supplémentaire.
TSearch est idéal pour gérer les arbres binaires d'éléments génériques. Il ne ajoutera pas deux fois un élément, afin que nous puissions l'utiliser pour des ensembles.