どうすればコンピュータが単語リストから83667語の単語をすばやく選択できるようにすることができますか？

Question

のより速いバージョンを提供してください。compChooseWord（hand、wordList、n）関数。 ここにいくつかの詳細があります。

wordListは83667語のリストです。

手は{ 'A'：1、 'P'：2 'S'：1、 'E'：1、 'L'：1}

nは正の整数

SCRABBLE_LETTER_VALUES = { 
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10 
} 

def getWordScore(word, n): 

    score=0 
    for i in word: 
     if i in SCRABBLE_LETTER_VALUES: 
      score=score+SCRABBLE_LETTER_VALUES[i] 
    score=score*len(word) 

    if len(word)==n: 
     score=score+50 

    return score 
def isValidWord(word, hand, wordList): 

    """ 
    Returns True if word is in the wordList and is entirely 
    composed of letters in the hand. Otherwise, returns False. 

    Does not mutate hand or wordList. 

    word: string 
    hand: dictionary (string -> int) 
    wordList: list of lowercase strings 
    """ 


    c=True 
    wordCount=len(word) 
    handCopy=hand.copy() 
    for i in word: 
     if i in hand: 
      handCopy[i]=handCopy.get(i,0)-1 
      wordCount=wordCount-1 
      if handCopy[i]<0: 
       c=False 
       break 

    b=word in wordList and wordCount==0 

    return b and c 

上記@mromanコメントを1として機能

def compChooseWord(hand, wordList, n): 

    """ 
    Given a hand and a wordList, find the word that gives 
    the maximum value score, and return it. 

    This word should be calculated by considering all the words 
    in the wordList. 

    If no words in the wordList can be made from the hand, return None. 

    hand: dictionary (string -> int) 
    wordList: list (string) 
    n: integer (HAND_SIZE; i.e., hand size required for additional points) 

    returns: string or None 
    """ 

    bestScore = 0 
    bestWord = None 
    for word in wordList: 
     if isValidWord(word, hand, wordList): 
      score = getWordScore(word, n) 
      if (score > bestScore): 
       bestScore = score 
       bestWord = word 
    return bestWord 

Answer 1

を以下に別の高速化バージョンを提供します：逆スコア値にwordistをソートjsutあり、最も簡単な最適化、そしてあなたが見つけたときに停止最初の言葉。

それが機能getWordScoreは、ソートのキーとして使用することitsef、およびソート時にも、アカウントにあなたの手の大きさを取ることができますことができますようPythonのソートは、このようなものに非常に効率的である - ので、あなたの検索は次のようになります。

def compChooseWord(hand, wordList, n): 

    bestScore = 0 
    bestWord = None 
    wordList = sorted(wordList, key=lambda word: getWordScore(word, n)) 
    for word in wordList: 
     if isValidWord(word, hand, wordList): 
      break 
    else: 
     # No "break" means: end of the list with no word-matching 
     return None 
    return word 

しかし、それでも十分でない場合は、「set」を使用して単語を形成するために必要な文字があるかどうかを最初に確認して、少し速くなるようにisValidWordを書き直すことができますより高価な文字数の確認方法を使用して文字数を確認します。

def isValidWord(word, hand, wordList): 

    word_letters = set(word) 
    if not word_letters.intersection(hand.keys()): 
     # You don't have the needed letters to start with 
     return False 
    handCopy=hand.copy() 

    for letter in word: 
     handCopy[letter] -= 1 
     if handCopy[letter] < 0: 
      return False    

    return wordCount == 0 

「単語」内の「文字」をループしている場合は、「i」という名前の理由はありません。単に「文字」と呼んでください。 2つ目は、「wordCount」のような持ち運びに便利な変数はほとんど必要ありません。ループが終了すると、すべての文字をチェックします。とにかく失敗したことを示すように、厄介な名前のb変数を設定するのではなく、Falseを返します。

また、拡張代入演算子-=を使用して、平等の