Verbesserung der Boyer-Moore-Saiten-Suche

Question

Ich habe mit dem Boyer-Moore-Stech-Suchalgorithmus herumgespielt und mit einem Basiscode-Set von Shriphani Palakodety begonnen. Ich habe 2 zusätzliche Versionen (v2 und v3) erstellt - jede macht einige Modifikationen wie Entfernen der Funktion len() aus der Schleife und dann Refactoring der while/if-Bedingungen. Von v1 bis v2 sehe ich eine Verbesserung von 10% -15% und von v1 zu v3 eine Verbesserung von 25% -30% (signifikant).

Meine Frage ist: Hat jemand irgendwelche zusätzlichen Mods, die Leistung noch mehr verbessern würden (wenn Sie als v4 einreichen können) - behalten die Basis "algorithm" Boyer-Moore treu.

---

#!/usr/bin/env python 
#original Boyer-Moore implementor (v1): Shriphani Palakodety 

import time 

bcs = {} #the table 

def goodSuffixShift(key): 
    for i in xrange(len(key)-1, -1, -1): 
    if key[i] not in bcs.keys(): 
     bcs[key[i]] = len(key)-i-1 


#---------------------- v1 ---------------------- 
def searchv1(text, key): 
    #base from Shriphani Palakodety fixed for single char 
    i = len(key)-1 
    index = len(key) -1 
    j = i 

    while True: 
     if i < 0: 
      return j + 1 
     elif j > len(text): 
      return "not found" 
     elif text[j] != key[i] and text[j] not in bcs.keys(): 
      j += len(key) 
      i = index 
     elif text[j] != key[i] and text[j] in bcs.keys(): 
      j += bcs[text[j]] 
      i = index 
     else: 
      j -= 1 
      i -= 1 

#---------------------- v2 ----------------------       
def searchv2(text, key): 
    #removed string len functions from loop 
    len_text = len(text) 
    len_key = len(key) 
    i = len_key-1 
    index = len_key -1 
    j = i 

    while True: 
    if i < 0: 
     return j + 1 
    elif j > len_text: 
     return "not found" 
    elif text[j] != key[i] and text[j] not in bcs.keys(): 
     j += len_key 
     i = index 
    elif text[j] != key[i] and text[j] in bcs.keys(): 
     j += bcs[text[j]] 
     i = index 
    else: 
     j -= 1 
     i -= 1       

#---------------------- v3 ---------------------- 
def searchv3(text, key): 
    #from v2 plus modified 3rd if condition - breaking down the comparison for efficency, 
    #modified the while loop to include the first if condition (oppposite of it) 
    len_text = len(text) 
    len_key = len(key) 
    i = len_key-1 
    index = len_key -1 
    j = i 

    while i >= 0 and j <= len_text: 
    if text[j] != key[i]: 
      if text[j] not in bcs.keys(): 
       j += len_key 
       i = index 
      else: 
       j += bcs[text[j]] 
       i = index 
    else: 
     j -= 1 
     i -= 1 

    if j > len_text: 
    return "not found" 
    else: 
     return j + 1 


key_list = ["POWER", "HOUSE", "COMP", "SCIENCE", "SHRIPHANI", "BRUAH", "A", "H"] 

text = "SHRIPHANI IS A COMPUTER SCIENCE POWERHOUSE" 

t1 = time.clock() 
for key in key_list: 
    goodSuffixShift(key) 
    #print searchv1(text, key) 
     searchv1(text, key) 
    bcs = {} 

t2 = time.clock() 
print 'v1 took %0.5f ms' % ((t2-t1)*1000.0) 

t1 = time.clock() 
for key in key_list: 
    goodSuffixShift(key) 
    #print searchv2(text, key) 
     searchv2(text, key) 
    bcs = {} 

t2 = time.clock() 
print 'v2 took %0.5f ms' % ((t2-t1)*1000.0) 

t1 = time.clock() 
for key in key_list: 
    goodSuffixShift(key) 
    #print searchv3(text, key) 
     searchv3(text, key) 
    bcs = {} 

t2 = time.clock() 
print 'v3 took %0.5f ms' % ((t2-t1)*1000.0) 

Answer 1

verwenden "in bcs.keys()" eine Liste erstellen und dann eine O (N) Suche nach der Liste zu tun - nur "in bcs" verwenden.

Führen Sie die Funktion goodSuffixShift (Schlüssel) in der Suchfunktion aus. Zwei Vorteile: Der Aufrufer hat nur eine API zu verwenden, und Sie vermeiden, bcs als global (schrecklich ** 2) zu haben.

Ihr Einzug ist an mehreren Stellen falsch.

aktualisieren

Dies ist nicht der Boyer-Moore-Algorithmus (die Tabellen TWO-Lookup verwendet). Es sieht mehr wie der Boyer-Moore-Horspool-Algorithmus aus, der nur die erste BM-Tabelle verwendet.

Eine wahrscheinliche Beschleunigung: Fügen Sie die Zeile 'bcsget = bcs.get' hinzu, nachdem Sie das bcs dict eingerichtet haben. Dann ersetzen:

if text[j] != key[i]: 
    if text[j] not in bcs.keys(): 
     j += len_key 
     i = index 
    else: 
     j += bcs[text[j]] 
     i = index 

mit:

if text[j] != key[i]: 
    j += bcsget(text[j], len_key) 
    i = index 

Update 2 - zurück zu den Wurzeln, wie immer der Code korrekt, bevor Sie

Version 1 hat einige Fehler zu optimieren, die Sie durchgeführt haben Weiter zu den Versionen 2 und 3. Einige Vorschläge:

Ändern Sie die nicht gefundene Antwort von "nicht gefunden" auf -1. Dies macht es kompatibel mit text.find (key), mit dem Sie Ihre Ergebnisse überprüfen können.

Weitere Textwerte erhalten, z. "R" * 20, "X" * 20 und "XXXSCIENCEYYY" zur Verwendung mit Ihren vorhandenen Schlüsselwerten.

Lash einen Test-Harnisch, so etwas wie dies oben:

func_list = [searchv1, searchv2, searchv3] 
def test(): 
    for text in text_list:  
     print '==== text is', repr(text) 
     for func in func_list: 
      for key in key_list: 
       try: 
        result = func(text, key) 
       except Exception, e: 
        print "EXCEPTION: %r expected:%d func:%s key:%r" % (e, expected, func.__name__, key) 
        continue 
       expected = text.find(key) 
       if result != expected: 
        print "ERROR actual:%d expected:%d func:%s key:%r" % (result, expected, func.__name__, key) 

Run, dass die Fehler in v1 beheben, führt den Updates vor, erneut die Tests laufen, bis sie alles in Ordnung sind. Dann können Sie Ihr Zeitmessgeschirr entlang derselben Linie aufräumen und sehen, was die Leistung ist. Dann können Sie sich hier melden, und ich gebe Ihnen meine Vorstellung davon, wie eine searchv4-Funktion aussehen sollte ;-)