5

私はアレン・ダウニーのThink PythonからPythonを学んでいますが、ここでは演習6で立ち往生しています。私はそれに対する解決策を書きました、そして一見それはここで与えられた答えに対する改善であるように見えました。しかし、両方を実行すると、私のソリューションが答えを計算するのに丸1日（約22時間）かかったのに対し、作成者のソリューションは数秒しかかからなかったことがわかりました。113,812語を含む辞書を反復処理し、それぞれに再帰関数を適用して結果を計算するときに、作成者のソリューションがいかに高速であるかを誰かに教えてもらえますか？

私の解決策：

known_red = {'sprite': 6, 'a': 1, 'i': 1, '': 0}  #Global dict of known reducible words, with their length as values

def compute_children(word):
   """Returns a list of all valid words that can be constructed from the word by removing one letter from the word"""
    from dict_exercises import words_dict
    wdict = words_dict() #Builds a dictionary containing all valid English words as keys
    wdict['i'] = 'i'
    wdict['a'] = 'a'
    wdict[''] = ''
    res = []

    for i in range(len(word)):
        child = word[:i] + word[i+1:]
        if nword in wdict:
            res.append(nword)

    return res

def is_reducible(word):
    """Returns true if a word is reducible to ''. Recursively, a word is reducible if any of its children are reducible"""
    if word in known_red:
        return True
    children = compute_children(word)

    for child in children:
        if is_reducible(child):
            known_red[word] = len(word)
            return True
    return False

def longest_reducible():
    """Finds the longest reducible word in the dictionary"""
    from dict_exercises import words_dict
    wdict = words_dict()
    reducibles = []

    for word in wdict:
        if 'i' in word or 'a' in word: #Word can only be reducible if it is reducible to either 'I' or 'a', since they are the only one-letter words possible
            if word not in known_red and is_reducible(word):
                known_red[word] = len(word)

    for word, length in known_red.items():
        reducibles.append((length, word))

    reducibles.sort(reverse=True)

    return reducibles[0][1]
4

1 に答える 1

5 
wdict = words_dict() #Builds a dictionary containing all valid English words...

おそらく、これにはしばらく時間がかかります。

ただし、 削減しようとする単語ごとに、この同じ不変の辞書を何度も再生成します。なんてもったいない！この辞書を一度作成してから、 の場合のように削減しようとするすべての単語に対してその辞書を再利用するとknown_red、計算時間が大幅に短縮されます。

于 2013-03-13T11:31:16.943 に答える