Optimizing Java using D

[Steven Schveighoffer via Digitalmars-d]

On Mon, 23 Jun 2014 11:38:24 -0400, Chris Cain <zshazz at gmail.com> wrote:

> On Monday, 23 June 2014 at 15:19:15 UTC, Steven Schveighoffer wrote:
>> Is it just me, or does this seem unintuitive? I would think a stable  
>> sort requires extra care, i.e. extra time, to ensure stability.
>>
>> Do we need an unstable sort then? Or is this a corner case? I am fully  
>> ignorant on these advanced sorting routines and how they work. The  
>> Quicksort-based sort routines are like black magic to me, my knowledge  
>> stops at merge sort :)

>
> Technically, you can prove that there exists some unstable sort that is  
> always faster than a stable sort. Andrei showed me this once:
>
> [2,2,2,2,1]
>
> With unstable sort, the 1 and first 2 could be swapped, but with stable  
> sort, the 1 must swap with each 2 until it settles into the 0th position.
>
> That said, I've never seen the unstable sort that's always faster than  
> any stable sort and since it doesn't appear in any of the languages I  
> know of, I've got to guess that no one else has discovered it either.

Right. It's all dependent on whether the unstable sort can make the "right  
decisions." In my mind, ensuring stability seems like an extra task. In  
other words, (and I know it's not true) for every stable sort, there  
exists an equivalent unstable sort that does not have to do extra work to  
preserve ordering. But some sorts are stable by nature. It's probably a  
factor of the two sorts using different algorithms that happen to work  
better on some data sets.

> That said, I've seen some cases where the unstable sort is faster  
> (particularly in cases where the ordering of the elements is nearly  
> completely random), so it's not as if unstable sort is currently always  
> worse. It's just in many real-world scenarios it ends up being worse.  
> Furthermore, our stable sort (an implementation of Timsort) is  
> impossible to really use "incorrectly" ... even using it very "stupidly"  
> (as an example, append an element on the end of a sorted array and  
> "insert" it by calling stable sort) will result in reasonable runtimes  
> and do what the programmer expects of it. It makes writing simple quick  
> scripts and prototypes absurdly easy and still very efficient. Plus  
> maintaining the current order of the elements is really nice in general.
>
> Personally, I'm still in the camp of suggesting that our default should  
> be stable sort and if you're certain your use case will benefit from the  
> extra speed of unstable sort, you should specify it. But I don't think  
> that's going to change.

This seems like sound advice. An interesting "feature" may be to try and  
predict which sorts are working better for some process. In other words,  
choose a proportion of sorts to perform using stable, and some to use  
unstable. Then compare the speed per element, and adjust the proportion to  
favor the faster sort (obviously only when the sort method is not  
specified). I wonder how well this might perform for tasks that frequently  
sort. You could wrap the sorting routine with another function which does  
this.

-Steve