как я могу сделать этот код, который позволяет компьютеру выбирать слово из wordList из 83667 слов быстро?

Question

Укажите более быструю версию compChooseWord (рука, wordList, n) функция. вот некоторые подробности.

wordList - это список из 83667 слов;

рука { 'а': 1, 'р': 2, 'S': 1, 'е': 1, 'л': 1}

п является положительным целым числом

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 

Обеспечить альтернативную быструю версию для следующих функций

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

согласно @mroman комментария выше: самой простой оптимизации есть сортировка этого нужно просто wordist в обратном значении оценки, и останавливается, когда вы находите первое слово.

Python сортировки очень эффективно такие вещи, как это, так как это позволяет функция getWordScore itsef будет использоваться в качестве ключа для сортировки, и он может даже принять во внимание размер рук при сортировке - так что ваш поиск будет:

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 

Но, если этого недостаточно, вы также можете переписать isValidWord, чтобы быть немного быстрее, сначала проверив, есть ли у вас нужные буквы, чтобы сформировать слово, используя «set» s, и только пятно так , проверьте количество писем, используя более дорогой метод проверки количества букв:

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» - просто назовите их «буквами». Во-вторых: вам не нужно много вспомогательных переменных, которые вы переносите, например «wordCount»: когда цикл закончен, вы проверите все буквы. А также, просто возвращает значение False, вместо того, установив ДОПОЛНИТЕЛЬНОЕ (и плохо имени) b переменную, чтобы указать матч не удалось так или иначе

И в качестве бонуса вы можете использовать расширенный оператор присваивания -=, чтобы избежать повторения выражения с обеих сторон равенства.