Quale struttura di dati useresti: TreeMap o HashMap? (Giava)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Descrizione | Un programma Java per leggere un file di testo e stampare ciascuna delle parole univoche in ordine alfabetico insieme al numero di volte in cui la parola compare nel testo.
Il programma dovrebbe dichiarare una variabile di tipo Map<String, Integer> per memorizzare le parole e la corrispondente frequenza di occorrenza. Quale tipo concreto, però? TreeMap<String, Number> o HashMap<String, Number>?
L'input deve essere convertito in minuscolo.
Una parola non contiene nessuno di questi caratteri: \t\t\n]f.,!?:;\"()'
Esempio di output |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
Nota | Lo so, ho visto soluzioni eleganti a questo in Perl con circa due righe di codice. Tuttavia, voglio vederlo in Java.
Modifica: Oh sì, può essere utile mostrare un'implementazione usando una di queste strutture (in Java).
Soluzione
TreeMap sembra un gioco da ragazzi per me - semplicemente a causa del " in ordine alfabetico " Requisiti. HashMap non ha ordini quando si scorre attraverso di esso; TreeMap scorre nell'ordine delle chiavi naturale.
EDIT: penso che il commento di Konrad potrebbe aver suggerito " usa HashMap, quindi ordina. " Questo è utile perché sebbene inizialmente avremo N iterazioni, alla fine avremo K & Lt; = N chiavi a causa dei duplicati. Potremmo anche salvare il bit costoso (ordinamento) fino alla fine quando abbiamo meno chiavi rispetto al colpo piccolo ma non costante di mantenerlo ordinato mentre andiamo.
Detto questo, per il momento mi attengo alla mia risposta: perché è il modo più semplice di raggiungere l'obiettivo. Non sappiamo davvero che l'OP sia particolarmente preoccupato per le prestazioni, ma la domanda implica che sia preoccupato per l'eleganza e la brevità. L'uso di una TreeMap lo rende incredibilmente breve, il che mi piace. Ho il sospetto che se le prestazioni sono davvero un problema, potrebbe esserci un modo migliore per attaccarlo rispetto a TreeMap o HashMap :)
Altri suggerimenti
TreeMap batte HashMap perché TreeMap è già in ordine per te.
Tuttavia, potresti prendere in considerazione l'utilizzo di una struttura dati più appropriata, una borsa. Vedere Collezioni comuni - e il TreeBag classe:
Questa ha una struttura interna e un'API ottimizzate:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDIT: Jon - HashMap ha risposto alla domanda HashMap vs TreeMap e l'ordinamento potrebbe essere più veloce (provalo!), ma TreeBag è più semplice. Lo stesso vale per le borse. C'è un HashBag e un TreeBag. In base all'implementazione (utilizza un intero mutabile) un sacchetto dovrebbe superare la mappa normale equivalente di Integer. L'unico modo per saperlo con certezza è testare, come per qualsiasi domanda relativa alle prestazioni.
Vedo alcune persone che dicono " La ricerca TreeMap richiede O(n log n) " !! Come mai?
Non so come sia stato implementato ma nella mia testa ci vogliono O(log n).
Questo perché la ricerca in un albero può essere effettuata in O(n + k log k). Non si ordina l'intero albero ogni volta che si inserisce un elemento in esso. Questa è l'idea di usare un albero!
Quindi, tornando alla domanda originale, le cifre per il confronto risultano essere:
Approccio HashMap: O(k + n log k) caso medio, il caso peggiore potrebbe essere molto più grande
Approccio TreeMap: <=> caso peggiore
dove n = numero di parole nel testo, k = numero di parole distinte nel testo.
La mappa hash dovrebbe essere molto più veloce. Non si dovrebbe scegliere un contenitore in base a come si desidera che gli articoli vengano disposti alla fine; Basta ordinare l'elenco di (word, frequency) -pairs alla fine. Di solito ci saranno meno coppie di questo tipo da ordinare rispetto alle parole nei file, quindi le prestazioni asintotiche (e reali) con una mappa hash saranno migliori.
Non puoi assegnare un TreeMap<String,Number> a una variabile con il tipo Map<String,Integer>. Double, Long, ecc. possono essere " put " in un Integer. Quando & Quot; ottengo & Quot; un valore compreso tra <=>, deve essere <=>.
Ignorando completamente eventuali problemi di i18n, vincoli di memoria e gestione degli errori, ecco:
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());
}
}
}
" Quando una chiave esiste già, ha le stesse prestazioni di una HashMap. " - È semplicemente sbagliato. HashMap ha l'inserimento di O (1) e TreeMap O (n log n). Ci vorranno almeno n log n controlli per scoprire se è nella tabella!
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();
}
}
}
In questo modo, a mio avviso, è meglio usare HashBag da Collezioni Apache Commons o HashMultiset da Guava o HashBag da Collezioni Eclipse (formaly Collezioni GS ) o qualsiasi delle seguenti classi:
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>))
────────────────────────────────────────────────────────────────────────
Esempi:
1. Utilizzo SynchronizedSortedBag di 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. Utilizzo di TreeBag da 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. Utilizzo LinkedHashMultiset di 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
Altri esempi che puoi trova nei miei progetti github
Sceglierei sicuramente una TreeMap:
- TreeMap ordina automaticamente le nuove chiavi all'inserimento, non è necessario alcun ordinamento in seguito.
- Quando una chiave esiste già, ha le stesse prestazioni di una HashMap.
Un TreeSet utilizza internamente una TreeMap, quindi perché non usare direttamente TreeMap.
A seconda di quali sono i requisiti di velocità, puoi anche utilizzare un Trie . Ma non ha senso implementare uno di questi se una TreeMap è abbastanza veloce.
considera la frequenza di aggiunta o eliminazione della struttura dei dati. TreeMap non sarebbe l'ideale se è alto. Oltre alla ricerca di voci esistenti nLn subisce anche frequenti riequilibri.
d'altra parte le strutture di hash sono un po 'sgargianti in memoria (oltre alloca). Se riesci a mordere quel proiettile, scegli la struttura hash e ordina quando richiesto.
Ecco l'esempio java per la lettura di un file di testo, l'ordinamento basato sulla chiave, quindi sui valori; a seconda del numero di occorrenze di una parola nel file.
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;
}
}
Perché non usare TreeSet ?
Stesso concetto di ordinamento di una TreeMap, tranne per il fatto che è un Set - che, per definizione, è " Una raccolta che non contiene elementi duplicati " ;.
Dalla descrizione del tuo problema, sembra che tu abbia bisogno di un Set, non vedo quali chiavi e valori stai mappando insieme.
Questa classe implementa l'interfaccia Set, supportata da un'istanza TreeMap. Questa classe garantisce che l'insieme ordinato sarà in ordine crescente di elementi, ordinato secondo l'ordine naturale degli elementi (vedi Comparable) o dal comparatore fornito al momento della creazione dell'insieme, a seconda del costruttore utilizzato.
Fondamentalmente dipende dal requisito. A volte la mappa hash è buona a volte treemap. ma la mappa hash è meglio usare solo il loro è un vincolo per l'overhead per ordinarla.
