Re: Randomisation for ensuring nlogn complexity in quicksort

Поиск
Список
Период
Сортировка
От Peter Geoghegan
Тема Re: Randomisation for ensuring nlogn complexity in quicksort
Дата
Msg-id CAM3SWZRHi=T2-xPLg4aANHTPqoqkKR3jUctomxHD3D0k-5Zt9w@mail.gmail.com
обсуждение исходный текст
Ответ на Re: Randomisation for ensuring nlogn complexity in quicksort  (Robert Haas <robertmhaas@gmail.com>)
Список pgsql-hackers
Дерево обсуждения 
On Mon, Jul 1, 2013 at 12:32 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> I have been reading the recent discussion and was researching a bit, and I think that we should really go with the
ideaof randomising the input data(if it is not completely presorted), to ensure that we do not get quadratic
complexity.
>
> That doesn't ensure any such thing.  It just makes it less likely.
> But we have existing guards that also make that unlikely, so I'm not
> sure what we'd be gaining.

+1

-- 
Peter Geoghegan

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

Предыдущее
От: Greg Smith
Дата:
Сообщение: Re: fallocate / posix_fallocate for new WAL file creation (etc...)
Следующее
От: Alvaro Herrera
Дата:
Сообщение: Re: pg_resetxlog -m documentation not up to date