Re: Change to search_n

[Dimitris Xochellis <jimxoch at yahoo dot gr>]

Hi Chris, hi list,

> I'm going to have to check that carefully... one
> problem with your 
> implementation is that you store a temporary value
> in int, and this isn't allowed, I'm fairly certain 
> you have to use iterator_traits<>::difference_type.

You are right. I am not proud about that and I have
already fixed it in my new revision. (In particular my
(_Integer)(__last - __first) expression could produce
very nasty bugs in case that _Integer is char or even
short)

>  Is it this that is causing the problem?

Its mainly the expressions like (__last - __first >
__count) that are producing these warnings. These
expression will fail to work as expected in case
__first > __last.

> 
> The broad definition of my algorithm is:
> 1) Go backwards while predicate is still true.
> 2) if you got "a" predicate accepts in the first
> step, jump forward 
> "n-a" steps.
> 
> I thought the improvement of my algorithm is that
> whenever possible I 
> jump forward, so that this would mean I'd get
> through the vector faster. 
> However as I get to jump further less far, then
> overall the gain isn't 
> worth it (it is for some densities of values, but
> not all, and it 
> greatly increases the complexity)

Nevertheless the basic idea is still very good, it
just needs a little more elaboration and a different
implementation. I am currently working on a
amelioration of my old search_n implementation that I
have published in CodeProject. One of the things that
I have improved is exactly that I am trying to "jump"
after the backtracking. And after that I jump again...

According to my tests, my new implementation seems to
perform better than the old one in most cases (though
there are circumstances when it performs slightly
worse) and is testing less elements in all cases.
Particularly, when the probability of meeting a
matching element is high, it performs great. In the
example I have mentioned in a previous mail (test D of
my article) your implementation is testing 16% of the
overtaken elements, my old implementation is testing
14% of the overtaken elements and my newest one only
10.7% of the overtaken elements. I have to admit that
when the element comparison itself is very fast, then
my new implementation is not always faster in all
compilers, but in case that the comparison is
non-trivial then it really takes off. :)

Bellow I include a draft of this new implementation
and I waiting for your comments.

//---------------------------------------------------

template <class _RandomAccessIter, class _Integer,
class _Tp> inline
_RandomAccessIter search_n(_RandomAccessIter __first,
_RandomAccessIter __last,
                      _Integer __count, const _Tp&
__val)
{
	if (__count <= 0)
		return __first;
	if (__count == 1)
		return std::find(__first, __last, __val);

	typedef
std::iterator_traits<_RandomAccessIter>::difference_type
iter_diff;

	iter_diff __tailSize = __last - __first;
	iter_diff __pattSize = __count;

	if (__tailSize >= __pattSize)
	{
		_RandomAccessIter __backTrack;

		iter_diff __remainder, __prevRemainder;
		iter_diff __skipOffset = __pattSize - 1;
		
		_RandomAccessIter __lookAhead = __first +
__skipOffset;

		for ( ; ; __lookAhead += __pattSize ) // the main
loop...
		{
			//__lookAhead here is always pointing to the last
element of next possible match.
			assert( __tailSize >= __pattSize );
			__tailSize -= __pattSize;

			for ( ; ; ) // the skip loop...
			{
				if (*__lookAhead == __val)
					break;
				if (__tailSize < __pattSize)
					return __last;
				
				__lookAhead += __pattSize;
				__tailSize -= __pattSize;
			}
			
			assert( __tailSize == (__last - __lookAhead) - 1 );
			__remainder = __skipOffset;
			
			for ( __backTrack = __lookAhead - 1; *__backTrack
== __val; --__backTrack )
			{
				if (--__remainder == 0)
					return (__lookAhead - __skipOffset); //Success
			}

			for ( ; ; )
			{
				if (__remainder > __tailSize)
					return __last; //failure

				__lookAhead += __remainder;
				__tailSize -= __remainder;

				if (*__lookAhead == __val)
				{
					__prevRemainder = __remainder;
					__backTrack = __lookAhead;

					do
					{
						if (--__remainder == 0)
							return (__lookAhead - __skipOffset); //Success

					} while ( *--__backTrack == __val);
					
					//adjust remainder for next comparison
					__remainder += __skipOffset - __prevRemainder;
				}
				else
					break;
			}

			//__lookAhead here is always pointing to the
element of the last mismatch.
			if (__tailSize < __pattSize)
				return __last;
		}
	}
	
	return __last; //failure
}

//---------------------------------------------------

Best regards,
Jim Xochellis


____________________________________________________________
Do You Yahoo!?
Αποκτήστε τη δωρεάν @yahoo.gr διεύθυνση σας στο http://www.otenet.gr