Ricerca dei valori n più alti in una mappa

Question

Ho una grande mappa di String-> Intero e voglio trovare i 5 valori più alti nella mappa. Il mio approccio attuale prevede la traduzione della mappa in un elenco di array di oggetti coppia (chiave, valore) e quindi l'ordinamento con Collections.sort() prima di eseguire il primo 5. È possibile che una chiave abbia il proprio valore aggiornato durante il corso dell'operazione .

Penso che questo approccio sia accettabile a thread singolo, ma se avessi più thread tutti attivando la trasposizione e ordinando frequentemente non sembra molto efficiente. L'alternativa sembra essere quella di mantenere un elenco separato delle 5 voci più alte e tenerlo aggiornato quando si verificano le operazioni rilevanti sulla mappa.

Potrei avere alcuni suggerimenti/alternative sull'ottimizzazione per favore? Sono felice di prendere in considerazione diverse strutture di dati se c'è beneficio.

Grazie!

Answer 1

Credo che questo approccio è accettabile filettato singolo, ma se avevo più thread tutti innescando la trasposta e ordinare spesso non sembra molto efficiente. L'alternativa sembra essere quella di mantenere un elenco separato delle 5 voci più alte e tenerlo aggiornato quando si verificano le operazioni rilevanti sulla mappa.

C'è un approccio nel mezzo che puoi prendere anche tu. Quando una discussione richiede una "vista ordinata" della mappa, crea una copia della mappa e poi gestisci l'ordinamento su quella mappa.

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

    //sort the copy as usual 
    return list; 
} 

Idealmente, se si dispone di uno stato (come questa cartina) accessibile da più thread, si incapsulare lo stato dietro qualche altra classe in modo che ciascun filo non aggiorna direttamente la mappa.

Answer 2

Bene, per trovare i 5 valori più alti in una mappa, è possibile farlo nel tempo O(n) in cui qualsiasi tipo è più lento di quello.

Il modo più semplice è fare semplicemente un ciclo for attraverso il set di voci della mappa.

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

Answer 3

Si prega di provare un'altra struttura di dati. Supponiamo che ci sia una classe chiamata MyClass che i suoi attributi sono key (String) e value (int). MyClass, ovviamente, ha bisogno di implementare un'interfaccia comparabile. Un altro approccio consiste nel creare una classe denominata MyClassComparator che estenda Comparator.

Il metodo compareTo (non importa dove sia) deve essere definito in questo modo: compareTo (parametri) { valore restituito2 - valore1; // descending }

Il resto è facile. Usando List e invocando il metodo Collections.sort (parametri) verrà eseguita la parte di ordinamento.

Non so quale algoritmo di ordinamento Collections.sort (parametri) utilizza. Ma se ritieni che alcuni dati possano arrivare nel tempo, avrai bisogno di un ordinamento per l'inserimento. Dal momento che è buono per un dato che ha quasi ordinato ed è online.

Answer 4

È possibile utilizzare due mappe:

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

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

e assicurarsi di tenerli sempre in sincronia (possibilmente avvolgere sia in un'altra classe che è responsabile della put, ottenere, ecc). Per i valori più alti utilizzare byValue.navigableKeySet().descendingIterator().

Answer 5

Se le modifiche sono rare, implementerei un po 'di SortedByValHashMap<K,V> extends HashMap <K,V>, simile a LinkedHashMap che mantiene le voci ordinate per valore.

Answer 6

vorrei creare un metodo come:

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

Sfruttando Collections.max() e Collections.singleton()

Answer 7

Ci sono due modi di fare così facilmente:

1. Ponga il mappa in un heap structure e riattivare gli elementi n da esso.
2. Iterate attraverso la mappa e aggiornate un elenco di n valori più alti utilizzando ciascuna voce.

Se si desidera recuperare uno sconosciuto o un numero elevato di valori massimi, il primo metodo è la strada da percorrere. Se hai una piccola quantità fissa di valori da recuperare, la seconda potrebbe essere più facile da capire per alcuni programmatori. Personalmente, preferisco il primo metodo.