recorrer - ¿Qué estructura de datos usarías: TreeMap o HashMap?(Java)

recorrer un map java (14)

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 aparece la palabra 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 concreto, 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: Oh sí, sería útil mostrar una implementación usando una de estas estructuras (en Java).

"Cuando una clave ya existe, tiene el mismo rendimiento que una HashMap". - Eso es simplemente incorrecto. HashMap tiene inserción O (1) y TreeMap O (n log n). Tomará al menos n log n cheques para ver si está en la mesa.

¿Por qué no usar TreeSet ?

El mismo concepto de ordenamiento que TreeMap, excepto que es un conjunto, que, por definición, es "Una colección que no contiene elementos duplicados".

A partir de la descripción de su problema, parece que necesita un conjunto, no veo qué claves y valores está mapeando.

Esta clase implementa la interfaz Set, respaldada por una instancia de TreeMap. Esta clase garantiza que el conjunto ordenado estará en orden de elementos ascendente, ordenado de acuerdo con el orden natural de los elementos (vea Comparable), o por el comparador proporcionado en el tiempo de creación del conjunto, dependiendo de qué constructor se use.

Aquí está el ejemplo de Java para leer un archivo de texto, ordenar según la clave y luego sobre los valores; dependiendo del número de ocurrencias de una palabra 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; } }

Básicamente depende del requisito. A veces, el mapa hash es bueno a veces treemap. pero el mapa hash es mejor usar solo su es una restricción para la sobrecarga para ordenarlo.

Definitivamente elegiría un TreeMap:

TreeMap clasifica automáticamente nuevas claves en la inserción, no es necesario ordenarlas después.
Cuando una clave ya existe, tiene el mismo rendimiento que un HashMap.

Un TreeSet internamente usa un TreeMap entonces ¿por qué no usar TreeMap directamente?

Dependiendo de cuáles sean los requisitos de velocidad, también puede usar un Trie . Pero no tiene sentido implementar uno de ellos si un TreeMap es lo suficientemente rápido.

El mapa hash debe ser mucho más rápido. No debe elegir un contenedor según cómo quiera que los elementos se organicen con el tiempo; Solo ordena la lista de pares (palabra, frecuencia) al final. Por lo general, habrá menos pares de ese tipo para clasificar que las 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. se pueden "poner" en un TreeMap<String,Number> . Cuando "obtengo" un valor de un Map<String,Integer> , debe ser un Integer .

Completamente ignorando cualquier problema 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()); } } }

Por este camino, en mi opinión, mejor usar HashBag de Apache Commons Collections o HashMultiset de Guava o HashBag de Eclipse Collections ( colecciones formaly GS ) o cualquiera de las siguientes clases:

Ejemplos:

1. Usando SynchronizedSortedBag desde 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 desde 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 puedes encontrar en mis proyectos de github

TreeMap supera a HashMap porque TreeMap ya está ordenado para usted.

Sin embargo, es posible que desee considerar el uso de una estructura de datos más apropiada, una bolsa. Ver colecciones de Commons - y la 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 cuestión del rendimiento de HashMap frente a TreeMap y el género puede ser más rápido (¡pruébalo!), Pero TreeBag es más fácil. Lo mismo es cierto para las bolsas. Hay un HashBag así como un TreeBag. En función de la implementación (utiliza un entero mutable), una bolsa debería superar al mapa normal equivalente de Entero. La única manera de saberlo con certeza es probar, como con cualquier pregunta de rendimiento.

Veo a muchas personas diciendo "¡La búsqueda TreeMap toma O(n log n) "! ¿Cómo?

No sé cómo se ha implementado, pero en mi cabeza toma O(log n) .

Esto se debe a que la búsqueda en un árbol se puede hacer en O(log n) . No ordena el árbol completo cada vez que inserta un elemento en él. ¡Esa es la idea de usar un árbol!

Por lo tanto, volviendo a la pregunta original, las cifras para la comparación resultan ser:

Aproximación HashMap: caso promedio O(n + k log k) , el peor caso podría ser mucho más grande

Acercamiento de TreeMap: O(k + n log k) peor caso

donde n = número de palabras en el texto, k = número de palabras distintas en el texto.

considere la frecuencia de la adición o eliminación de 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 se somete a un reequilibrio frecuente.

por otro lado, las estructuras Hash son un tanto extravagantes en la memoria (sobre asigna). Si puedes morder esa bala, elige la estructura hash y clasifícala cuando sea necesario.

TreeMap parece una obviedad para mí, simplemente por el requisito de "en orden alfabético". HashMap no tiene pedidos cuando iteras a través de él; TreeMap itera en el orden de clave natural.

EDITAR: Creo que el comentario de Konrad puede haber sugerido "usar HashMap, luego ordenar". Esto es bueno porque aunque tendremos N iteraciones inicialmente, tendremos claves K <= N al final debido a los duplicados. También podríamos guardar el poco costoso (clasificación) hasta el final cuando tengamos menos claves que tomar el pequeño pero no constante golpe de mantenerlo ordenado sobre la marcha.

Habiendo dicho eso, me estoy quedando 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 le preocupa la elegancia y la brevedad. Usar un TreeMap lo hace increíblemente breve, lo cual me atrae. Sospecho que si el rendimiento es realmente un problema, puede haber una mejor manera de atacarlo que TreeMap o HashMap :)

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(); } } }