linear/relative or binary search algorithm?

[Jonathan Schmidt-Dominé - Developer]

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.

------------------------

Automatisch eingefügte Signatur:
Es lebe die Freiheit!
Stoppt den Gebrauch proprietärer Software!
Operating System: GNU/Linux
Kernel: Linux 2.6.31-ARCH
Distribution: Arch Linux
Qt: 4.5.1
KDE: 4.3.71 (KDE 4.3.71 (KDE 4.4 >= 20091007))
KMail: 1.12.90
http://gnu.org/
http://kde.org/
http://windows7sins.org/