programar - Ordenado automáticamente por mapa de valores en Java

scala ejemplos

Question

Necesito tener un mapa ordenado automáticamente por valores en Java, de modo que siga siendo ordenado en cualquier momento mientras agrego nuevos pares clave-valor o actualizo el valor de un par clave-valor existente, o incluso elimino algunos entrada.

Tenga en cuenta también que este mapa va a ser muy grande (cientos de miles, o incluso 10 de millones de entradas en tamaño).

Básicamente, estoy buscando la siguiente funcionalidad:

Suponemos que tenemos una clase ''SortedByValuesMap'' que implementa la funcionalidad antes mencionada y tenemos el siguiente código:

SortedByValuesMap<String,Long> sorted_map = new SortedByValuesMap<String, Long>();
sorted_map.put("apples", 4);
sorted_map.put("oranges", 2);
sorted_map.put("bananas", 1);
sorted_map.put("lemons", 3);
sorted_map.put("bananas", 6);
for (String key : sorted_map.keySet()) {
System.out.println(key + ":" + sorted_map.get(key));
}

la salida debe ser:

bananas:6
apples:4
lemons:3
oranges:2

En particular, lo que es realmente importante para mí, es poder obtener la entrada con el valor más bajo en cualquier momento, usando un comando como:

smallestItem = sorted_map.lastEntry();

que debería darme la entrada ''naranjas''

EDITAR: Soy un novato de Java, así que por favor elabora un poco en tus respuestas - gracias

EDIT2: Esto podría ayudar: estoy usando esto para contar palabras (para aquellos que están familiarizados: n-grams en particular) en archivos de texto enormes. Entonces necesito construir un mapa donde las claves sean palabras y los valores sean las frecuencias de esas palabras. Sin embargo, debido a las limitaciones (como RAM), quiero mantener solo las X palabras más frecuentes, pero no se puede saber de antemano cuáles serán las palabras más frecuentes, por supuesto. Entonces, la forma en que pensé que podría funcionar (como una aproximación) es comenzar a contar palabras y cuando el mapa alcanza un límite superior (como entradas de 1 mil), la entrada menos frecuente se eliminará para mantener el tamaño del mapa en 1 mil siempre.

Answer 1

¿Qué tal si usamos un índice adicional o solo TreeMap<Long, TreeSet<String>> o TreeMap<Long, String> si los valores Long son distintos?

También puedes escribir un Heap .

Answer 2

Encontré la necesidad de una estructura similar para mantener una lista de objetos ordenados por valores asociados. Basado en la sugerencia de Caracol mecánico en este hilo, codifiqué una implementación básica de dicho mapa. Siéntase libre de usar.

import java.util.*;
/**
* A map where {@link #keySet()} and {@link #entrySet()} return sets ordered
* with ascending associated values with respect to the the comparator provided
* at constuction. The order of two or more keys with identical values is not
* defined.
* <p>
* Several contracts of the Map interface are not satisfied by this minimal
* implementation.
*/
public class ValueSortedMap<K, V> extends HashMap<K, V> {
protected Map<V, Collection<K>> valueToKeysMap;
public ValueSortedMap() {
this((Comparator<? super V>) null);
}
public ValueSortedMap(Comparator<? super V> valueComparator) {
this.valueToKeysMap = new TreeMap<V, Collection<K>>(valueComparator);
}
public boolean containsValue(Object o) {
return valueToKeysMap.containsKey(o);
}
public V put(K k, V v) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
valueToKeysMap.get(oldV).remove(k);
}
super.put(k, v);
if (!valueToKeysMap.containsKey(v)) {
Collection<K> keys = new ArrayList<K>();
keys.add(k);
valueToKeysMap.put(v, keys);
} else {
valueToKeysMap.get(v).add(k);
}
return oldV;
}
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public V remove(Object k) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
super.remove(k);
valueToKeysMap.get(oldV).remove(k);
}
return oldV;
}
public void clear() {
super.clear();
valueToKeysMap.clear();
}
public Set<K> keySet() {
LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
for (V v : valueToKeysMap.keySet()) {
Collection<K> keys = valueToKeysMap.get(v);
ret.addAll(keys);
}
return ret;
}
public Set<Map.Entry<K, V>> entrySet() {
LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
for (Collection<K> keys : valueToKeysMap.values()) {
for (final K k : keys) {
final V v = get(k);
ret.add(new Map.Entry<K,V>() {
public K getKey() {
return k;
}
public V getValue() {
return v;
}
public V setValue(V v) {
throw new UnsupportedOperationException();
}
});
}
}
return ret;
}
}

Esta implementación no respeta todos los contratos de la interfaz de Mapa, como reflejar cambios de valores y eliminaciones en el conjunto de claves devuelto y conjuntos de entradas en el mapa real, pero dicha solución sería un poco grande para incluir en un foro como este. Tal vez trabaje en uno y lo haga disponible vía github o algo similar.

Answer 3

Mantenga 2 estructuras de datos:

• Un diccionario de palabras -> contar. Solo use un HashMap<String, Long> ordinario HashMap<String, Long> .

• Una "matriz" para realizar un seguimiento del orden, de modo que la list[count] contiene un Set<String> de palabras con esa cuenta.

  Estoy escribiendo esto como si fuera una matriz como una conveniencia de notación. De hecho, es probable que no conozca un límite superior en el número de apariciones, por lo que necesita una estructura de datos redimensionable. Implementar usando un Map<Long, Set<String>> . O, si eso consume demasiada memoria, use un ArrayList<Set<String>> (deberá probar para count == size() - 1 , y si es así, use add() lugar de set(count + 1) ).

Para incrementar el número de ocurrencias para una palabra (pseudocódigo):

// assumes data structures are in instance variables dict and arr
public void tally(final String word)
{
final long count = this.dict.get(word) or 0 if absent;
this.dict.put(word, count + 1);
// move word up one place in arr
this.arr[count].remove(word); // This is why we use a Set: for fast deletion here.
this.arr[count + 1].add(word);
}

Para iterar sobre las palabras en orden (pseudocódigo):

for(int count = 0; count < arr.size; count++)
for(final String word : this.arr[count])
process(word, count);

Answer 4

Pruebe la solución publicada en http://paaloliver.wordpress.com/2006/01/24/sorting-maps-in-java/ . Usted tiene la flexibilidad de hacer la clasificación ascendente o descendente también.

Esto es lo que dicen

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
public class MapValueSort {
/** inner class to do soring of the map **/
private static class ValueComparer implements Comparator<String> {
private Map<String, String> _data = null;
public ValueComparer (Map<String, String> data){
super();
_data = data;
}
public int compare(String o1, String o2) {
String e1 = (String) _data.get(o1);
String e2 = (String) _data.get(o2);
return e1.compareTo(e2);
}
}
public static void main(String[] args){
Map<String, String> unsortedData = new HashMap<String, String>();
unsortedData.put("2", "DEF");
unsortedData.put("1", "ABC");
unsortedData.put("4", "ZXY");
unsortedData.put("3", "BCD");
SortedMap<String, String> sortedData = new TreeMap<String, String>(new MapValueSort.ValueComparer(unsortedData));
printMap(unsortedData);
sortedData.putAll(unsortedData);
System.out.println();
printMap(sortedData);
}
private static void printMap(Map<String, String> data) {
for (Iterator<String> iter = data.keySet().iterator(); iter.hasNext();) {
String key = (String) iter.next();
System.out.println("Value/key:"+data.get(key)+"/"+key);
}
}
}

Salidas

Value/key:BCD/3
Value/key:DEF/2
Value/key:ABC/1
Value/key:ZXY/4
Value/key:ABC/1
Value/key:BCD/3
Value/key:DEF/2
Value/key:ZXY/4

Answer 5

Puede consultar la implementación de java.util.LinkedHashMap . La idea básica es usar una lista vinculada interna para almacenar pedidos. Aquí hay algunos detalles:

Se extiende desde HashMap. En HashMap, cada entrada tiene una clave y un valor, que es básico. Puede Agregar un puntero siguiente y uno anterior para almacenar las entradas en orden por valor. Y un puntero y un puntero en la cola para obtener la primera y la última entrada. Para cada modificación (agregar, eliminar, actualizar), puede agregar su propio código para cambiar el orden de la lista. No es más que una búsqueda lineal y un interruptor de puntero.

Claro que será lento agregar / actualizar si hay demasiadas entradas porque es una lista vinculada, no una matriz. Pero mientras la lista esté ordenada, creo que hay muchas formas de acelerar la búsqueda.

Así que aquí está lo que obtienes: un mapa que tiene la misma velocidad con HashMap cuando recuperas una entrada con una tecla. Una lista vinculada que almacena las entradas en orden.

Podemos analizar esto más a fondo si esta solución cumple con sus requisitos.

a jtahlborn: Como dije, seguramente es lento sin ninguna optimización. Ya que estamos hablando de rendimiento no impl ahora, se pueden hacer muchas cosas.

Una solución es usar un árbol en lugar de una lista vinculada, como el árbol rojo-negro. Luego itere el árbol en lugar de iterar el mapa.

Acerca del valor más pequeño, es más fácil. Simplemente usando una variable miembro para almacenar la más pequeña, cuando agregue o actualice un elemento, actualice el valor más pequeño. Cuando lo elimine, busque el árbol por el más pequeño (esto es muy rápido)

si el árbol es demasiado complejo, también es posible utilizar otra lista / matriz para marcar algunas posiciones en la lista. por ejemplo, tal vez 100 elementos cada uno. Luego, cuando busque, simplemente busque primero en la lista de posiciones y luego en la lista real. Esta lista también debe mantenerse, sería razonable volver a contar la lista de posiciones para ciertos tiempos de modificación, tal vez 100.

Answer 6

Solución Guava BiMap :

//Prepare original data
BiMap<String, Integer> biMap = HashBiMap.create();
biMap.put("apples" , 4);
biMap.put("oranges", 2);
biMap.put("bananas", 1);
biMap.put("lemons" , 3);
biMap.put("bananas", 6);
//Create a desc order SortedMap
SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(new Comparator<Integer>(){
@Override public int compare(Integer o1, Integer o2) {
return o2-o1;
}});
//Put inversed map
sortedMap.putAll(biMap.inverse());
for (Map.Entry<Integer, String> e: sortedMap.entrySet()) {
System.out.println(e);
}
System.out.println(sortedMap.lastKey());

Answer 7

si todo lo que necesita es el valor "mínimo", simplemente use un mapa normal y realice un seguimiento del valor "mínimo" cada vez que se modifique.

EDITAR:

por lo tanto, si realmente necesita un pedido de valor y desea usar soluciones listas para usar, básicamente necesita 2 colecciones. Un mapa normal (por ejemplo, HashMap) y un SortedSet (por ejemplo, TreeSet>). puede atravesar elementos ordenados a través del TreeSet y buscar frecuencias mediante la clave utilizando HashMap.

Obviamente, siempre podrías codificar algo como una LinkedHashMap, donde los elementos son localizables por clave y atravesables por orden, pero eso va a ser un código completamente personalizado (dudo que algo específico ya exista, pero podría ser incorrecto).

Answer 8

Actualización: no puede ordenar mapas por valores, lo siento.

Puede usar la implementación de SortedMap como TreeMap con el orden de definición del Comparator por valores (en lugar de por defecto - por claves).

O, mejor aún, puede colocar elementos en un PriorityQueue con un comparador predefinido por valores. Debería ser más rápido y tomar menos memoria en comparación con TreeMap.