Quelle structure de données utiliseriez-vous: TreeMap ou HashMap? (Java)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Description | Programme Java permettant de lire un fichier texte et d'imprimer chacun des mots uniques dans l'ordre alphabétique, ainsi que le nombre d'occurrences de ce mot dans le texte.
Le programme doit déclarer une variable de type Map<String, Integer> pour stocker les mots et la fréquence d'occurrence correspondante. Quel type de béton, cependant? TreeMap<String, Number> ou HashMap<String, Number>?
L'entrée doit être convertie en minuscule.
Un mot ne contient aucun de ces caractères: \t\t\n]f.,!?:;\"()'
Exemple de sortie |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
Remarque | Je sais, j'ai vu des solutions élégantes à cela en Perl avec environ deux lignes de code. Cependant, je veux le voir en Java.
Edit: Ah oui, il serait utile de montrer une implémentation en utilisant l’une de ces structures (en Java).
La solution
TreeMap semble aller de soi pour moi - simplement à cause de & "dans l'ordre alphabétique &"; exigence. HashMap n'a pas d'ordres lorsque vous le parcourez. TreeMap effectue une itération dans l'ordre des clés naturelles.
EDIT: Je pense que le commentaire de Konrad suggérait peut-être & "utiliser HashMap, puis trier. &"; C’est bien parce que même si nous aurons initialement N itérations, nous aurons K & Lt; = N clés d’ici la fin en raison des doublons. Nous pourrions aussi bien économiser le tri coûteux jusqu'à la fin, lorsque nous aurons moins de clés que le simple mais non constant problème consistant à le garder trié au fur et à mesure.
Cela étant dit, je m'en tiens à ma réponse pour le moment: parce que c'est la manière la plus simple d'atteindre le but. Nous ne savons pas vraiment que le PO est particulièrement préoccupé par les performances, mais la question implique qu'il est préoccupé par l'élégance et la brièveté. Utiliser une TreeMap rend cela incroyablement bref, ce qui me plaît. Je pense que si les performances sont réellement un problème, il peut exister un meilleur moyen de les attaquer que TreeMap ou HashMap:)
Autres conseils
TreeMap bat HashMap car TreeMap est déjà trié pour vous.
Cependant, vous pouvez envisager d’utiliser une structure de données plus appropriée, un sac. Voir Collections communes - et le TreeBag classe:
Cela a une belle structure interne optimisée et une API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDIT: Jon - HashMap a répondu à la question des performances de HashMap vs TreeMap et le tri peut être plus rapide (essayez-le!), mais TreeBag est plus facile. La même chose est vraie pour les sacs. Il y a un HashBag ainsi qu'un TreeBag. Sur la base de la mise en œuvre (utilise un entier mutable), un sac doit être plus performant que la carte simple équivalente d'Integer. Le seul moyen de savoir avec certitude est de tester, comme pour toute question de performance.
Je vois pas mal de gens dire que & "La recherche TreeMap prend O(n log n) &"! Comment venir?
Je ne sais pas comment cela a été mis en œuvre, mais dans ma tête, cela prend O(log n).
En effet, la recherche dans un arbre peut être effectuée dans O(n + k log k). Vous ne triez pas tout l’arbre chaque fois que vous y insérez un élément. C'est l'idée d'utiliser un arbre!
Ainsi, pour revenir à la question initiale, les chiffres de comparaison se révèlent être les suivants:
Approche HashMap: O(k + n log k) cas moyen, le pire des cas pourrait être beaucoup plus volumineux
Approche TreeMap: <=> dans le pire des cas
où n = nombre de mots dans le texte, k = nombre de mots distincts dans le texte.
La carte de hachage devrait être beaucoup plus rapide. Vous ne devez pas choisir un conteneur en fonction de la manière dont vous souhaitez organiser les éléments à terme; Il suffit de trier la liste des paires (mot, fréquence) à la fin. Il y aura généralement moins de paires à classer que de mots dans les fichiers, donc les performances asymptotiques (et réelles) avec une carte de hachage seront meilleures.
Vous ne pouvez pas affecter un TreeMap<String,Number> à une variable de type Map<String,Integer>. Double, Long, etc. peuvent être & "mettre &"; dans un Integer. Quand je & Quot; reçois & Quot; une valeur parmi <=>, il doit s'agir d'un <=>.
En ignorant complètement les problèmes liés à i18n, les contraintes de mémoire et la gestion des erreurs, voici:
class Counter {
public static void main(String... argv)
throws Exception
{
FileChannel fc = new FileInputStream(argv[0]).getChannel();
ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
CharBuffer cb = Charset.defaultCharset().decode(bb);
Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
Map<String, Integer> counts = new TreeMap<String, Integer>();
Matcher m = p.matcher(cb);
while (m.find()) {
String word = m.group();
Integer count = counts.get(word);
count = (count == null) ? 1 : count + 1;
counts.put(word, count);
}
fc.close();
for (Map.Entry<String, Integer> e : counts.entrySet()) {
System.out.printf("%s: %d%n", e.getKey(), e.getValue());
}
}
}
& "Quand une clé existe déjà, elle a les mêmes performances qu'un HashMap. &"; - C'est tout simplement faux. HashMap a une insertion O (1) et TreeMap O (n log n). Il faudra au moins n journaux et vérifications pour savoir s’il se trouve dans le tableau!
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class TreeMapExample {
public static void main (String args[]){
Map<String,Integer> tm = new TreeMap<String,Integer>();
try {
FileInputStream fis = new FileInputStream("Test.txt");
DataInputStream in = new DataInputStream(fis);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String line;
int countValue = 1;
while((line = br.readLine())!= null ){
line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
StringTokenizer st = new StringTokenizer(line, " ");
while(st.hasMoreTokens()){
String nextElement = (String) st.nextElement();
if(tm.size()>0 && tm.containsKey(nextElement)){
int val = 0;
if(tm.get(nextElement)!= null){
val = (Integer) tm.get(nextElement);
val = val+1;
}
tm.put(nextElement, val);
}else{
tm.put(nextElement, 1);
}
}
}
for(Map.Entry<String,Integer> entry : tm.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Pour cette façon, à mon avis, mieux vaut utiliser HashBag de Collections Apache Commons ou HashMultiset de Goyave ou HashBag à partir de Collections Eclipse (officiellement collections GS ) ou les classes suivantes:
Order | Guava | Apache | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define | HashMultiset | HashBag | HashBag | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted | TreeMultiset | TreeBag | TreeBag | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked |LinkedHashMultiset| - | - | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash- |Synchroniz-|Synchroniz- | Collections.synchronizedMap(
not define | Multiset | edBag | edBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent | - |Synchroniz-|Synchroniz- | Collections.synchronizedSorted-
and sorted | |edSortedBag| edSortedBag | Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab- | Collections.unmodifiableMap(
not define | | leBag | leBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab- | Collections.unmodifiableSorted-
sorted | Multiset |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────
Exemples:
1. SynchronizedSortedBag à partir d'Apache :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));
// Print count words
System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
// Print all unique words
System.out.println(bag.uniqueSet()); // print [All!, Hello, Hi, World!]- in natural (alphabet) order
// Print count occurrences of words
System.out.println("Hello = " + bag.getCount("Hello")); // print 2
System.out.println("World = " + bag.getCount("World!")); // print 2
System.out.println("All = " + bag.getCount("All!")); // print 1
System.out.println("Hi = " + bag.getCount("Hi")); // print 1
System.out.println("Empty = " + bag.getCount("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.uniqueSet().size()); //print 4
2. Utilisation de TreeBag à partir d’Eclipse (GC) :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
MutableSortedBag<String> bag = TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
// Print all unique words
System.out.println(bag.toSortedSet()); // print [All!, Hello, Hi, World!]- in natural order
// Print count occurrences of words
System.out.println("Hello = " + bag.occurrencesOf("Hello")); // print 2
System.out.println("World = " + bag.occurrencesOf("World!")); // print 2
System.out.println("All = " + bag.occurrencesOf("All!")); // print 1
System.out.println("Hi = " + bag.occurrencesOf("Hi")); // print 1
System.out.println("Empty = " + bag.occurrencesOf("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.toSet().size()); //print 4
3. LinkedHashMultiset de Guava :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
// Print all unique words
System.out.println(multiset.elementSet()); // print [Hello, World!, All!, Hi] - in predictable iteration order
// Print count occurrences of words
System.out.println("Hello = " + multiset.count("Hello")); // print 2
System.out.println("World = " + multiset.count("World!")); // print 2
System.out.println("All = " + multiset.count("All!")); // print 1
System.out.println("Hi = " + multiset.count("Hi")); // print 1
System.out.println("Empty = " + multiset.count("Empty")); // print 0
// Print count all words
System.out.println(multiset.size()); //print 6
// Print count unique words
System.out.println(multiset.elementSet().size()); //print 4
Plusieurs exemples possibles trouver dans mes projets github
Je choisirais certainement une TreeMap:
- TreeMap trie automatiquement les nouvelles clés à l’insertion, aucun tri ultérieur n’est nécessaire.
- Quand une clé existe déjà, elle a les mêmes performances qu'un HashMap.
Un TreeSet utilise en interne une TreeMap, alors pourquoi ne pas utiliser TreeMap directement.
En fonction de la vitesse requise, vous pouvez également utiliser un Trie . Mais il ne sert à rien d’en implémenter une si TreeMap est assez rapide.
considérons la fréquence d’ajout ou de suppression à la structure de données. TreeMap ne serait pas idéal s'il est élevé. Outre la recherche de l'entrée existante nLn, il subit également un rééquilibrage fréquent.
Par contre, les structures de hachage sont un peu flamboyantes en mémoire (sur-alloue). Si vous pouvez mordre la balle, optez pour la structure de hachage et triez-la si nécessaire.
Voici l'exemple Java pour la lecture d'un fichier texte, le tri basé sur la clé, puis sur les valeurs; en fonction du nombre d'occurrences d'un mot dans le fichier.
public class SortFileWords {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
ValueCompare vc = new ValueCompare(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
List<String> list = new ArrayList<>();
Scanner sc;
try {
sc = new Scanner(new File("c:\\ReadMe1.txt"));
while (sc.hasNext()) {
list.add(sc.next());
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
for (String s : list) {
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else
map.put(s, 1);
}
System.out.println("Unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("Sorted map on keys: " + sorted_map);
TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
sorted_value_map.putAll(map);
System.out.println("Sorted map on values: " + sorted_value_map);
}
}
class ValueCompare implements Comparator<String> {
Map<String, Integer> map;
public ValueCompare(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String s1, String s2) {
if (map.get(s1) >= map.get(s2))
return -1;
else
return 1;
}
}
Pourquoi ne pas utiliser TreeSet ?
Même concept de tri qu'une TreeMap, sauf qu'il s'agit d'un ensemble - qui, par définition, est & "Une collection qui ne contient aucun élément dupliqué &";
D'après votre description du problème, il semble que vous ayez besoin d'un ensemble. Je ne vois pas quelles clés et quelles valeurs vous associez.
Cette classe implémente l'interface Set, appuyée par une instance TreeMap. Cette classe garantit que le jeu trié sera dans l’ordre croissant des éléments, trié selon l’ordre naturel des éléments (voir Comparable) ou par le comparateur fourni au moment de la création du jeu, en fonction du constructeur utilisé.
Cela dépend essentiellement de l'exigence. Parfois, la carte de hachage est parfois bonne. mais hash map est préférable d’utiliser uniquement une contrainte de surcharge pour le trier.
