Je dois stocker beaucoup de mots (+ 200k) dans un programme Java et je souhaite y accéder vraiment vite.
J'ai juste besoin de savoir si un mot donné appartient à mon "dictionnaire". Je n'ai pas besoin d'une paire comme PS: Peut-être que l'utilisation d'une structure de données n'est pas la meilleure façon de le faire? Lire chaque fois que le fichier contenant les mots sera plus efficace?
Edit: C'est un petit projet. Je dois faire face à l'efficacité et à la mémoire
Dernier édition: je choisis enfin hashset.
4 Réponses :
Utilisez soit un Trie ou Arbre Patricia en fonction de la distribution des mots. Je vais personnellement aller avec Patricia Tree car il est plus optimisé pour l'utilisation de la mémoire (bien qu'il soit plus difficile de mettre en œuvre).
Pour une assez petite quantité d'objets comme dans le cas d'utilisation de l'OP, un hashset ferait très bien. Vaut également la peine d'être noté, il n'y a pas d'implémentations TRIE / PATRICIA TREE dans la norme JDK.
Utilisez des ensembles Java car les ensembles sont une structure de données triée linéaire comme celui de l'arbre. Donc, pour la recherche, des techniques telles que la recherche binaire peuvent être implémentées et elles sont rapides sans répétition.
C'est la structure d'un jeu Java.
En outre, il ne permettra pas de laisser la duplication donc de réduire la redondance et de sauvegarder votre mémoire.
Si vous voulez connaître diverses complexités d'algorithmes de recherche, référez ce lien. Voici
Les ensembles vont perdre beaucoup de mémoire. Il existe des structures de données spécialisées pour ce type de tâches.
@IvaylosTrandjev 200k Mots de 10 caractères en moyenne, stocké dans un hashset, prendra peut-être 5 à 10 Mo en mémoire. Ce n'est pas beaucoup ...
@assylias Ya C'est ce que la recherche sera beaucoup rapide car les ensembles sont triés et vous pouvez appliquer de nombreuses techniques à leur.
En ce qui concerne la performance, remplissez un hashset avec des mots 200K et 1 million de recherches de mots prend environ 150 ms au total sur mon ordinateur de bureau.
Tout le monde recherche dans une participation ou une trie est au moins aussi efficace. Il existe des structures de données spécialisées pour travailler avec des chaînes.
@Ivaylostrandjev Je ne dis pas que Hashset est plus efficace que les structures de données spécialisées - je dis simplement que ce sera suffisant pour l'exigence de l'OP. Cela ne vaut donc probablement pas la peine de rechercher et d'importer des bibliothèques externes ou, pire, de mettre en œuvre manuellement ces structures.
@assylie Puis-je avoir votre identifiant de messagerie ou votre twitterid.
Et qu'en est-il de la période de chargement de ces mots 200K dans ce type de structure?
Il faut moins de 1econd pour charger et vérifier chaque mot avec un hashset. Merci :-)
@Nikhil Je ne partage généralement pas mon email mais n'hésitez pas à laisser un commentaire ici.
@assylias My Mail ID est Nikhilagrawal60@gmail.com, Twitter - _nikhilagrawal
Peut-être que vous souhaitez tester mon triemap code> ou trieset code> implémentations ( trouvé ici )? Je les ai écrites spécifiquement pour des cas comme celui-ci. Jusqu'à présent, j'ai mis en œuvre des essais pour chaîne code> et octet [] code>. A: [hell, hello, helmet, help]
B: [hell, hello]
> 1,5 kloc et pas un seul test?
Ce look bien ok pour moi, je ne sais pas si je me trompe pour une raison quelconque:
//put all your words to an ArrayList and sort the list.
List <String> arr = new Arraylist<>();
while(there is next)
arr.add(theWord)
Collections.sort(arr);
//this is your search method
boolean mysearch(keyword){
return Collections.binarySearch(arr, keyword)
}
Sonne comme un HASHSET pourrait être un bon en forme.
Avez-vous une idée de l'utilisation de Lucene
@Keppil Le problème dans HashSet est qu'il n'est pas trié. Donc, la recherche sera plus lente.
@Nikhil: trouver un mot dans un
hashset esto (1) , par opposition à unarbreset , où il esto ( log n)Hashset est vraiment plus rapide. Merci
@Yavar: Je pensais que le problème est avec des millions de données ..!