Re: gsoc, text search selectivity and dllist enhancments

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