Optimizing Java using D

[Andrei Alexandrescu via Digitalmars-d]

On 6/22/14, 10:07 AM, Xinok wrote:
> On Sunday, 22 June 2014 at 15:51:13 UTC, Andrei Alexandrescu wrote:
>> On 6/22/14, 7:47 AM, Xinok wrote:
>>> On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu wrote:
>>>> On 6/21/14, 8:28 AM, Xinok wrote:
>>>>> That has since been fixed. I implemented heapsort as a fallback
>>>>> algorithm, effectively making it an introsort.
>>>>
>>>> Wait, when did that happen? I think a better solution would be to take
>>>> median of more than 3 elements. -- Andrei
>>>
>>> https://github.com/D-Programming-Language/phobos/pull/1735
>>
>> Thanks. I wonder if it's possible to factor some of the heap sort code
>> with the BinaryHeap code; they look very similar.
>
> That's a possibility, and BinaryHeap could benefit from it. My heapsort
> is over twice as fast and performs almost half the number of comparisons.

Smile, you're on camera! https://issues.dlang.org/show_bug.cgi?id=12966

>> http://dlang.org/phobos/std_algorithm.html#topN is linear.
>
> Unfortunately not. I managed to trigger quadratic time using the same
> test case as above. If you're not aware, topN simply works by
> recursively partitioning the range until the Nth element is in place (in
> essence, it performs a partial quick sort). The author of this
> implementation made the poor decision of simply choosing the last
> element as the pivot, not even a median of three.
>
> http://dpaste.dzfl.pl/f30fd2539f66

That would be me, terrible, I know :o). I'd file a task a while ago, now 
I assigned you to it if you'd like to take a look: 
https://issues.dlang.org/show_bug.cgi?id=12141


Thanks,

Andrei