Welche Datenstruktur würden Sie: TreeMap oder HashMap? (Java)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Beschreibung | Ein Java-Programm eine Textdatei und druckt jede der eindeutigen Worte in alphabetischer Reihenfolge zusammen mit der Anzahl, wie oft zu lesen, das Wort im Text vorkommt.
Das Programm sollte eine Variable vom Typ Map<String, Integer> erklärt die Worte und entsprechende Häufigkeit des Auftretens zu speichern. Welche konkreten Typ, obwohl? TreeMap<String, Number> oder HashMap<String, Number>?
Der Eingang sollte in Kleinbuchstaben umgewandelt werden.
Ein Wort enthält keine dieser Zeichen: \t\t\n]f.,!?:;\"()'
Beispiel Ausgabe |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
Hinweis | Ich weiß, ich habe mit rund zwei Zeilen Code elegante Lösungen für diesen in Perl gesehen. Allerdings mag ich es in Java sehen.
Edit: Ach ja, es hilfreich sein, eine Implementierung zu zeigen, mit einem der folgenden Strukturen (in Java).
Lösung
TreeMap scheint ein Kinderspiel ich - einfach wegen der „in alphabetischer Reihenfolge“ Anforderung. HashMap hat keine Ordnung, wenn man durch sie durchlaufen; TreeMap Iterierten in der natürlichen Reihenfolge des Schlüssels.
EDIT: Ich denke, Konrads Kommentar wurde darauf hindeutet „HashMap verwenden, dann sortieren.“ Das ist gut, denn obwohl wir N Iterationen haben zunächst, wir werden K haben <= N Tasten am Ende aufgrund von Duplikaten. Wir könnten sparen als auch die teure Bit (Sortierung) bis zum Ende, wenn wir haben weniger Tasten als nehmen Sie die kleine-but-nicht-ständigen Hit zu halten es sortiert, wie wir gehen.
Having said that, ich bleibe auf meine Antwort für den Moment: weil es der ist einfachste Weg, um das Ziel zu erreichen. Wir wissen nicht wirklich, dass der OP ist besonders besorgt über die Leistung, aber die Frage impliziert, dass er über die Eleganz und Kürze betroffen ist. ein TreeMap Mit macht diese unglaublich kurz, was mir gefällt. Ich vermute, dass, wenn die Leistung wirklich ein Problem ist, kann es ein besserer Weg, es anzugreifen, als entweder TreeMap oder HashMap:)
Andere Tipps
TreeMap schlägt HashMap weil TreeMap bereits für Sie sortiert ist.
Allerdings mögen Sie vielleicht mit einer geeigneteren Datenstruktur zu prüfen, einen Beutel. Sehen Commons Sammlungen - und die TreeBag Klasse:
Dies hat eine schöne optimierte interne Struktur und API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDIT: Die Frage der HashMap vs TreeMap Leistung von Jon beantwortet wurde - HashMap und Art sein kann schneller (versuchen Sie es!), Aber TreeBag ist einfacher. Das gleiche gilt für Taschen. Es gibt eine HashBag sowie ein TreeBag. Auf der Basis der Implementierung (verwendet eine veränderliche ganze Zahl ist) eine Tasche soll die äquivalente Ebene Karte von Integer übertreffen. Der einzige Weg, um sicher zu wissen ist zu prüfen, wie bei jeder Leistung Frage.
Ich sehe durchaus ein paar Leute, die sagen "TreeMap Look-up nimmt O(n log n)" !! Woher?
Ich weiß nicht, wie es umgesetzt wurde, aber in meinem Kopf dauert es O(log n).
Dies liegt daran, Look-up in einem Baum kann in O(log n) erfolgen. Sie müssen nicht den gesamten Baum in es jedes Mal, sortieren Sie ein Element einzufügen. Das ist die ganze Idee, einen Baum zu verwenden!
Daher auf die ursprüngliche Frage zurückgehen, werden die Zahlen zum Vergleich heraus sein:
HashMap Ansatz: O(n + k log k) durchschnittlicher Fall könnte schlimmstenfalls viel größer sein
TreeMap Ansatz: O(k + n log k) worst case
wobei n = Anzahl der Wörter im Text, k = Anzahl der verschiedenen Wörter im Text.
Hash Karte sollte viel schneller sein. Sie sollten nicht einen Container wählen, basierend auf, wie Sie wollen, dass die Gegenstände schließlich angeordnet werden; sortieren, einfach die Liste von (Wort, Frequenz) -Paare am Ende. Es wird in der Regel weniger solche Paare als Worte in den Dateien sortiert werden, so asymptotisch (und real) Leistung mit einer Hash-Karte besser sein wird.
Sie können keine TreeMap<String,Number> auf eine Variable mit dem Typ Map<String,Integer> zuweisen. Double, Long usw. sein "put" in eine TreeMap<String,Number>. Als ich „get“ einen Wert von einem Map<String,Integer>, muss es eine Integer sein.
Completely alle i18n Probleme, Speicherbeschränkungen zu ignorieren, und die Fehlerbehandlung, hier geht:
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());
}
}
}
„Wenn bereits ein Schlüssel existiert es hat die gleiche Leistung wie eine HashMap.“ - Das ist einfach falsch. HashMap hat O (1) Einführen und TreeMap O (n log n). Es wird zumindest nehmen n log n überprüft, um herauszufinden, ob es in der Tabelle ist!
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();
}
}
}
Für diese Art und Weise, meiner Meinung nach, eine bessere Nutzung HashBag von Apache Commons Sammlungen oder HashMultiset Guava oder HashBag von eclipse-Collections (formaly GS Sammlungen ) oder alle folgenden Klassen:
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>))
────────────────────────────────────────────────────────────────────────
Beispiele:
1. Verwendung SynchronizedSortedBag von 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
Verwendung LinkedHashMultiset von 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
Weitere Beispiele können Sie finden in meinem gitHub Projekte
ich wählen würde auf jeden Fall eine TreeMap:
- TreeMap sortiert automatisch neuen Schlüssel beim Einsetzen, danach keine Sortierung erforderlich ist.
- Wenn ein Schlüssel bereits vorhanden ist es die gleiche Leistung wie eine HashMap hat.
Ein TreeSet intern verwendet einen TreeMap warum also nicht TreeMap direkt verwenden.
Je nachdem, was die Geschwindigkeitsanforderungen sind, könnten Sie auch einen Trie . Aber es hat keinen Sinn, einer von denen bei der Umsetzung, wenn ein TreeMap schnell genug ist.
die Häufigkeit der Addition oder Deletion auf die Datenstruktur in Betracht ziehen. TreeMap wäre nicht ideal, wenn es hoch ist. Neben der Suche nach vorhandenen Eintrag nln es erfährt auch häufigen Rebalancing.
Auf der anderen Seite Hash-Strukturen auf Merkers flamboyant sind (über zuordnet). Wenn Sie diese Kugel beißen können dann für die Hash-Struktur gehen und zu sortieren, wenn erforderlich.
Dies ist das Java-Beispiel eine Textdatei zum Lesen, basierend auf Schlüssel Sortierung, dann auf Werte; abhängig von der Anzahl des Auftretens von Worten in der Datei.
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;
}
}
Warum nicht benutzen TreeSet ?
Die gleiche Ordnungskonzept als TreeMap, außer es ist ein Set - die per definitionem „Eine Sammlung, die keine doppelten Elemente enthält“ ist.
Von der Problembeschreibung, es klingt, als ob Sie ein Set benötigen, sehe ich nicht, welche Schlüssel und Werte, die Sie zuordnen zusammen.
Diese Klasse implementiert die Set-Schnittstelle, durch eine TreeMap Instanz gesichert. Diese Klasse garantiert, dass der Satz sortiert in aufsteigender Reihenfolge der Elemente sein, die natürliche Reihenfolge der Elemente entsprechend sortiert (siehe Vergleichbare) oder durch den Komparator zu festgelegten Erstellungszeit vorgesehen ist, je nachdem, welche Konstruktor verwendet wird.
Grundsätzlich hängt es von der Anforderung. Manchmal Hash-Karte ist gut manchmal treemap. aber Hash-Karte ist besser nur nutzen, um ihre einige Einschränkung für Overhead zu sortieren.
