Re: [HACKERS] Re: about 7.0 LIMIT optimization

>>> QuickSort: 1.6E+14
>>> SortStop: 1.5E+11
>
>> Are there some zeroes missing here? That sounds like an awful lot of
>> operations for a quicksort of only 1E5 elements...

> Yeah, obviously one or more of his numbers are wrong. Let's see, a
> [...]

Yes I'm sorry, those numbers were completely wrong, I shoud have realized immediately. Here are the correct ones:

QuickSort: 1.66096e+06
SortStop: 1.00327e+05

>> The obvious way to do it would be with a heap-based sort. After you've
>> built the heap, you pull out the first ten elements and then stop.
>> Offhand this only seems like it'd save about half the work, though,
>> so maybe Roberto has a better idea.

> I'd like to see some elaboration.

It is, indeed, a heap-based sort, but you don't need to do so many insertions in the heap.
It works like that:

- put first 10 rows in the heap, whith the worst value on head
- compare each other 99990 rows with the current head
- if new row is better, then
trash current head and insert new row into the heap,
otherwise trash the new row.

In this way the number of insertions in the heap is considerably lower (you can find more details on Knuth, vol III). Moreover, only <N> rows (10 in this case) are kept in memory at the same time, reducing the probability to need an external-sort.

Regards

Roberto Cornacchia

===========================================================

VIRGILIO MAIL - Il tuo indirizzo E-mail gratis e per sempre
http://mail.virgilio.it/

VIRGILIO - La guida italiana a Internet
http://www.virgilio.it/