Выполнение алгоритма проверки анаграммы менее чем за секунду

Question

Я создал этот алгоритм, чтобы проверить, являются ли две строки анаграммой друг друга. В этом упражнении я рассматриваю две строки как анаграммы друг друга, если они имеют одинаковые символы или отличаются только на одну. Например, математика и математика - это анаграмма, но даже математика и математика - анаграмма. Мне нужно выполнить этот алгоритм менее чем за секунду, но с некоторыми примерами, включенными в тест, иногда требуется более 10 минут. Очевидно, что это можно сделать намного лучше. Вложенность для l oop - это проблема, но я просто не могу найти возможное решение без этого.

#len(word1) <= len(word2)
def check(word1, word2): 
   lword1 = len(word1)
   lword2 = len(word2)
   sword1 = sorted(word1)
   sword2 = sorted(word2)

   # lword1 == lword2
   if lword1 == lword2: 
       return sword1 == sword2

   # lword1 < lword2, word2 has one more character
   sword2_copy = sword2.copy()
   for c in sword2:
       if c in sword1:
           sword1.remove(c)
           sword2_copy.remove(c)

   return len(sword1) == 0 and len(sword2_copy) == 1


def main(fin, fout, k):

   words = [line.rstrip('\n') for line in open(fin)] 
   words = [x.strip(' ') for x in words]

   d = {}

   for w1 in words:
       for w2 in words:
           if len(w1) == len(w2) or len(w1) == len(w2) - 1:
               if check(w1, w2):
                   if w1 not in d.keys():
                       d[w1] = [w2]
                   else:
                       d[w1].append(w2)

   highV = list(d.values())[0]
   highK = list(d.keys())[0]
   for key, value in d.items():
       if len(value) > len(highV) or (len(value) == len(highV) and key < highK):
           highK = key
           highV = value

   highV.sort()

   with open(fout, 'w') as f:
       for i in range(len(highV)):
           f.write(highV[i]+' ')
           if (i + 1) % k == 0: 
               f.write('\n')

   return int(len(highV))

Answer 1

Вы должны проверить счетчик из коллекций:

from collections import Counter
str = 'Testanagram'
counter = Counter(str)
print(counter)
> Counter({'a': 3, 'T': 1, 'e': 1, 's': 1, 't': 1, 'n': 1, 'g': 1, 'r': 1, 'm': 1})

Используя это, вы должны быть намного быстрее - вы также можете вычесть один счетчик из другого, чтобы получить разницу

Answer 2

Основная оптимизация будет в check().

Используя что-то вроде collections.Counter, решение выглядит проще, но медленнее:

def check_with_counter(word1, word2):
    c1 = Counter(word1)
    c2 = Counter(word2)
    return sum(((c1 - c2) + (c2 - c1)).values()) < 2

Решение, похожее на ваше, но значительно быстрее (примерно на порядок)

def check_faster(word1, word2):
    # checks faster than check() and works for words of any length (in any order)
    ld = len(word1) - len(word2)
    if ld in [0, 1]:
        sword_long = list(word1)
        sword_short = list(word2)
        if ld == 0:
            return sword_long == sword_short
    elif ld == -1:
        sword_long = list(word2)
        sword_short = list(word1)
    else:
        return False

    for c in sword_short:
        try:
            sword_long.remove(c)
        except ValueError:
            pass

    return len(sword_long) < 2

, а использовать его несколько быстрее run():

def run_faster(fin, fout, k):
    words = [line.rstrip('\n') for line in open(fin)]
    words = [x.strip(' ') for x in words]

    d = {}

    for w1 in words:
        for w2 in words:
            if check_faster(w1, w2):
                if w1 not in d.keys():
                    d[w1] = [w2]
                else:
                    d[w1].append(w2)

    most = 0
    most_anagrams = []
    for word, anagrams in d.items():
        if len(anagrams) > most:
            most = len(anagrams)
            most_anagrams = anagrams

    most_anagrams.sort()

    with open(fout, 'w') as f:
        for i in range(len(most_anagrams)):
            f.write(most_anagrams[i]+' ')
            if (i + 1) % k == 0:
                f.write('\n')

    return int(len(most_anagrams))

Answer 3

Кажется, это работает довольно быстро, хотя для моего списка слов (235 886 из них, полный список из /usr/share/dict/words) это занимает около 2 секунд, так что оно все еще может быть слишком медленным для вас. Но, честно говоря, как часто вы планируете запускать его по всему списку?

with open('/usr/share/dict/words', 'r') as f:
    wordlist = f.readlines()

wordlist = [word.strip() for word in wordlist]
wordlist = [(word,''.join(sorted([kar for kar in word]))) for word in wordlist]

worddict = {}
for word in wordlist:
    if word[1] in worddict:
        worddict[word[1]].append(word[0])
    else:
        worddict[word[1]] = [word[0]]

for word in wordlist:
    if len(worddict[word[1]]) > 1:
        print (worddict[word[1]])

Результат:

['aal', 'ala']
['aam', 'ama']
['aba', 'baa']
['abac', 'caba']
['abactor', 'acrobat']
['abaft', 'bafta']
['abalone', 'balonea']
...
(27,390 lines omitted for brevity)
['ozotype', 'zootype']
['gazy', 'zyga']
['glazy', 'zygal']
[Finished in 2.1s]

Он создает словарь с отсортированными символами каждого слова в качестве ключ и список, содержащий только само это слово в качестве его начального значения . Если ключ уже присутствует в словаре, слово добавляется в его список. Тогда нужно только напечатать все списки, длина которых превышает 1 элемент.

Побочным эффектом является то, что все слова анаграммы появляются несколько раз. Это логика c для вас: incomputable, который находится в этом списке слов, является анаграммой uncompatible, и, следовательно, uncompatible (по определению также в этом списке) является анаграммой incomputable. QED.¹

Самый большой набор найденных им слов анаграммы:

['angor', 'argon', 'goran', 'grano', 'groan', 'nagor', 'orang', 'organ', 'rogan']

и интересная пара противоположностей

['misrepresentation', 'representationism']

Список даже содержит слово `pythoni c ':

['hypnotic', 'phytonic', 'pythonic', 'typhonic']

^{¹ После попытки: печать каждой комбинации только один раз оказалась тривиальной. Он сокращает список до 12 189 «уникальных» наборов, и проверка заняла еще 0,1 секунды.}