python - 如何提高这个递归函数的性能？

Question

我正在尝试编写一个函数，该函数将在 str 中搜索 substr，同时考虑到编写奇怪字母的不同可能性，例如丹麦语中的 æ、ø、å。例如，您可以搜索“Ålborg”，如果存在，函数将返回 true，在 str 中说“Aalborg”。

下面的功能可以，但是性能不堪。您会推荐什么来提高性能？

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)

Answer 1

我认为你应该完全消除递归。例如，您可以决定输入字符串的“正常形式”，并相应地转换它们(即替换那些“不明确的” "字符)并做一个简单的

return substring in string_

另请注意，您不需要同时调用find 和replace，后者就足够了。如果未找到搜索字符串，则替换不会替换任何内容。