patternpythonMinor
Increase performance of Boyer Moore
Viewed 0 times
boyerperformanceincreasemoore
Problem
Here is my Boyer Moore code in Python:
I was wondering what are some small tweaks here and there that I can do to increase the efficiency. Redesigning this code is fine too.
def BoyerMoore(stringy, substring):
if stringy == substring:
return 0
ASCIIcharset = [-1]*256
for x in xrange(len(stringy)):
ASCIIcharset[ord(stringy[x])] = x
stringLen = len(stringy)
substringLen = len(substring)
for i in xrange(stringLen - substringLen):
skip = 0
for j in xrange(substringLen - 1 , 0, -1):
if stringy[i + j] is not substring[j]:
skip = max(1, j - ASCIIcharset[ord(stringy[i + j])])
i += skip
break
if skip == 0:
return i
return -1I was wondering what are some small tweaks here and there that I can do to increase the efficiency. Redesigning this code is fine too.
Solution
The following examples show that there is something wrong in your code :
print(BoyerMoore('azertyuiop', 'zertyuio' )) # 1 - fair enough
print(BoyerMoore( 'zertyuio' , 'azertyuiop')) # -1 - so far so good
print(BoyerMoore('azertyuiop', 'azertyuiop')) # 0 - ok
print(BoyerMoore('abcdefgiop', 'iop')) # -1 - looks wrong to me
print(BoyerMoore('iop' , 'abcdefgiop')) # -1 - ok (just wanted to check that arguments were in the right order)Code Snippets
print(BoyerMoore('azertyuiop', 'zertyuio' )) # 1 - fair enough
print(BoyerMoore( 'zertyuio' , 'azertyuiop')) # -1 - so far so good
print(BoyerMoore('azertyuiop', 'azertyuiop')) # 0 - ok
print(BoyerMoore('abcdefgiop', 'iop')) # -1 - looks wrong to me
print(BoyerMoore('iop' , 'abcdefgiop')) # -1 - ok (just wanted to check that arguments were in the right order)Context
StackExchange Code Review Q#47508, answer score: 2
Revisions (0)
No revisions yet.