Encontrar los valores más altos de n en un mapa

Question

Tengo un mapa grande de String-> Integer y quiero encontrar los 5 valores más altos en el mapa. Mi enfoque actual implica traducir el mapa en una lista de matrices de objetos de par (clave, valor) y luego ordenar usando Collections.sort() antes de tomar los primeros 5. Es posible que una clave tenga su valor actualizado durante el curso de la operación .

Creo que este enfoque es aceptable con una sola hebra, pero si tuviera múltiples hilos todos activando la transposición y clasificación con frecuencia, no parece muy eficiente. La alternativa parece ser mantener una lista separada de las 5 entradas más altas y mantenerla actualizada cuando se realizan operaciones relevantes en el mapa.

¿Podría obtener algunas sugerencias/alternativas para optimizar esto, por favor? Me complace considerar diferentes estructuras de datos si hay un beneficio.

Gracias!

Answer 1

creo que este enfoque es el único subproceso aceptable, pero si tuviera múltiples hilos de toda la transpuesta de activación y clasificar con frecuencia no parece muy eficiente. La alternativa parece ser mantener una lista separada de las 5 entradas más altas y mantenerla actualizada cuando se realizan operaciones relevantes en el mapa.

Hay un enfoque intermedio que puede tomar también. Cuando un hilo solicita una "vista ordenada" del mapa, crea una copia del mapa y luego maneja la clasificación en ese mapa.

public List<Integer> getMaxFive() { 
    Map<String, Integer> copy = null; 
    synchronized(lockObject) { 
     copy = new HashMap<String, Integer>(originalMap); 
    } 

    //sort the copy as usual 
    return list; 
} 

ideal sería que si usted tiene algún estado (como este mapa) se accede por múltiples hilos, que está encapsulando el estado detrás de alguna otra clase de manera que cada hilo no se actualiza el mapa directamente.

Answer 2

Bueno, para encontrar los 5 valores más altos en un Mapa, puede hacerlo en el momento O(n) donde cualquier tipo es más lento que eso.

La manera más fácil es simplemente hacer un ciclo for en el conjunto de entradas del Mapa.

for (Entry<String, Integer> entry: map.entrySet()) { 
    if (entry.getValue() > smallestMaxSoFar) 
     updateListOfMaximums(); 
} 

Answer 3

Intente con otra estructura de datos. Supongamos que hay una clase llamada MyClass cuyos atributos son key (String) y value (int). MyClass, por supuesto, necesita implementar una interfaz comparable. Otro enfoque es crear una clase llamada MyClassComparator que amplíe Comparator.

El método compareTo (independientemente de dónde se encuentre) debe definirse así: compareTo (parámetros) { return value2 - value1; // descendiendo }

El resto es fácil. Usar el método List e invocar Collections.sort (parameters) hará la parte de clasificación.

No sé qué algoritmo de clasificación usa Collections.sort (parameters). Pero si crees que algunos datos pueden aparecer con el tiempo, necesitarás un tipo de inserción. Dado que es bueno para una información casi ordenada, es online.

Answer 4

se pueden utilizar dos mapas:

// Map name to value 
Map<String, Integer> byName 

// Maps value to names 
NavigableMap<Integer, Collection<String>> byValue 

y asegúrese de mantener siempre en sincronía (posiblemente envuelva tanto en otra clase que se encarga de poner, obtener, etc). Para los valores más altos, use byValue.navigableKeySet().descendingIterator().

Answer 5

Si las modificaciones son raras, implementaría algunas SortedByValHashMap<K,V> extends HashMap <K,V>, similar a LinkedHashMap) que mantiene las entradas ordenadas por valor.

Answer 6

me gustaría crear un método como:

private static int[] getMaxFromMap(Map<String, Integer> map, int qty) { 
    int[] max = new int[qty]; 
    for (int a=0; a<qty; a++) { 
     max[a] = Collections.max(map.values()); 
     map.values().removeAll(Collections.singleton(max[a])); 
     if (map.size() == 0) 
      break; 
    } 
    return max; 
} 

Aprovechando Collections.max() y Collections.singleton()

Answer 7

Hay dos maneras de hacerlo fácilmente:

1. poner el mapa en un heap structure y recupera los elementos n que quieras de él.
2. Iterar a través del mapa y actualizar una lista de n valores más altos con cada entrada.

Si desea recuperar un número desconocido o un gran número de valores más altos, el primer método es el camino a seguir. Si tiene una pequeña cantidad fija de valores para recuperar, la segunda podría ser más fácil de entender para algunos programadores. Personalmente, prefiero el primer método.