0

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" -> [9]

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?

Improve this question
7
  • This doesn't feel correct to me. You'll get a boatload of problems, the most obvious of them - numeric precision. I think I have a better solution if (a) you can access all lists concurrently and (b) if all values are positive. This later seems to be the case since you propose logarithms, but I just want to make sure.
    – Ordous
    Commented Sep 16, 2016 at 19:06
  • 1
    If you have memory for lists of unbounded size, you have memory for a BigInt per list that cannot overflow. Don't invent half-baked solutions yourself, use the ones already invented.
    – Kilian Foth
    Commented Sep 16, 2016 at 19:06
  • @Ordous yes, values are >= 0 (I did mention it). I can't really control how I access the lists though, I'm actually fed one value from each list at a time and need to keep a running sum.
    – Nicolas Rinaudo
    Commented Sep 16, 2016 at 19:08
  • 1
    @NicolasRinaudo One at a time from each list? Can you request that one of the lists stop sending for a moment and consume 2 or more values from another list? This will not affect the end values obviously, but will make some tricks available. Also, unless this is an academic problem, rather than a practical one, Kilian is right - just use a arbitrary-precision library. To overflow a 256-bit long by summing 32-bit integers, you need at least 2^224 summing operations. If you can manage that, then the NSA is already coming for your machine to crack everyone's encryption.
    – Ordous
    Commented Sep 16, 2016 at 19:15
  • 2
    Your formula evaluates to about 2.48 for list "b", and about 2.30 for list "c", so it would consider "b" to be the larger one. (edit: assuming by "lng" you mean "ln")
    – nomadictype
    Commented Sep 16, 2016 at 19:19

1 Answer 1

Reset to default
2

Your formula evaluates to about 2.48 for list "b", and about 2.30 for list "c", so it would consider "b" to be the larger one. So it is not correct.

As for alternative solutions, I would simply go with a running total per list (as a bignum) if at all possible.

Since you mentioned in a comment that the lists are actually streams, you could try to keep the numbers small by periodically subtracting the minimum of all running totals from all running totals. But that only helps if the totals grow at similar rates (the difference between the totals stays small) and might not be feasible if the number of lists/streams is large.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.