Given a map that associates labels (strings, say) to lists of ints greater than or equal to 0, I'd like to get list where the labels are ordered by the sum of their associated lists' values, descending.
To take a concrete example, given:
"a" -> [1, 1, 1] "b" -> [2, 3] "c" -> 
I would like the result to be:
["c", "b", "a"]
A naïve algorithm is trivial, just sum and compare. My issue is that I'm working with lists that can be huge, and values that have no known upper bound, and it's very possible for the sum to exceed
maxint and overflow.
The solution I have in mind is, rather than summing the actual values, to sum their natural logarithm (+ 1 to avoid negative infinity). In my previous example, the values I'd use for sorting are:
"a": ln(1 + 1) + ln(1 + 1) + ln(1 + 1) "b": ln(1 + 2) + ln(1 + 3) "c": lng(1 + 9)
This obviously doesn't fix the problem entirely - I don't think that's possible, given that my lists can have arbitrarily large sizes - but certainly alleviates it quite a bit.
What I'm wondering though, is it correct? It feels correct, but I don't have the maths to prove it rigorously anymore.
And whether this is correct or not, is there a better solution?