Re: [HACKERS] qsort again

Поиск
Список
Период
Сортировка
От Ron
Тема Re: [HACKERS] qsort again
Дата
Msg-id 7.0.1.0.2.20060216082618.03ad7e48@earthlink.net
обсуждение исходный текст
Ответ на Re: [HACKERS] qsort again  (Florian Weimer <fw@deneb.enyo.de>)
Список pgsql-performance
At 07:10 AM 2/16/2006, Florian Weimer wrote:
>* Neil Conway:
>
> > On Wed, 2006-02-15 at 18:28 -0500, Tom Lane wrote:
> >> It seems clear that our qsort.c is doing a pretty awful job of picking
> >> qsort pivots, while glibc is mostly managing not to make that mistake.
> >> I haven't looked at the glibc code yet to see what they are doing
> >> differently.
> >
> > glibc qsort is actually merge sort, so I'm not surprised it avoids this
> > problem.
>
>qsort also performs twice as many key comparisons as the theoretical
>minimum.

The theoretical minimum number of comparisons for a general purpose
comparison based sort is O(lgN!).
QuickSort uses 2NlnN ~= 1.38NlgN or ~1.38x the optimum without tuning
(see Knuth, Sedgewick, Corman, ... etc)
OTOH, QuickSort uses ~2x as many =moves= as the theoretical minimum
unless tuned, and moves are more expensive than compares in modern systems.

See my other posts for QuickSort tuning methods that attempt to
directly address both issues.


Ron



В списке pgsql-performance по дате отправления:

Предыдущее
От: Peter Childs
Дата:
Сообщение: Re: Postgres slower than MS ACCESS
Следующее
От: Markus Schaber
Дата:
Сообщение: Re: qsort again (was Re: Strange Create Index