¿Qué estructura de datos usarías: TreeMap o HashMap? (Java)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Descripción | Un programa Java para leer un archivo de texto e imprimir cada una de las palabras únicas en orden alfabético junto con la cantidad de veces que la palabra aparece en el texto.
El programa debe declarar una variable de tipo Map<String, Integer> para almacenar las palabras y la frecuencia correspondiente de ocurrencia. ¿Qué tipo de hormigón, sin embargo? TreeMap<String, Number> o HashMap<String, Number>?
La entrada debe convertirse a minúsculas.
Una palabra no contiene ninguno de estos caracteres: \t\t\n]f.,!?:;\"()'
Ejemplo de salida |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
Observación | Lo sé, he visto soluciones elegantes para esto en Perl con aproximadamente dos líneas de código. Sin embargo, quiero verlo en Java.
Editar: Ah, sí, sería útil mostrar una implementación utilizando una de estas estructuras (en Java).
Solución
TreeMap parece obvio para mí, simplemente por el " en orden alfabético " requisito. HashMap no tiene orden cuando itera a través de él; TreeMap itera en el orden de las claves naturales.
EDITAR: Creo que el comentario de Konrad puede haber sugerido & "; use HashMap, luego ordene. &"; Esto es bueno porque aunque inicialmente tendremos N iteraciones, tendremos K & Lt; = N claves al final debido a duplicados. También podríamos guardar el bit costoso (clasificación) hasta el final cuando tengamos menos claves que tomar el golpe pequeño pero no constante de mantenerlo ordenado a medida que avanzamos.
Habiendo dicho eso, me quedo con mi respuesta por el momento: porque es la forma más simple de lograr el objetivo. Realmente no sabemos que el OP está particularmente preocupado por el rendimiento, pero la pregunta implica que está preocupado por la elegancia y la brevedad. Usar un TreeMap hace que esto sea increíblemente breve, lo que me atrae. Sospecho que si el rendimiento es realmente un problema, puede haber una mejor manera de atacarlo que TreeMap o HashMap :)
Otros consejos
TreeMap supera a HashMap porque TreeMap ya está ordenado por ti.
Sin embargo, es posible que desee considerar el uso de una estructura de datos más apropiada, una bolsa. Ver Colecciones comunes - y el Clase TreeBag :
Esto tiene una buena estructura interna optimizada y API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDITAR: Jon - HashMap respondió la pregunta sobre el rendimiento de HashMap vs TreeMap y la clasificación puede ser más rápida (¡pruébalo!), pero TreeBag es más fácil. Lo mismo es cierto para las bolsas. Hay un HashBag y un TreeBag. Según la implementación (usa un número entero mutable), una bolsa debería superar el mapa plano equivalente de número entero. La única forma de saberlo con certeza es mediante una prueba, como con cualquier pregunta de rendimiento.
¡Veo algunas personas que dicen " ¡La búsqueda de TreeMap requiere O(n log n) " !! ¿Cómo?
No sé cómo se ha implementado, pero en mi cabeza se necesita O(log n).
Esto se debe a que la búsqueda en un árbol se puede hacer en O(n + k log k). No clasifica todo el árbol cada vez que inserta un elemento en él. ¡Esa es toda la idea de usar un árbol!
Por lo tanto, volviendo a la pregunta original, las cifras de comparación resultan ser:
Enfoque HashMap: O(k + n log k) caso promedio, el peor de los casos podría ser mucho más grande
Enfoque de TreeMap: <=> peor de los casos
donde n = número de palabras en el texto, k = número de palabras distintas en el texto.
El mapa hash debería ser mucho más rápido. No debe elegir un contenedor en función de cómo desea que se organicen los artículos eventualmente; Simplemente ordene la lista de pares (palabra, frecuencia) al final. Por lo general, habrá menos pares de ordenadas que palabras en los archivos, por lo que el rendimiento asintótico (y real) con un mapa hash será mejor.
No puede asignar un TreeMap<String,Number> a una variable con el tipo Map<String,Integer>. Double, Long, etc. pueden ser " poner " en un Integer. Cuando yo & Quot; obtener & Quot; un valor de un <=>, debe ser un <=>.
Ignorando completamente cualquier problema de i18n, restricciones de memoria y manejo de errores, aquí va:
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());
}
}
}
" Cuando ya existe una clave, tiene el mismo rendimiento que un HashMap. " - Eso es simplemente incorrecto. HashMap tiene inserción O (1) y TreeMap O (n log n). ¡Se necesitarán al menos n log n cheques para saber si está en la tabla!
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();
}
}
}
Para esta forma, en mi opinión, mejor uso HashBag de Apache Commons Collections o HashMultiset de Guava o HashBag de Eclipse Collections (formaly GS Collections ) o cualquiera de las siguientes clases:
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>))
────────────────────────────────────────────────────────────────────────
Ejemplos:
1. Uso 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. Uso 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
Más ejemplos que puede encontrar en mis proyectos github
Definitivamente elegiría un TreeMap:
- TreeMap clasifica automáticamente las nuevas claves en la inserción, no es necesario ordenarlas posteriormente.
- Cuando ya existe una clave, tiene el mismo rendimiento que un HashMap.
Un TreeSet usa internamente un TreeMap, entonces ¿por qué no usar TreeMap directamente?
Según cuáles sean los requisitos de velocidad, también puede usar un Trie . Pero no tiene sentido implementar uno de esos si un TreeMap es lo suficientemente rápido.
considere la frecuencia de adición o eliminación a la estructura de datos. TreeMap no sería ideal si es alto. Además de la búsqueda de la entrada existente nLn, también sufre un reequilibrio frecuente.
por otro lado, las estructuras Hash son poco extravagantes en la memoria (sobre asignaciones). Si puede morder esa bala, busque la estructura hash y ordene cuando sea necesario.
Aquí está el ejemplo de Java para leer un archivo de texto, ordenar en función de la clave y luego según los valores; dependiendo del número de palabras que aparecen en el archivo.
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 qué no usar TreeSet ?
El mismo concepto de orden que un TreeMap, excepto que es un Set, que, por definición, es " Una colección que no contiene elementos duplicados " ;.
De la descripción de su problema, parece que necesita un Set, no veo qué claves y valores están asignando juntos.
Esta clase implementa la interfaz Set, respaldada por una instancia de TreeMap. Esta clase garantiza que el conjunto ordenado estará en orden ascendente de elementos, ordenados de acuerdo con el orden natural de los elementos (ver Comparable), o por el comparador proporcionado en el momento de la creación del conjunto, dependiendo del constructor utilizado.
Básicamente depende del requisito. A veces, el mapa hash es bueno, a veces el treemap. pero el mapa hash es mejor usar solo su es una restricción para la sobrecarga para ordenarlo.
