linear/relative or binary search algorithm?

[Milian Wolff]

On Monday, 26. October 2009 19:13:54 Jonathan Schmidt-Dominé - Developer 
wrote:
> Hi Milian!
> 
> > I have now implemented my two ideas, i.e. a relative search (relative to
> >  the last search) and a binary search. Of course the latter is faster for
> >  random access, while the former is faster for linear access.
> >
> > To decide which one to use I'm now running callgrind on each of the three
> > (i.e. also the initial algorithm) on the huge phpfunctions.php file.
> >
> > Thank god I have access to always-on machines at my university :)
> >
> > So far I'd say: Implement binary search as it's always fast. I doubt the
> > additional speed in the linear/relative algorithm is significant together
> >  with the other stuff going on during a declaration build.
> 
> Binary-Search is complicate. Iterative usage is a common usecase and a
>  small if with a comparison and a + or - is very cheap. But try it out. ;)
> 
> > I'll publish the results tomorrow (lets hope it finishes in ~12h ;-) ).
> >  Maybe we can find some more bottlenecks this way :)
> >
> > Oh and please review my implementation of the binary search algorithm,
> > you can find it here:
> >
> > http://websvn.kde.org/trunk/playground/devtools/kdevelop-pg-
> > qt/tests/benchmarks.cpp?revision=HEAD&view=markup
> >
> > Note that I never wrote such an algorithm before, hence feedback is much
> > appreciated. Esp. the part where I increase/decrease the iterator by
> > float(upperBound - lowerBound)/2. Is that OK?
> >
> > As you can see in the benchmarks, I've added some tests to verify that
> > all algorithms return the same results.
> >
> > I'd be also interested in testing whether it's significantly slower (if
> > not even faster!) to use e.g. QVector or QList together with qBinaryFind,
> > or a std::vector with a binary_search. Of course that would mean I'd have
> > to benchmark _filling_ the lookup table as well.
> 
> qBinaryFind would also work with pointers. But it searches for exact
>  matches,, positionAt does not do the same.

True, could be that we cannot use existing functions... hmm!

-- 
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/13a87c4d/attachment.sig>