On 9/10/10 5:25 PM, Andrei Alexandrescu wrote:
> On 10/9/10 11:23 CDT, Peter Alexander wrote:
>> On 9/10/10 4:53 PM, bearophile wrote:
>>> Andrei:
>>>
>>>> Currently std.algorithm.getPivot picks the middle of the range as the
>>>> pivot, but I made it modular such that it can be improved in a
>>>> number of
>>>> ways (i.e. randomized, median-of-3, median-of-5, etc).
>>>
>>> Isn't median of 3 a better default?
>>>
>>> Bye,
>>> bearophile
>>
>> There is no "best". They are all trade-offs between the time taken to
>> select the pivot and the suitability of the pivot.
>>
>> Middle - Fastest, not very good
>> Median-of-3 - Slower, but slightly better
>> Median-of-5 - Slower still, but even better
>>
>> Randomized - Speed depends on the random number algorithm. Suitability
>> is random, so could be good, could be bad, but on average it's good
>> enough. Has the added quality that it's practically impossible to devise
>> worst-case input for it (you'd need to know the generator and seed),
>> whereas for the other 3, a malicious user could provide data that gives
>> you O(n^2) complexity.
>
> Also: in-place sorting for the median cases.
>
> Andrei

Could you elaborate? I don't see how you lose in-place sorting with the random and middle selection cases.

On 10/9/10 11:52 CDT, Sean Kelly wrote:
> Andrei Alexandrescu Wrote:
>>
>> In fact, guards can be put to ensure that the _expected_ (not average,
>> not best-case) complexity is O(n log n). This makes the risk of hitting
>> a worst-case scenario negligible in a principled manner.
>>
>> http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
>>
>> http://docs.google.com/viewer?a=v&q=cache:MdBVR26N5UsJ:www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf+randomized+quicksort&hl=en&gl=us&pid=bl&srcid=ADGEESi3GTSxfHWkeb_f14H0pkbigduS94qJVc9XLQ7aPa6lPUJ5JZbggI0izFe3ogiVOJCYcVkGtdumaS9hBvrGw0-TA_yZQj2qd1-AEudKyEWEGXnO4sTwqCZL95OpFkdFHDF2WXFV&sig=AHIEtbT1R0q5RIR4rob17QUKlYVl90vXyQ
>>
>> Currently std.algorithm.getPivot picks the middle of the range as the
>> pivot, but I made it modular such that it can be improved in a number of
>> ways (i.e. randomized, median-of-3, median-of-5, etc).
>
> It would be nice if it used insertion sort for small ranges as well.  There's also a quicksort variant that partitions equal-to elements separately from less-than and greater-than values, which is faster for ranges with a lot of equal elements (and no slower for ranges without).

I guess that's "fit pivot" :o). Fat pivot does cost some more.

Andrei

On 10/9/10 12:12 CDT, Peter Alexander wrote:
> On 9/10/10 5:25 PM, Andrei Alexandrescu wrote:
>> On 10/9/10 11:23 CDT, Peter Alexander wrote:
>>> On 9/10/10 4:53 PM, bearophile wrote:
>>>> Andrei:
>>>>
>>>>> Currently std.algorithm.getPivot picks the middle of the range as the
>>>>> pivot, but I made it modular such that it can be improved in a
>>>>> number of
>>>>> ways (i.e. randomized, median-of-3, median-of-5, etc).
>>>>
>>>> Isn't median of 3 a better default?
>>>>
>>>> Bye,
>>>> bearophile
>>>
>>> There is no "best". They are all trade-offs between the time taken to
>>> select the pivot and the suitability of the pivot.
>>>
>>> Middle - Fastest, not very good
>>> Median-of-3 - Slower, but slightly better
>>> Median-of-5 - Slower still, but even better
>>>
>>> Randomized - Speed depends on the random number algorithm. Suitability
>>> is random, so could be good, could be bad, but on average it's good
>>> enough. Has the added quality that it's practically impossible to devise
>>> worst-case input for it (you'd need to know the generator and seed),
>>> whereas for the other 3, a malicious user could provide data that gives
>>> you O(n^2) complexity.
>>
>> Also: in-place sorting for the median cases.
>>
>> Andrei
>
> Could you elaborate? I don't see how you lose in-place sorting with the
> random and middle selection cases.

You just take median-of-some and also sort those elements right away before returning the pivot. It's a minor improvement.

Andrei

On Sat, Oct 9, 2010 at 9:11 AM, Stewart Gordon <smjg_1998@yahoo.com> wrote:

> On 08/10/2010 00:39, Tomek Sowiński wrote:
> <snip>
>
>> What's the halting problem?
>>
>
> Basically, it's the challenge of determining algorithmically whether an arbitrary algorithm given arbitrary input will eventually halt or carry on running forever.
>
> The point is that the halting problem is known to be unsolvable.  The standard proof of this is as follows.  Suppose the halt analyser algorithm we seek exists.  Call it WillHalt(Algorithm, Input).  Then we can consider WillHalt(Algorithm, Algorithm).
>
> Then we can define a new algorithm, LoopIfHaltsOnItself(Algorithm), defined
> as
>
> if WillHalt(Algorithm, Algorithm) then
>    loop forever
> else
>    return
>
> Now try to analyse the outcome of LoopIfHaltsOnItself(LoopIfHaltsOnItself).
>
>
> Personally, I think it's a shame that the halting problem can't be solved.
>  If it could, we could use it to solve many mathematical problems that have
> as it happens remained unsolved for centuries.
>
> Stewart.


Or  more poetically,

No general procedure for bug checks succeeds.
Now, I won’t just assert that, I’ll show where it leads:
I will prove that although you might work till you drop,
you cannot tell if computation will stop.

For imagine we have a procedure called P
that for specified input permits you to see
whether specified source code, with all of its faults,
defines a routine that eventually halts.

You feed in your program, with suitable data,
and P gets to work, and a little while later
(in finite compute time) correctly infers
whether infinite looping behavior occurs.

If there will be no looping, then P prints out `Good.’
That means work on this input will halt, as it should.
But if it detects an unstoppable loop,
then P reports `Bad!’ — which means you’re in the soup.

Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.

Here’s the trick that I’ll use — and it’s simple to do.
I’ll define a procedure, which I will call Q,
that will use P’s predictions of halting success
to stir up a terrible logical mess.

For a specified program, say A, one supplies,
the first step of this program called Q I devise
is to find out from P what’s the right thing to say
of the looping behavior of A run on A.

If P’s answer is `Bad!’, Q will suddenly stop.
But otherwise, Q will go back to the top,
and start off again, looping endlessly back,
till the universe dies and turns frozen and black.

And this program called Q wouldn’t stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own source code, just what will it do?
What’s the looping behavior of Q run on Q?

If P warns of infinite loops, Q will quit;
yet P is supposed to speak truly of it!
And if Q’s going to quit, then P should say `Good’
— which makes Q start to loop! (P denied that it would.)

No matter how P might perform, Q will scoop it:
Q uses P’s output to make P look stupid.
Whatever P says, it cannot predict Q:
P is right when it’s wrong, and is false when it’s true!

I’ve created a paradox, neat as can be —
and simply by using your putative P.
When you posited P you stepped into a snare;
Your assumption has led you right into my lair.

So where can this argument possibly go?
I don’t have to tell you; I’m sure you must know.
By reductio, there cannot possibly be
a procedure that acts like the mythical P.

You can never find general mechanical means
for predicting the acts of computing machines.
It’s something that cannot be done. So we users
must find our own bugs. Our computers are losers!
- Geoffrey K. Pullum

On 08/10/2010 00:42, Jonathan M Davis wrote:
> On Thursday, October 07, 2010 16:39:15 Tomek Sowiński wrote:
>
> http://en.wikipedia.org/wiki/Halting_problem
>
> It's a classic problem in computer science. Essentially what it comes down to is
> that you can't determine when - or even if - a program will halt until it
> actually has. It's why stuff like file transfer dialogs can never be totally
> accurate. And best, you can estimate how long a file transfer will take based on
> the current progress, but you can't _know_ when it will complete.

O_o

-- 
Bruno Medeiros - Software Engineer