Re: Change to search_n

[chris jefferson <caj at cs dot york dot ac dot uk>]

Paolo Carlini wrote:

> Chris Jefferson wrote:
>
> > Hello!
>
>
> Hi and thanks for your message.
>
> During the next days I will analyze in detail your proposal but, 
> first, I'd like to ask your whether your work is related to this 
> algorithm which we were already finding very interesting:
>
>    http://www.codeproject.com/vcpp/stl/SearchN.asp


My minor fix, and more extensive fix turn out to be.. identical to the 
things discussed in this article :) I did come up with it independantly 
(I originally investigated the algorithm because I was using it, looked 
it up in my STL manual and was shocked to find the complexity being far 
higher than I expected).

I had thought about the final part of his dicussion (how even in 
non-random access partners the number of comparisions can be reduced at 
the cost of moving through iterators more). This would be useful when 
comparisons are expensive, but not so in general.

However, it could still be useful, using a little bit of lookahead when 
pointers can be stored in a register I think (ie just pop forward 2 
iterator positions, storing all of them in registers, then check the 
third one to see if it matches. If so, pop back and check the other 2. 
This shouldn't cost anything and posibily save some comparisons).

One other thing I think could slightly improve efficency would be to 
alter the random access version of find (which skips along in 4s) to 
instead of having a trip_count variable, instead reduce the __last 
iterator by (__last-__first)%4, and then continue as normal. One thing 
that pops up from there, is >> 2 really still considered faster than /4, 
and is that a legal thing to do?

Thank you,

Chris