First different char in two strings?

[Emile van Sebille]

Darrell,

I knew before ever responding that the binary
search would of course be the fastest.  Originally,
I was simply trying to make the point that without
knowing what kind of strings you'll be comparing,
or the range of possible strings anyway, that you
can't design the right algorithm.  In that case,
the binary search is probably the right thing.

But, for example, if you know that they're going
to be long, and if they're different, it's likely 
to be in the first few bytes, then a different 
method may out-perform the binary search.  It all
depends on the data.

Anyway, I resisted posting this yesterday:  ;-)

def algo5(a, b):
    return len(("".join(map(lambda a,b: str(a==b),a,b)).split("0"))[0])

But-it-gets-beat-by-the-binary-search-as-well-ly y'rs

Emile van Sebille
emile at fenx.com
-------------------


----- Original Message ----- 
From: Darrell Gallion <dgallion1 at yahoo.com>
To: <emile at fenx.com>; <python-list at python.org>
Sent: Tuesday, May 23, 2000 10:00 AM
Subject: Re: First different char in two strings?


> Emile wrote:
> >Ah, but with only a minor mod, time it again: ;-)
> >a = "abc"*
> >b = a[:-1]+'l'
> > 
> >for i in range(len(a)-1,0,-1):
> >  if b[i] != a[i]:
> >    break
> >print i
> > 
> >Life's-easier-when-you-get-to-select-the-test-case-ly
> y'rs,
>  
> I missed the meaning of the ";-)" 
> Then didn't read close enough the
> "range(len(a)-1,0,-1)"
> But your absolutely correct
> "Life's-easier-when-you-get-to-select-the-test-case-ly
> y'rs"
> 
> Unexpectedly the binary search still wins.
> Change "range" to "xrange" and it becomes faster.
> ********
> 1499999
> 0.00999999046326 sec Reverse linear
> 1499999
> 0.0900000333786 sec Binary search
> ********
> 
> But the strings have to be the same length.
> 
> 
> --Darrell Gallion 
> 
> 
> 
> 
> 
> 
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Send instant messages & get email alerts with Yahoo! Messenger.
> http://im.yahoo.com/
> 
> -- 
> http://www.python.org/mailman/listinfo/python-list
>