Data una mappa che associa etichette (stringhe, per esempio) a liste di ints maggiori o uguali a 0, vorrei ottenere la lista in cui le etichette sono ordinate in base alla somma dei valori dei loro elenchi associati, in ordine decrescente.
Per fare un esempio concreto, dato:
"a" -> [1, 1, 1]
"b" -> [2, 3]
"c" -> [9]
Vorrei che il risultato fosse:
["c", "b", "a"]
Un algoritmo ingenuo è banale, basta sommare e confrontare. Il mio problema è che sto lavorando con liste che possono essere enormi, e valori che non hanno limiti superiori conosciuti, ed è molto possibile che la somma superi il maxint e l'overflow.
La soluzione che ho in mente è, piuttosto che sommare i valori effettivi, per sommare il loro logaritmo naturale (+ 1 per evitare l'infinito negativo). Nel mio esempio precedente, i valori che userei per l'ordinamento sono:
"a": ln(1 + 1) + ln(1 + 1) + ln(1 + 1)
"b": ln(1 + 2) + ln(1 + 3)
"c": lng(1 + 9)
Ovviamente questo non risolve il problema completamente - non penso sia possibile, dato che le mie liste possono avere dimensioni di dimensioni arbitrarie - ma certamente lo allevia un bel po '.
Quello che mi chiedo però è corretto? si sente corretto, ma non ho la matematica per dimostrarlo rigorosamente.
E se questo è corretto o no, c'è una soluzione migliore?