Optimizing Java using D

Chris Cain via Digitalmars-d digitalmars-d at puremagic.com
Tue Jun 24 09:37:05 PDT 2014


On Tuesday, 24 June 2014 at 09:22:24 UTC, Andrea Fontana wrote:
> On Monday, 23 June 2014 at 16:33:13 UTC, Chris Cain wrote:
>> It's not really about the time complexity but the absolute 
>> time it must take. But I showed the example that shows that 
>> the fact that any stable sort must do extra work:
>>
>> [2,2,2,2,1]
>> [...]
>
> I'm sorry if i'm going to say some stupid things, but I'm still 
> not sure about this.
>
> You said: "you can prove that there exists some unstable sort 
> that is always faster than a stable sort"
>
> First of all: stable sort are also unstable, ok, but I think 
> you meant: "you can prove that there exists some unstable sort 
> - that it isn't a stable sort too -  that is always faster than 
> a stable sort", didn't you?

Of course. It couldn't take advantage of the looser definition to 
be faster otherwise.

>
> With your example you're showing that is this specific case is 
> faster, you're not proving that is *always* faster (btw, i 
> think you meant equal or faster).

Yes, equal to or faster in any individual case. Since there 
exists one specific case that it must be faster, that means *in 
general* it is faster. I didn't mean "in every circumstance it's 
faster", just that unstable sorts will always be, in general, 
faster because they can do all the same things as a stable sort 
but they have fewer restrictions and can potentially perform 
"short-cuts" that are illegal with stable sorts.

Basically, there's no reason an unstable sort will ever be slower 
than a stable sort, but this at least "one specific case" shows 
the reverse is not true.

> In my opinion you're just proving that for *swap-based 
> algorithms* number of swaps you need to unstable sorting is 
> always *less or equals* to the number of swaps you need to 
> stable sorting.
>
> Anyway some sorting algorithms don't use comparison between 
> elements so swap doesn't make any sense. Radix sort, for 
> example, never compares two elements. It "directly" write the 
> output array, so I don't think the number of swaps is the right 
> metric. Counting sort doesn't do any comparison too, and it 
> doesn't swap elements.

OK, sure, but those are technically also unstable sorts, so it's 
not as if you've found a case where what I said is untrue. Plus 
you're ignoring the fact that those are specialized solutions 
with reduced restrictions of their own. They aren't general 
sorting algorithms that work perfectly in all situations.

Plus counting sort could be said to be strictly an unstable sort 
because it doesn't necessarily preserve the order of the elements 
(in fact, it removes the identity of each element entirely, but 
that's one of the reasons it's not a good "general sorting 
algorithm").

Let's say you use counting sort on a hand of cards and you want 
to sort based on the card values irrespective of their suit. I 
think at this point you know that it's impossible to preserve the 
stability of the cards with counting sort.

> Moreover you're assuming it should work "in-place". Usually we 
> need a sorted copy, so you can't just swap that elements, you 
> need to copy the other elements too and then apply your swaps 
> over copy. If element are complex you have to copy element to 
> new array one-by-one.
>
> Using your example a 
> "magical-stable-sort-without-swaps-planning-algorithm" could 
> guess that we just need to prepend last element before the 
> first one: it is a stable sort. There's no swap at all. And we 
> copy exactly n elements. (and it's faster than copy all n 
> elements and then do the swap).

Of course, that's yet more playing around with restrictions. Plus 
your proposed relaxed stable sort is also the same as relaxed 
unstable sort so your restriction just made them identically fast.

That said, what you have to understand is that this is showing 
that restrictions that you place on the data/storage/etc will 
make it so that you can only do a subset of all possible 
algorithms. stability is a restriction that makes it so that you 
can't do all the same things an unstable sort can do. Never does 
this mean that a stable sort can be faster, but it *can* mean 
that an unstable sort will be faster.

In the by-default restrictions placed on std.algorithm.sort, 
unstable sort is faster. The possibility of application/removal 
of other restrictions making them ultimately equivalent is 
irrelevant.

So if you're wondering if there possibly exists a set of 
conditions where stable sort and unstable sort are equal, then 
yes, there are. However, if you know nothing about the conditions 
or restrictions, it's a safe bet to say that unstable sort is 
equal to or faster than stable sort. Furthermore, if you know 
about the conditions/restrictions on std.algorithm.sort, you 
_know_ unstable sort can be made faster than stable sort.


More information about the Digitalmars-d mailing list