On Sat, Mar 9, 2013 at 10:22 PM, Dann Corbit wrote:
> Yes, you are right. I knew of a median of medians technique for pivot
> selection and I mistook that for the median of medians median selection
> algorithm (which it definitely isn't).
> I was not aware of a true linear time selection of the
On Sat, Mar 9, 2013 at 8:52 PM, Dann Corbit wrote:
> Median of medians selection of the pivot gives you O(n*log(n)).
>
> No. It does make O(n*n) far less probable, but it does not eliminate it.
> If it were possible, then introspective sort would be totally without purpose.
No really, quickso
On Sat, Mar 9, 2013 at 10:32 AM, Dann Corbit wrote:
> There is no such thing as a quicksort that never goes quadratic. It was
> formally proven
The median of medians selection of the pivot gives you O(n*log(n)).
--
greg
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
On Fri, Mar 8, 2013 at 7:43 PM, Dann Corbit wrote:
> Checking for pre-sorted input will not make the routine faster on average.
> However, it prevents a common perverse case where the runtime goes quadratic,
> so sorting 10^6 elements will take K*10^12th operations when the bad
> condition does
-Original Message-
From: Peter Geoghegan [mailto:peter.geoghega...@gmail.com]
Sent: Friday, March 08, 2013 12:00 PM
To: Bruce Momjian
Cc: Dann Corbit; Robert Haas; Tom Lane; PG Hackers
Subject: Re: [HACKERS] Why do we still perform a check for pre-sorted input
within qsort variants?
On
On 8 March 2013 11:48, Bruce Momjian wrote:
> On Fri, Mar 8, 2013 at 07:43:10PM +, Dann Corbit wrote:
>> I seem to recall that a year or two back some study was done on
>> quicksort methodology as used in PostgreSQL. As I recall, the
>> algorithm used in PostgreSQL fared well in the tests.
>
On Fri, Mar 8, 2013 at 07:43:10PM +, Dann Corbit wrote:
> I seem to recall that a year or two back some study was done on
> quicksort methodology as used in PostgreSQL. As I recall, the
> algorithm used in PostgreSQL fared well in the tests.
Well, that's good to hear.
--
Bruce Momjian
>-Original Message-
>From: pgsql-hackers-ow...@postgresql.org
>[mailto:pgsql-hackers-ow...@postgresql.org] On Behalf Of Bruce Momjian
>Sent: Friday, March 08, 2013 11:22 AM
>To: Peter Geoghegan
>Cc: Robert Haas; Tom Lane; PG Hackers
>Subject: Re: [HACKERS] Why do we
On Mon, Feb 25, 2013 at 02:31:21PM +, Peter Geoghegan wrote:
> On 25 February 2013 11:49, Robert Haas wrote:
> > I did attempt to do some tinkering with this while I was playing with
> > it, but I didn't come up with anything really compelling. You can
> > reduce the number of comparisons on
On 25 February 2013 11:49, Robert Haas wrote:
> I did attempt to do some tinkering with this while I was playing with
> it, but I didn't come up with anything really compelling. You can
> reduce the number of comparisons on particular workloads by tinkering
> with the algorithm, but then somebody
On Mon, Feb 25, 2013 at 5:43 AM, Tom Lane wrote:
> Peter Geoghegan writes:
>> In the past, Robert and I have criticised the fact that our qsort
>> implementation (and the various specialisations thereof) each perform
>> a check for pre-sorted input. This check does not appear in the
>> original N
I wrote:
> FWIW, I've been suspicious of that pre-sorted check since the day it
> went in. Bentley was my faculty adviser for awhile in grad school,
> and I know him to be *way* too smart to have missed anything as simple
> as that. But I didn't have hard evidence on which to object to it
> at th
I wrote:
> FWIW, I've been suspicious of that pre-sorted check since the day it
> went in. Bentley was my faculty adviser for awhile in grad school,
> and I know him to be *way* too smart to have missed anything as simple
> as that. But I didn't have hard evidence on which to object to it
> at th
Peter Geoghegan writes:
> In the past, Robert and I have criticised the fact that our qsort
> implementation (and the various specialisations thereof) each perform
> a check for pre-sorted input. This check does not appear in the
> original NetBSD qsort that we lifted our implementation from, and
14 matches
Mail list logo
