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

[Bertjan Broeksema]

On Monday 26 October 2009 17:37:31 Milian Wolff wrote:
> 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!

I think its worth the effort. In general it is not easy to proof the 
correctness of an implementation of an algorithm. You've implemented a verify 
function, but are you absolutely sure that it covers all cases? (especially 
corner cases). This is the reason that a well tested and much used 
implementation should be preferred whenever possible over a reinvented wheel.

However, the results look nice =:)

Cheers,

Bertjan