Re: gsoc, text search selectivity and dllist enhancments

Tom Lane wrote:
> =?UTF-8?B?SmFuIFVyYmHFhHNraQ==?= <j(dot)urbanski(at)students(dot)mimuw(dot)edu(dot)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