Tom Lane wrote:
=?UTF-8?B?SmFuIFVyYmHFhHNraQ==?= <[EMAIL PROTECTED]> writes:
Come to think of it, the current code is in a way a variant of Lossy
Counting, it's just doing the pruning after each and every new element,
isn't it?
Interesting comment. In LC's terms we have w=1 therefore e=1 therefore
the maximum error is as bad as possible?
Well, the similarity doesn't go as far as that IMHO. Having a LC
algorithm with w = 1 you'd just go about adding one element, and then
deleting it, 'cause is has f = 1 and delta = b_current - 1, so f + delta
<= b_current.
But scanning the list linearily each time *and* keeping it incrementally
sorted sure didn't help the preformance ;)
BTW: I don't know if you've noticed - I settled for adding elements to a
hashtable and sequentially scanning it at prune time, instead of
maintaining an additional array of pointers to hashtable entires and
qsort()ing it every time a pruning is called for. I only qsort() the
pointers for determining the final MCLs (by allocating an array of the
same size as the hashtable, copying the pointers and applying qsort()).
That saves a lot of headaches and, if I did my calculations right, is
asymptotically faster.
Cheers,
Jan
--
Jan Urbanski
GPG key ID: E583D7D2
ouden estin
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
