3 ms·
A solution more accurate than sorting before adding is to place your numbers into a priority queue and repeatedly add the smallest two numbers and re-insert the
by ball_of_lint 8y ago
A solution more accurate than sorting before adding is to place your numbers into a priority queue and repeatedly add the smallest two numbers and re-insert the result into the queue. This helps handle the case where you have many similarly valued numbers and your running sum becomes large enough relative to your numbers to cause the same rounding errors.
- taneq 8y agoIsn't a priority queue implicitly sorted?
- Zarel 8y agoYes. I don't think your parent post meant to imply otherwise. The priority queue approach boils down to "sort after every addition, instead of just once at the beginning".
- taneq 8y agoAh right, I read 'more accurate than sorting before adding' as 'without sorting before adding' and missed that it was more about rounding errors than the sorting.