Quelle structure de données utiliseriez-vous: TreeMap ou HashMap? (Java)
Description | Un programme Java pour lire un fichier texte et d'imprimer chacun des mots uniques dans l'ordre alphabétique avec le nombre de fois que le mot apparaît 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 minuscules.
Un mot ne contient aucun de ces caractères: ttn]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: Oh oui, il serait utile de montrer une implémentation utilisant l'une de ces structures (en Java).
14 réponses
TreeMap me semble une évidence-simplement à cause de l'exigence "dans l'ordre alphabétique". HashMap n'a pas d'ordre lorsque vous l'parcourez; TreeMap itère dans l'ordre de clé naturelle.
EDIT: je pense que le commentaire de Konrad a peut-être suggéré " utiliser HashMap, puis trier."C'est bien parce que même si nous aurons n itérations au départ, nous aurons K
Cela dit, Je m'en tiens à ma réponse pour le moment: parce que c'est le moyen le plus simple d'atteindre l'objectif. Nous ne savons pas vraiment que L'OP est particulièrement préoccupé par la performance, mais la question implique qu'il est préoccupé par l'élégance et la brièveté. L'utilisation d'un TreeMap rend cela incroyablement bref, ce qui me plaît. Je soupçonne que si la performance est vraiment un problème, il peut y avoir une meilleure façon de l'attaquer que TreeMap ou HashMap:)
TreeMap Bat HashMap parce que TreeMap est déjà trié pour vous.
Cependant, vous pouvez envisager d'utiliser une structure de données plus appropriée, un sac. Voir Commons Collections - et la classeTreeBag :
Cela a une belle structure interne optimisée et API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDIT: la question de la performance HashMap vs TreeMap a été répondue par Jon-HashMap 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 que d'un TreeBag. Basé sur l'implémentation (utilise un entier mutable), un sac devrait surpasser la carte simple équivalente D'entier. La seule façon de savoir à coup sûr est de tester, comme pour toute question de performance.
Je vois pas mal de gens dire "TreeMap look-up prend O(n log n)"!! Comment venir?
Je ne sais pas comment cela a été implémenté mais dans ma tête il faut O(log n).
C'est parce que la recherche dans un arbre peut être faite dans O(log n). Vous ne triez pas l'arborescence entière chaque fois que vous y insérez un élément. C'est l'idée de l'aide d'un arbre!
Par conséquent, pour revenir à la question initiale, les chiffres de comparaison se révèlent être:
Approche HashMap: O(n + k log k) Cas moyen, pire des cas pourrait être beaucoup plus
Approche TreeMap: O(k + n log k) 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 devriez pas choisir un conteneur en fonction de la façon dont vous voulez que les éléments soient arrangés éventuellement; il suffit de trier la liste des paires (mot, fréquence) à la fin. Il y aura généralement moins de paires à trier que les 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. peut être "mis" dans un TreeMap<String,Number>. Quand je "reçois" une valeur d'un Map<String,Integer>, il doit s'agir d'un Integer.
Ignorant complètement les problèmes 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());
}
}
}
" Lorsqu'une clé existe déjà, elle a les mêmes performances qu'un HashMap."- C'est tout simplement faux. HashMap A O (1) insertion et TreeMap O (N log n). Il faudra au moins n log n vérifications pour savoir si elle est dans la table!
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 utiliser HashBag de Apache Commons Collections ou HashMultiset de Guava ou HashBag de Eclipse Collections (formaly GS Collections) ou toutes 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. utilisation de 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. en utilisant LinkedHashMultiset depuis Goyave:
// 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
Plus d'exemples que vous pouvez trouver dans mes projets github
Je choisirais certainement un TreeMap:
- TreeMap trie automatiquement les nouvelles clés lors de l'insertion, aucun tri n'est nécessaire par la suite.
- Lorsqu'une clé existe déjà, elle a les mêmes performances qu'un HashMap.
Un TreeSet utilise en interne un TreeMap alors pourquoi ne pas utiliser TreeMap directement.
Considérez 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 NLN d'entrée existante, il subit également un rééquilibrage fréquent.
D'autre part, les structures de hachage sont peu flamboyantes sur la mémoire (sur allocates). Si vous pouvez mordre cette balle, optez pour la structure de hachage et le tri si nécessaire.
Voici l'exemple java pour la lecture d'un fichier texte, le tri basé sur la touche, puis sur les valeurs en fonction du nombre d'occurrence des mots 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 d'ordre qu'un 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 la description de votre problème, il semble que vous ayez besoin d'un ensemble, Je ne vois pas quelles clés et quelles valeurs vous mappez ensemble.
Cette classe implémente L'interface Set, soutenue par une instance TreeMap. Cette classe garantit que l'ensemble trié sera dans l'ordre croissant des éléments, triés selon l'ordre naturel des éléments (Voir Comparable), ou par le comparateur fourni au moment de la création de l'ensemble, en fonction du constructeur utilisé.
Fondamentalement, cela dépend de l'exigence. Parfois, la carte de hachage est bonne parfois treemap. mais la carte de hachage est préférable d'utiliser uniquement leur contrainte pour les frais généraux pour le trier.