Qual estrutura de dados você usaria: TreeMap ou HashMap? (Java)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Descrição | Um programa Java para ler um arquivo de texto e imprimir cada uma das palavras únicas em ordem alfabética juntamente com o número de vezes que a palavra aparece no texto.
O programa deve declarar uma variável do tipo Map<String, Integer> para armazenar as palavras e correspondente frequência de ocorrência. Que tipo de concreto, embora? TreeMap<String, Number> ou HashMap<String, Number>?
A entrada deve ser convertido para minúsculas.
Uma palavra não contém qualquer um desses caracteres: \t\t\n]f.,!?:;\"()'
Exemplo de saída |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
Observação | Eu sei, eu vi soluções elegantes para isso em Perl com cerca de duas linhas de código. No entanto, eu quero vê-lo em Java.
Edit: Oh sim, é ser útil para mostrar uma implementação usando uma dessas estruturas (em Java).
Solução
TreeMap parece um acéfalo para mim - simplesmente por causa da exigência "em ordem alfabética". HashMap não tem nenhuma ordenação quando você iterar através dele; TreeMap repete na ordem da chave natural.
EDIT: Eu acho que o comentário de Konrad pode ter sido sugerindo "uso HashMap, em seguida, classificar." Isso é bom porque, embora teremos iterações N inicialmente, teremos K <= N chaves no final devido a duplicações. Nós também podemos salvar o pouco caro (triagem) até o final quando temos menos teclas de tomar o hit pequeno-mas-não-constante de mantê-lo classificado como vamos nós.
Dito isso, eu estou aderindo a minha resposta para o momento: porque é a simples maneira de alcançar a meta. Nós realmente não sei o que o OP é particularmente preocupado com o desempenho, mas a questão implica que ele está preocupado com a elegância e concisão. Usando um TreeMap faz este breve incrivelmente, o que me atrai. Eu suspeito que se o desempenho é realmente um problema, pode haver uma maneira melhor de atacá-lo do que qualquer um TreeMap ou HashMap:)
Outras dicas
TreeMap bate HashMap porque TreeMap já está classificado para você.
No entanto, você pode querer considerar o uso de uma estrutura de dados mais apropriado, um saco. Vejo Commons Collections - e o TreeBag classe:
Este tem um bom otimizado estrutura interna e API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDIT: A questão da HashMap vs desempenho TreeMap foi respondido por Jon - HashMap e meio pode ser mais rápido (tentar!), Mas TreeBag é mais fácil. O mesmo é verdadeiro para sacos. Há uma HashBag, bem como um TreeBag. Com base na execução (usa um número inteiro mutável) um saco deve superar o mapa simples equivalente de Integer. A única maneira de saber ao certo se a teste, como acontece com qualquer questão de desempenho.
Eu vejo algumas pessoas dizendo "TreeMap look-up leva O(n log n)" !! Por quê?
Eu não sei como ela foi implementada, mas na minha cabeça que leva O(log n).
Isto porque look-up em uma árvore pode ser feito em O(log n). Você não tipo toda a árvore de cada vez que você inserir um item na mesma. Essa é toda a idéia de usar uma árvore!
Por isso, de volta à pergunta original indo, os números para comparação vir a ser:
abordagem HashMap: O(n + k log k) caso médio, pior caso poderia ser muito maior
abordagem TreeMap: O(k + n log k) pior dos casos
onde n = número de palavras do texto, k = número de palavras distintas no texto.
mapa Hash deve ser muito mais rápido. Você não deve escolher um recipiente com base em como você deseja que os itens a serem organizados, eventualmente; Apenas uma espécie da lista de (word, frequência) -pairs no final. Haverá geralmente menos tais pares de ser classificadas do que palavras nos arquivos, o desempenho de modo assintótica (e real) com um mapa de hash será melhor.
Você não pode atribuir um TreeMap<String,Number> a uma variável com o tipo Map<String,Integer>. Double, Long, etc. pode ser "put" em um TreeMap<String,Number>. Quando eu "pegar" um valor de uma Map<String,Integer>, ele deve ser um Integer.
Ignorando completamente quaisquer problemas de i18n, restrições de memória e tratamento de erros, aqui vai:
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 uma chave já existe tem o mesmo desempenho de um HashMap." - Isso é simplesmente errado. HashMap tem ó (1) de inserção e TreeMap O (N log N). Vai demorar pelo menos n log n verificações para saber se ele está em cima da mesa!
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();
}
}
}
Por este caminho, na minha opinião, a melhor utilização HashBag de Apache Commons Collections ou HashMultiset Goiaba ou HashBag de Eclipse coleções (formaly GS coleções ) ou quaisquer seguintes classes:
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>))
────────────────────────────────────────────────────────────────────────
Exemplos:
1. Usando SynchronizedSortedBag de 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. Usando TreeBag de 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. Usando LinkedHashMultiset de goiaba :
// 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
Mais exemplos que você pode encontrar em meus projetos github
Eu definitivamente escolher um TreeMap:
- TreeMap classifica automaticamente novas chaves sobre a inserção, sem ordenação depois é necessário.
- Quando uma chave já existe tem o mesmo desempenho de um HashMap.
A TreeSet usa internamente um TreeMap então porque não usar TreeMap diretamente.
Dependendo do que os requisitos de velocidade são, você também pode usar um Trie . Mas não há nenhum ponto na implementação de um daqueles se um TreeMap é suficiente rápido.
considerar a frequência de adição ou supressão à estrutura de dados. TreeMap não seria ideal se é alta. Além da busca de entrada NLN também sofre reequilíbrio frequente existente.
sobre as outras estruturas Hash lado, são pouco flamboyant na memória (mais aloca). Se você pode morder a bala, em seguida, ir para a estrutura de hash e de classificação, quando necessário.
Aqui está o exemplo java para ler um arquivo de texto, a triagem com base na chave, em seguida, em valores; dependendo do número de ocorrência de algumas palavras no arquivo.
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;
}
}
Por que não usar TreeSet ?
conceito ordenação mesmo que um TreeMap, exceto que é um Set - que, por definição, é "uma coleção que não contém elementos duplicados".
A partir da sua descrição do problema, soa como se você precisa de um set, eu não vejo o que as chaves e valores que você está mapeando juntos.
Esta classe implementa a interface Set, apoiado por uma instância TreeMap. Esta classe garante que o conjunto classificado serão em ordem ascendente elemento, classificados de acordo com a ordem natural dos elementos (ver Comparável), ou pelo comparador fornecida no momento da criação conjunto, dependendo de qual é utilizado construtor.
Basicamente, depende da exigência. Às vezes, mapa de hash é bom às vezes treemap. mas mapa de hash é melhor usar apenas a sua é alguma restrição para cima para classificá-lo.
