python – 如何提高这种递归函数的性能?

我正在尝试编写一个函数来搜索str的substr,考虑到编写奇怪字母的不同可能性,例如丹麦语中的æ,ø,å.例如,您可以搜索’Ålborg’,如果有,在str中说’Aalborg’,函数将返回true.

以下功能有效,但性能难以忍受.你会建议什么来提高性能?

def danish_tolerating_search(substr, str):
    '''Figure out if substr is in str, taking into account
    possible deviations in writing letters æ, ø, å.
    æ  <->  ae a ea
    ø  <->  oe o
    å  <->  aa a o
    '''

    # normalize input
    substr = substr.lower().replace('aa',u'å')
    str = str.lower()

    # normalized recursive search
    # TODO fix perfomance
    def s(substr, str):
        if str.find(substr) >= 0: return True
        if substr.find(u'æ') >= 0:
            if    s(substr.replace(u'æ','ae', 1), str): return True
            elif  s(substr.replace(u'æ', 'a', 1), str): return True
            elif  s(substr.replace(u'æ','ea', 1), str): return True
        if str.find(u'æ') >= 0:
            if    s(substr, str.replace(u'æ','ae', 1)): return True
            elif  s(substr, str.replace(u'æ', 'a', 1)): return True
            elif  s(substr, str.replace(u'æ','ea', 1)): return True
        if substr.find(u'ø') >= 0:
            if    s(substr.replace(u'ø','oe', 1), str): return True
            elif  s(substr.replace(u'ø', 'o', 1), str): return True
        if str.find(u'ø') >= 0:
            if    s(substr, str.replace(u'ø','oe', 1)): return True
            elif  s(substr, str.replace(u'ø', 'o', 1)): return True
        if substr.find(u'å') >= 0:
            if    s(substr.replace(u'å','aa', 1), str): return True
            elif  s(substr.replace(u'å', 'a', 1), str): return True
            elif  s(substr.replace(u'å', 'o', 1), str): return True
        if str.find(u'å') >= 0:
            if    s(substr, str.replace(u'å','aa', 1)): return True
            elif  s(substr, str.replace(u'å', 'a', 1)): return True
            elif  s(substr, str.replace(u'å', 'o', 1)): return True
        return False

    return s(substr, str)
我认为你应该完全消除递归.例如,您可以决定输入字符串的“正常形式”,相应地转换它们(即替换那些“模棱两可”的字符),而不是完成所有查找和替换的操作.

return substring in string_

另请注意,您不需要一起调用查找和替换,后者就足够了.如果找不到搜索字符串,则替换只是不会替换任何内容.

相关文章
相关标签/搜索