Блог

Сравнительная форма прилагательного big — больше, а форма превосходной степени — самая большая. Я хотел бы распечатать все такие тройки (early, ранее, earlesty) или (hard, harder, hardesty),…

Я использую Python для открытия wordList.txt он состоит примерно из 5000 слов. Я отлично протестировал свой код на небольшом файле, но он не может выполняться на большом файле, поскольку циклы слишком длинные.

 def puzzleA(wordList):
    tempList1 = []
    tempList2 = []
    tempList3 = []
    for word in wordList:
        if word[-2:]=='er':
            tempList1.append(word)
        if word[-3:]=='est':
            tempList2.append(word)            

    for word1 in wordList:
        for word2 in tempList1:
            if word1==word2[:-2]:
                tempList3.append(word1)
    for word1 in tempList3:
        for word2 in tempList2:
            if word1==word2[:-3]:
                print('{}, {}er, {}'.format(word1,word1,word2))      
  

Можете ли вы, ребята, предложить другой алгоритм для оптимизации времени выполнения, пожалуйста!

Вы можете создать dict с корнем слов в качестве ключей и всеми вариантами в списке в качестве значения. Тогда мы сохраняем только записи с 3 значениями. Таким образом, мы выполняем итерацию только один раз по списку и один раз по созданному нами dict, сохраняя весь процесс O (n).

Мы можем использовать defaultdict для более простого построения dict. Обратите внимание, что root функция может нуждаться в некотором улучшении, проверьте свой список английских прилагательных!

 from collections import defaultdict


def root(word):
    if len(word) < 4:
        return word
    if word[-3:] == 'ier':
        return word[:-3]   'y'
    elif word[-4:] == 'iest':
        return word[:-4]   'y'
    elif word[-2:] == 'er':
        return word[:-2]
    elif word[-3:] == 'est':
        return word[:-3]
    else:
        return word

def find_triples(words):
    out_dict = defaultdict(list)
    for word in words:
        out_dict[root(word)].append(word)

    # keep only the lists with 3 distinct values, sorted by length
    out = [sorted(set(values), key=len) for values in out_dict.values() 
                                   if len(set(values))==3]
    return out


data = ['early', 'earlier', 'earliest', 'or', 'hard', 'harder', 'hardest', 'ignored']
print(find_triples(data))
# [['early', 'earlier', 'earliest'], ['hard', 'harder', 'hardest']]
  

Большое спасибо за публикацию Thierry Lathuille. Прошло 4 часа с тех пор, как я посмотрел на ваш ответ. Я недостаточно хорош, чтобы понимать ваши коды. Я настроил функцию root (word) следующим образом:

 def root(word):
    if len(word) < 4:
        return word
    if word[-3:] == 'ier':
        return word[:-3]   'y'
    elif word[-4:] == 'iest':
        return word[:-4]   'y'
    elif word[-2:] == 'er':
        if word[-4:-3]==word[-3:-2]:
            return word[:-3]
        else:
            return word[:-2]
    elif word[-3:] == 'est':
        if word[-4:-3]==word[-5:-4]:
            return word[:-4]        
        return word[:-3]
    else:
        return word
  

Но сейчас у него есть 2 проблемы:
Во-первых, в списке слов дублируется word, поэтому получается что-то вроде [терри, terry, терьер].

Во-вторых, действительно сложно найти такую тройку [большой, bigger, biggest]

Мой выдает [whin, нытик, нытик], [willy, willier, виллиер], [slat, slater, slatter],…

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

И, Тьерри, если у вас есть время, не могли бы вы объяснить этот код, пожалуйста?

 out = [sorted(values, key=len) for values in out_dict.values() if len(values)==3]
  

Я действительно плохо разбираюсь в понимании списка.

Похоже, что теперь вы боретесь с тем, как последовательно использовать слова. Для вашего сценария вы можете обойтись списком правил замены шаблонов, т. Е. «если слово заканчивается на этот шаблон, замените его на это«. Используя регулярные выражения, вы можете легко указать шаблоны и замены, включая такие вещи, как «если оно заканчивается повторяющейся буквой, замените его одним экземпляром этой буквы».

Например:

 def root(word):
  pattern_replacements = [
    ("e$", ""),    # fine => fin (to match finer, finest)
    ("y$", "i"),   # tiny => tini (to match tinier, tiniest)
    ("er$", ""),
    ("est$", ""),
    (r"([a-z])1$", r"1")  # bigger => big 
  ]

  for pattern, replacement in pattern_replacements:
    word = re.sub(pattern, replacement, word)

  return word


words = "big bigger biggest tiny tinier tiniest fine finer finest same samer samest good gooder goodest".split(" ")
map(root, words)
# ['big', 'big', 'big', 'tini', 'tini', 'tini', 'fin', 'fin', 'fin', 'sam', 'sam', 'sam', 'good', 'good', 'good']