First different char in two strings?
Emile van Sebille
emile at fenx.com
Mon May 22 21:58:20 EDT 2000
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,
Emile van Sebille
emile at fenx.com
-------------------
----- Original Message -----
From: Darrell Gallion <darrell at dorb.com>
To: <emile at fenx.com>
Cc: <python-list at python.org>
Sent: Monday, May 22, 2000 9:29 PM
Subject: Re: First different char in two strings?
> Emile wrote:
> > But, being as I generally find that the obvious way is often the
> > fastest,
> > or close enough, here's the obvious:
> >
> > a = "this is a test"
> > b = "this is not a test"
> > for i in range(len(a)):
> > if b[i] != a[i]:
> > break
> > print i
> >
> That was fun. The binary search won.
>
> Output:
> 1499999
> 3.86000001431 Sec
> 1499999
> 0.468000054359 Sec
> 1499999
> 0.0939999818802 Sec
> ###########################################
>
> import string, re
>
> s1="abc"*500000
> s2 = s1[:]
> s2 = s1[:-1]+'l'
>
> def algo1(a, b):
> for i in range(len(a)):
> if b[i] != a[i]:
> return i
> return -1
>
>
> def algo2(a, b, pat= re.compile("("+"."*1000+")")):
> aS = pat.split(a)
> bS = pat.split(b)
> offset=0
> for x in xrange(len(aS)):
> if aS[x] != bS[x]:
> i=offset+algo1(aS[x], bS[x])
> return i
> else:
> offset=offset+len(aS[x])
> return -1
>
> def algo3(a, b):
> aLen=len(a)
> if aLen < 2:
> if a[0] != b[0]:
> return 0
> if a[1] != b[1]:
> return 1
> return -1
>
> aLen=aLen/2
> aL= a[:aLen]
> bL= b[:aLen]
> if aL==bL:
> aH=a[aLen:]
> bH=b[aLen:]
> if aH==bH:
> return -1
> else:
> return aLen+algo3(aH, bH)
> else:
> return aLen+algo3(aL, bL)
>
>
> import time
> t1=time.time()
> print algo1(s1, s2)
> print time.time()-t1
>
> t1=time.time()
> print algo2(s1, s2)
> print time.time()-t1
>
> t1=time.time()
> print algo3(s1, s2)
> print time.time()-t1
>
>
>
>
More information about the Python-list
mailing list