KDevelop-PG-Location-Table::positionAt updated with new combined relative/binary algorithm

[Milian Wolff]

On Monday, 26. October 2009 17:07:29 Andreas Pakulat wrote:
> On 26.10.09 17:13:09, Milian Wolff wrote:
> > Hey guys,
> >
> > just wanted to notify you that I updated the algorithm that is used in
> > the KDevelop-PG-Qt LocationTable::positionAt method. The old linear
> > algorithm was of course pretty bad for huge files (i.e. our
> > phpfunctions.php with its 80k lines).
> 
> Nice and btw, of course the linear search algorithm was simply implemented
> because it was easiest and "fast enough" for the few dummy-usecases we(I)
> had back then :)

True, but why did you not use an existing container class?
 
> I have to admit though, that I'd sleep better if we could reuse an existing
> algorithm function like qBinarySearch or one from the stl...

True, but I've implemented a verify function that showed no differences. So 
the function should be failsafe.

Imo we should kill the LocationTable completely and use 
QVector/QLinkedList/QList or anything else. Maybe even std::vector/deck/list.

I'll have to do some more benchmarking for that, but really: Is it worth it? 
It's blazingly fast now!

-- 
Milian Wolff
mail at milianw.de
http://milianw.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20091026/206e1fb6/attachment.sig>