Sort sum refinement

[dpbutter]

I've been fiddling with sort_sum because recently I had a giant sum and the bubble sort was taking a while.

The first two commits were for debugging purposes, where I tried making the bubble sort a bit smarter, then implemented insertionSort (which seems to generally be faster by a factor of 2), and then implemented an unoptimized version of Python's timSort. For small sums (most people's use cases), the additional overhead of timSort seemed to make no difference.

The final commit here eliminates the bubbleSort entirely and just calls timSort. It takes a Python parameter runsize (ideally a power of 2, and defaults to 32) which sets the initial insertionSort runlength. Higher runsizes are better for nearly sorted lists.

[dpbutter]

After looking at corresponding tweaks of sort_product, I think the above code might be slower if there are MANY small sums in the tree, due do the slight additional overhead used in insertionSort on every sum. (Not enough terms in my testing to activate mergeSort.) I was concerned with a single long sum in the tree.

[kpeeters]

Thanks for taking a shot at this.

I actually had a long-term plan to use the tree<...>::sort function to handle sort_sum. The way that works is that it sticks the range of sibling iterators into a map, with a comparison function which should then look at the values the way the current bubble sort does. It then re-assembles the child nodes using the sorted iterators.

An alternative implementation of this could simply store the sibling iterators into a vector and then use std::sort on this.

In any case, it would have two advantages over the solution you created: a) it uses the standard library for the sort implementation, which is likely to beat whatever you write yourself (in speed, but potentially also in correctness and certainly in maintainability), and b) it moves all logic into the tree base class (where it belongs really).

[dpbutter]

Ah, I was wondering what the deal was with tree<>::sort. That certainly sounds like it would be a much better idea in the long run. I've been trying to optimize a couple things so some code I have will be a bit faster, and sort_sum was driving me mad. ;-)

[dpbutter]

I gave a shot at rewriting it to use your second suggestion to see how it worked. As you suggested, it's much simpler code. Runtimes seem roughly comparable to my hacky timSort even with all the additional overhead of constructing all the sibling iterators. I should have done that originally.