сравнение Integer в питона замедляет все ползти

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 секунд, чтобы пройти через словарь.

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

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

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

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

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

Заранее благодарен!

Answer 1

Try строить выход вместо того, чтобы удалить из него:

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 2

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

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

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

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 это должно дать огромное SpeedUp

Answer 3

Вот функция, которая должна предложить большую скорость вверх:

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. Вместо того, чтобы удалять слова из словаря, я добавляю их в массив, который возвращается из функции. Если у вас огромный словарь, скорее всего, будет всего несколько слов. Кроме того, если переменная словаря является массивом (который, как я подозреваю), то каждый раз, когда вы вызывали удаление, он должен был сначала искать слово в словаре (линейно начинать с самого начала), а затем удалять его. Его быстрее удалять, выбирая с помощью индекса слова, которое нужно удалить.

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

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

Answer 4

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

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

Answer 5

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 []