Целочисленное сравнение в python замедляет все до ползания

Question

Следующий код вызывает у меня огромные головные боли:

def extract_by_letters(letters, dictionary):

    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               if word in dictionary: #I cant leave this line out
                   dictionary.remove(word)

    return dictionary

Прежде всего: строка «если слово в словаре». Почему я не могу это оставить? Я получаю сообщение об ошибке ValueError: list.remove (x): x отсутствует в списке

Но это, очевидно.

Второе: словарь - это файл, содержащий около 50 000 слов, разделенных переносами строк. Приведенный выше код занимает около 2 минут для запуска ... Wayyy слишком долго. Я немного поиграл с кодом и обнаружил, что строка:

if word.count(letter) != letters.count(letter):

кажется, вызывает все мои проблемы. Если я вычеркну эту строку (которая полностью испортит вывод), функции потребуется около 2 секунд, чтобы пройти словарь.

Я думал, что это функции подсчета, но это не так.

если я изменю оператор if на что-то вроде:

print word.count(letter) 
print letters.count(letter)

запуск функции занимает около 3 секунд.

Я убежден, что это сравнение. Любые другие предложения? Есть ли лучший способ сделать это?

Заранее спасибо!

Answer 1

Причина, по которой вы получаете исключение, заключается в том, что если количество букв совпадает для более чем одной буквы, вы пытаетесь удалить слово более одного раза

Причина, по которой оно настолько медленное, состоит в том, что внутри вас есть петлициклы внутри циклов.

Если вы напишете одно или два предложения о том, что функция должна делать, было бы намного проще ее реорганизовать.В то же время, это остановит вас, проверяя, нужно ли удалить слово после того, как вы уже удалили его.

def extract_by_letters(letters, dictionary):
    for word in dictionary[:]:  # bad idea to change this while you iterate over it
        for letter in letters:
            if word.count(letter) != letters.count(letter):
                dictionary.remove(word)
                break
    return dictionary

Если словарь равен set, вы должны немного ускориться.Если словарь имеет значение list, это должно привести к значительному ускорению

Answer 2

Вот функция, которая должна обеспечить значительное ускорение:

def extract_by_letters(letters,dictionary):
    letdict = zip(set(letters),[letters.count(let) for let in set(letters)])
    outarr = []
    for word in dictionary:
        goodword = True
        for letter in letdict:
            if word.count(letter) != letdict[letter]:
                goodword = False
                break
        if goodword:
            outarr.append(word)
    return outarr

Вот оптимизации, которые я сделал:

1. Составлен словарь букв с соответствующими им частотами. Таким образом, вы не будете использовать letters.count снова и снова, когда вам нужно выполнить этот процесс только один раз и сохранить результаты.

2. Вместо того, чтобы удалять слова из словаря, я добавляю их в массив, который возвращается из функции. Если у вас огромный словарь, скорее всего, совпадут только несколько слов. Кроме того, если переменная словаря является массивом (что я подозреваю), то каждый раз, когда вы вызываете remove, он должен сначала искать слово в словаре (линейно начиная с начала), а затем удалять его. Его быстрее удалить, щелкнув по индексу удаляемого слова.

3. Выход из цикла при проверке буквы учитывается при обнаружении несоответствия. Это мешает нам делать ненужные проверки, когда у нас уже есть наш ответ.

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

Answer 3

Попробуйте создать вывод вместо удаления из него:

def extract_by_letters(letters, dictionary):
    d = []
    for word in dictionary:
       for letter in letters:
           if word.count(letter)>0:
               d.append(word)
               break
    return d

Или вы можете использовать регулярные выражения:

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    d=[]
    for word in dictionary:
       if regex.search(word):
           d.append(word)
    return d

Или, возможно, самый простой способ:

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    return [word for word in dictionary if regex.search(word)]

Этот последний не занимает заметного времени для сканирования / usr / share / dict / words на моем Mac, который представляет собой список из 234936 слов.

Answer 4

import pprint
from collections import defaultdict

# This is a best approximation to what Bryan is trying to do.
# However the results are meaningless because the list is being
# mutated during iteration over it. So I haven't shown the output.

def extract_by_letters_0(letters, input_list):
    dictionary = input_list.copy()
    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               if word in dictionary: #I cant leave this line out
                   dictionary.remove(word)
    return dictionary

# This avoids the mutation.
# The results are anagrams PLUS letters that don't occur
# in the query. E.g. "same" produces "samehood" but not "sameness"
# ("sameness" has 3*"s" and 2*"e" instead of 1 of each)

def extract_by_letters_1(letters, input_list):
    dictionary = set(input_list)
    ripouts = set()
    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               ripouts.add(word)
    return dictionary - ripouts

def anagram_key(strg):
    return ''.join(sorted(list(strg)))

def check_anagrams(str1, str2):
    return sorted(list(str1)) == sorted(list(str2))

# Advice: try algorithms like this out on a SMALL data set first.
# Get it working correctly. Use different test cases. Have test code
# however primitive that check your results.
# Then if it runs slowly, helpers
# don't have to guess what you are doing.

raw_text = """
twas brillig and the slithy toves
did gyre and gimble in the wabe
same mesa seam sameness samehood
"""

lexicon = sorted(set(raw_text.split()))
print "\nlexicon:", lexicon
#
# Assuming we want anagrams:
#
# Build an anagram dictionary
#
anagram_dict = defaultdict(set)
for word in lexicon:
    anagram_dict[anagram_key(word)].add(word)

print "\nanagram_dict (len == %d):" % len(anagram_dict)
pprint.pprint(anagram_dict)

# now purge trivial entries

temp = {}
for k, v in anagram_dict.iteritems():
    if len(v) != 1:
        temp[k] = v
anagram_dict = temp
print "\nanagram_dict (len == %d):" % len(anagram_dict)
pprint.pprint(anagram_dict)

# Test cases

tests = "sam same mesa sameness samehood xsame samex".split()
default_set = frozenset()
for test in tests:
    print
    results = extract_by_letters_1(test, lexicon)
    print test, [(result, check_anagrams(test, result)) for result in results]
    # In the following statement, you can use set([test]) as the default
    # if that produces a more useful or orthogonal result.
    results = anagram_dict.get(anagram_key(test), default_set)
    print test, [(result, check_anagrams(test, result)) for result in results]

Выход:

lexicon: ['and', 'brillig', 'did', 'gimble', 'gyre', 'in', 'mesa', 'same', 'samehood', 'sameness', 'seam', 'slithy', 'the', 'toves', 'twas', 'wabe']

anagram_dict (len == 14):
defaultdict(<type 'set'>, {'abew': set(['wabe']), 'eht': set(['the']), 'egry': set(['gyre']), 'begilm': set(['gimble']), 'hilsty': set(['slithy']), 'aems': set(['mesa', 'seam', 'same']), 'bgiillr': set(['brillig']), 'ddi': set(['did']), 'eostv': set(['toves']), 'adehmoos': set(['samehood']), 'in': set(['in']), 'adn': set(['and']), 'aeemnsss': set(['sameness']), 'astw': set(['twas'])})

anagram_dict (len == 1):
{'aems': set(['mesa', 'same', 'seam'])}

sam [('mesa', False), ('samehood', False), ('seam', False), ('same', False)]
sam []

same [('mesa', True), ('samehood', False), ('seam', True), ('same', True)]
same [('mesa', True), ('seam', True), ('same', True)]

mesa [('mesa', True), ('samehood', False), ('seam', True), ('same', True)]
mesa [('mesa', True), ('seam', True), ('same', True)]

sameness [('sameness', True)]
sameness []

samehood [('samehood', True)]
samehood []

xsame []
xsame []

samex []
samex []

Answer 5

Вы пытаетесь найти все анаграммы "букв"?

def anagrams(letters, words):
    letters = sorted(letters)
    result = []
    for word in words:
        if sorted(word.strip()) == letters:
            result.append(word)
    return result