Tom Lane wrote:
> Jan Urbański <j.urbanski@students.mimuw.edu.pl> 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
