Как я могу оптимизировать этот код Python для генерации всех слов с расстоянием в 1?
Профилирование показывает, что это самый медленный сегмент моего кода для небольшой словесной игры, которую я написал:
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
Заметки:
distance()вызывается более 5 миллионов раз, большинство из которых от getchildren, который должен получить все слова в списке слов, которые отличаются отwordровно на 1 букву.- список слов предварительно фильтруется, чтобы иметь только те слова, которые содержат столько же букв, сколько
wordтак что гарантировано, чтоword1а такжеword2имеют одинаковое количество символов. - Я довольно новичок в Python (начал изучать его 3 дня назад), поэтому комментарии к соглашениям об именах или другим стилевым вещам также приветствуются.
- для списка слов возьмите список слов 12dict, используя файл "2+2lemma.txt"
Результаты:
Спасибо всем, с комбинациями различных предложений, теперь я запустил программу в два раза быстрее (помимо оптимизаций, которые я сделал самостоятельно, прежде чем спрашивать, так что скорость в 4 раза увеличилась примерно по сравнению с моей первоначальной реализацией)
Я проверил с 2 наборами входов, которые я назову A и B
Оптимизация1: перебирать индексы слова1,2... из
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
перебирать пары букв, используя zip(word1, word2)
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
Получили время выполнения с 11,92 до 9,18 для входа A и с 79,30 до 74,59 для входа B
Оптимизация2: Добавлен отдельный метод для разности на единицу в дополнение к методу расстояния (который мне все еще был нужен в других местах для эвристики A*)
def is_neighbors(word1,word2):
different = False
for c1,c2 in zip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
Получил время выполнения от 9,18 до 8,83 для входа A и от 74,59 до 70,14 для входа B
Оптимизация3: большой победитель здесь должен был использовать izip вместо zip
Получил время выполнения от 8,83 до 5,02 для входа A и от 70,14 до 41,69 для входа B
Я мог бы лучше написать это на языке более низкого уровня, но сейчас я доволен этим. Спасибо всем!
Снова отредактируйте: больше результатов Используя метод Марка, проверяющий случай, когда первая буква не совпадает, мы получили 5,02 -> 3,59 и 41,69 -> 29,82.
Опираясь на это и включив izip вместо range Я закончил с этим:
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
Который сжал немного больше, сократив время с 3,59 -> 3,38 и 29,82 -> 27,88
Еще больше результатов!
Пытаясь предложить Сумуду, чтобы я сгенерировал список всех строк, которые на 1 букву удалены от слова, а затем проверил, какие из них были в списке слов, вместо функции is_neighbor, я закончил с этим:
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return ( w for w in oneoff if w in wordlist )
Что оказалось медленнее (3,38 -> 3,74 и 27,88 -> 34,40), но казалось многообещающим. Сначала я подумал, что часть, которую мне нужно оптимизировать, была "one_letter_off_strings", но профилирование показало обратное и медленная часть была на самом деле
( w for w in oneoff if w in wordlist )
Я подумал, будет ли какая-то разница, если я переключу "oneoff" и "wordlist" и сделал сравнение другим способом, когда меня поразило, что я искал пересечение двух списков. Я заменяю это на set-intersection на буквы:
return set(oneoff) & set(wordlist)
Бам! 3,74 -> 0,23 и 34,40 -> 2,25
Это действительно удивительно, общая разница в скорости по сравнению с моей первоначальной простой реализацией: 23,79 -> 0,23 и 180,07 -> 2,25, что примерно в 80-100 раз быстрее, чем в исходной реализации.
Если кому-то интересно, я сделал сообщение в блоге, описывающее программу и описывающее сделанные оптимизации, в том числе и ту, которая здесь не упоминается (потому что она находится в другом разделе кода).
Великие дебаты:
Хорошо, я и Неизвестный ведем большую дискуссию, которую вы можете прочитать в комментариях к его ответу. Он утверждает, что было бы быстрее использовать оригинальный метод (используя is_neighbor вместо использования наборов), если бы он был портирован на C. Я пытался в течение 2 часов получить модуль C, который я написал, для сборки и связывания без особого успеха после попытки следуйте этому и этому примеру, и похоже, что процесс немного отличается в Windows? Я не знаю, но я отказался от этого. В любом случае, вот полный код программы, и текстовый файл взят из списка слов 12dict с использованием файла "2+2lemma.txt". Извините, если код немного грязный, я просто взломал это вместе. Также я забыл вычеркнуть запятые из списка слов, так что на самом деле это ошибка, которую вы можете оставить для того же сравнения или исправить ее, добавив запятую в список символов в cleanentries.
from itertools import izip
def unique(seq):
seen = {}
result = []
for item in seq:
if item in seen:
continue
seen[item] = 1
result.append(item)
return result
def cleanentries(li):
pass
return unique( [w.strip('[]') for w in li if w != "->"] )
def distance(word1, word2):
difference = 0
for x,y in izip (word1, word2):
if x != y:
difference += 1
return difference
def is_neighbors(word1,word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for x,y in izip(word1[1:],word2[1:]):
if x != y:
if different:
return False
different = True
return different
def one_letter_off_strings(word):
import string
dif_list = []
for i in xrange(len(word)):
dif_list.extend((word[:i] + l + word[i+1:] for l in string.ascii_lowercase if l != word[i]))
return dif_list
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
def AStar(start, goal, wordlist):
import Queue
closedset = []
openset = [start]
pqueue = Queue.PriorityQueue(0)
g_score = {start:0} #Distance from start along optimal path.
h_score = {start:distance(start, goal)}
f_score = {start:h_score[start]}
pqueue.put((f_score[start], start))
parent_dict = {}
while len(openset) > 0:
x = pqueue.get(False)[1]
if x == goal:
return reconstruct_path(parent_dict,goal)
openset.remove(x)
closedset.append(x)
sortedOpen = [(f_score[w], w, g_score[w], h_score[w]) for w in openset]
sortedOpen.sort()
for y in getchildren(x, wordlist):
if y in closedset:
continue
temp_g_score = g_score[x] + 1
temp_is_better = False
appended = False
if (not y in openset):
openset.append(y)
appended = True
h_score[y] = distance(y, goal)
temp_is_better = True
elif temp_g_score < g_score[y] :
temp_is_better = True
else :
pass
if temp_is_better:
parent_dict[y] = x
g_score[y] = temp_g_score
f_score[y] = g_score[y] + h_score[y]
if appended :
pqueue.put((f_score[y], y))
return None
def reconstruct_path(parent_dict,node):
if node in parent_dict.keys():
p = reconstruct_path(parent_dict,parent_dict[node])
p.append(node)
return p
else:
return []
wordfile = open("2+2lemma.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
userentry = raw_input("Hello, enter the 2 words to play with separated by a space:\n ")
words = [w.lower() for w in userentry.split()]
if(len(words) == 2 and len(words[0]) == len(words[1])):
break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
print "Minimum number of steps is %s" % (len(answer))
reply = raw_input("Would you like the answer(y/n)? ")
if(reply.lower() == "y"):
answer.insert(0, words[0])
print "\n".join(answer)
else:
print "Good luck!"
else:
print "Sorry, there's no answer to yours"
reply = raw_input("Press enter to exit")
Я оставил метод is_neighbors, хотя он не используется. Это метод, который предлагается перенести на C. Чтобы использовать его, просто замените getchildren на:
def getchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w))
Что касается того, чтобы заставить его работать как модуль C, я не зашел так далеко, но вот что я придумал:
#include "Python.h"
static PyObject *
py_is_neighbor(PyObject *self, Pyobject *args)
{
int length;
const char *word1, *word2;
if (!PyArg_ParseTuple(args, "ss", &word1, &word2, &length))
return NULL;
int i;
int different = 0;
for (i =0; i < length; i++)
{
if (*(word1 + i) != *(word2 + i))
{
if (different)
{
return Py_BuildValue("i", different);
}
different = 1;
}
}
return Py_BuildValue("i", different);
}
PyMethodDef methods[] = {
{"isneighbor", py_is_neighbor, METH_VARARGS, "Returns whether words are neighbors"},
{NULL, NULL, 0, NULL}
};
PyMODINIT_FUNC
initIsNeighbor(void)
{
Py_InitModule("isneighbor", methods);
}
Я профилировал это, используя:
python -m cProfile "Wordgame.py"
И записанное время было общим временем вызова метода AStar. Быстрый набор ввода был "стихотворный стих", а длинный набор ввода - "стихотворный стих". Очевидно, что время будет различаться для разных машин, поэтому, если кто-нибудь попытается это сделать, приведите сравнение результатов как есть, так и с модулем C.
12 ответов
Если ваш список слов очень длинный, возможно, было бы эффективнее сгенерировать все возможные однобуквенные отличия от "слова", а затем проверьте, какие из них есть в списке? Я не знаю Python, но должна быть подходящая структура данных для списка слов, позволяющая осуществлять поиск во время журнала.
Я предлагаю это, потому что если ваши слова имеют разумную длину (~10 букв), то вы будете искать только 250 потенциальных слов, что, вероятно, быстрее, если ваш список слов превышает несколько сотен слов.
Ваша функция distance вычисляет общее расстояние, когда вы действительно заботитесь только о расстоянии =1. В большинстве случаев вы будете знать, что>1 в пределах нескольких символов, поэтому вы можете вернуться рано и сэкономить много времени.
Помимо этого, может быть лучший алгоритм, но я не могу думать об этом.
Изменить: еще одна идея.
Вы можете сделать 2 случая, в зависимости от того, соответствует ли первый символ. Если оно не совпадает, остальное слово должно точно соответствовать, и вы можете проверить это за один выстрел. В противном случае, сделайте это аналогично тому, что вы делали. Вы могли бы даже сделать это рекурсивно, но я не думаю, что это будет быстрее.
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
same = True
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if same:
same = False
else:
return False
return not same
Изменить 2: я удалил проверку, чтобы увидеть, если строки одинаковой длины, так как вы говорите, что это избыточно. Запустив тесты Райана для моего собственного кода и для функции is_neighbors, предоставляемой MizardX, я получаю следующее:
- Исходное расстояние (): 3,7 секунды
- My DifferentByOne(): 1,1 секунды
- Is_neighbors () MizardX (): 3,7 секунды
Редактировать 3: (Возможно, попасть на территорию сообщества вики здесь, но...)
Попытка окончательного определения is_neighbors() с использованием izip вместо zip: 2,9 секунды.
Вот моя последняя версия, которая все еще раз в 1,1 секунды:
def DifferentByOne(word1, word2):
if word1[0] != word2[0]:
return word1[1:] == word2[1:]
different = False
for i in range(1, len(word1)):
if word1[i] != word2[i]:
if different:
return False
different = True
return different
from itertools import izip
def is_neighbors(word1,word2):
different = False
for c1,c2 in izip(word1,word2):
if c1 != c2:
if different:
return False
different = True
return different
Или, может быть, в izip код:
def is_neighbors(word1,word2):
different = False
next1 = iter(word1).next
next2 = iter(word2).next
try:
while 1:
if next1() != next2():
if different:
return False
different = True
except StopIteration:
pass
return different
И переписанный getchildren:
def iterchildren(word, wordlist):
return ( w for w in wordlist if is_neighbors(word, w) )
izip(a,b)возвращает итератор для пар значений изaа такжеb,zip(a,b)возвращает список пар изaа такжеb,
Люди в основном делают это, пытаясь написать более быструю функцию, но может быть и другой путь.
"расстояние" называется более 5 миллионов раз
Почему это? Возможно, лучший способ оптимизировать это попытаться уменьшить количество звонков distanceвместо того, чтобы брить миллисекунды distance's время исполнения. Невозможно сказать, не увидев полный сценарий, но оптимизация конкретной функции, как правило, не требуется.
Если это невозможно, возможно, вы могли бы написать это как модуль C?
Как часто вызывается функция расстояния с одинаковыми аргументами? Простым для реализации оптимизации было бы использовать памятку.
Вы могли бы также создать какой-то словарь с заморозками букв и списками слов, которые отличаются на единицу, и искать значения в этом. Эта структура данных может быть либо сохранена и загружена через рассол, либо сгенерирована с нуля при запуске.
Короткое замыкание оценки даст вам выигрыш только в том случае, если используемые вами слова очень длинные, поскольку используемый вами алгоритм расстояния Хэмминга в основном равен O(n), где n - длина слова.
Я провел несколько экспериментов со временем для некоторых альтернативных подходов, которые могут быть иллюстративными.
Timeit Результаты
Ваше решение
d = """\
def distance(word1, word2):
difference = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
difference += 1
return difference
"""
t1 = timeit.Timer('distance("hello", "belko")', d)
print t1.timeit() # prints 6.502113536776391
Один лайнер
d = """\
from itertools import izip
def hamdist(s1, s2):
return sum(ch1 != ch2 for ch1, ch2 in izip(s1,s2))
"""
t2 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 10.985101179
Ярлык Оценка
d = """\
def distance_is_one(word1, word2):
diff = 0
for i in xrange(len(word1)):
if word1[i] != word2[i]:
diff += 1
if diff > 1:
return False
return diff == 1
"""
t3 = timeit.Timer('hamdist("hello", "belko")', d)
print t2.timeit() # prints 6.63337
Well you can start by having your loop break if the difference is 2 or more.
Также вы можете изменить
for i in range(len(word1)):
в
for i in xrange(len(word1)):
Because xrange generates sequences on demand instead of generating the whole range of numbers at once.
You can also try comparing word lengths which would be quicker. Also note that your code doesn't work if word1 is greater than word2
There's not much else you can do algorithmically after that, which is to say you'll probably find more of a speedup by porting that section to C.
Редактировать 2
Attempting to explain my analysis of Sumudu's algorithm compared to verifying differences char by char.
When you have a word of length L, the number of "differs-by-one" words you will generate will be 25L. We know from implementations of sets on modern computers, that the search speed is approximately log(n) base 2, where n is the number of elements to search for.
Seeing that most of the 5 million words you test against is not in the set, most of the time, you will be traversing the entire set, which means that it really becomes log(25L) instead of only log(25L)/2. (and this is assuming best case scenario for sets that comparing string by string is equivalent to comparing char by char)
Now we take a look at the time complexity for determining a "differs-by-one". If we assume that you have to check the entire word, then the number of operations per word becomes L. We know that most words differ by 2 very quickly. And knowing that most prefixes take up a small portion of the word, we can logically assume that you will break most of the time by L/2, or half the word (and this is a conservative estimate).
Итак, теперь мы строим временные сложности двух поисков, L/2 и log(25L), и помня, что это даже рассматривает строку, совпадающую с той же скоростью, что и последовательность символов (в пользу множеств). У вас есть лог уравнения (25*L) > L/2, который можно упростить до log(25) > L/2 - log(L). Как видно из графика, следует использовать алгоритм сопоставления символов быстрее, пока не достигнете очень большого числа L.
Кроме того, я не знаю, рассчитываете ли вы разницу в 2 или более раз в своей оптимизации, но из ответа Марка я уже разбил разницу в 2 или более, и на самом деле, если разница в первой букве, это разрывы после первой буквы, и даже несмотря на все эти оптимизации, переход на использование наборов просто унес их из воды. Мне интересно попробовать вашу идею, хотя
Я был первым человеком в этом вопросе, который предложил разбить разницу в 2 или более. Дело в том, что идея Марка обрезки строк (если word1[0]!= Word2[0]: return word1[1:] == word2[1:]) просто помещает то, что мы делаем, в C. Как вы думаете слово1 [1:] == слово2 [1:] рассчитывается? Так же, как и мы.
Я прочитал ваше объяснение несколько раз, но я не совсем понял его, не могли бы вы объяснить его немного глубже? Кроме того, я не очень хорошо знаком с C, и я работал на языках высокого уровня в течение последних нескольких лет (самый близкий изучал C++ в средней школе 6 лет назад
Что касается создания кода на C, я немного занят. Я уверен, что вы сможете сделать это, так как вы уже писали на C раньше. Вы также можете попробовать C#, который, вероятно, имеет аналогичные характеристики производительности.
Больше объяснений
Вот более глубокое объяснение Davy8
def getchildren(word, wordlist):
oneoff = one_letter_off_strings(word)
return set(oneoff) & set(wordlist)
Ваша функция one_letter_off_strings создаст набор из 25L строк (где L - количество букв).
Создание набора из списка слов создаст набор из D строк (где D - длина вашего словаря). Создавая пересечение из этого, вы ДОЛЖНЫ перебирать каждый из них и посмотреть, существует ли он в списке слов.
Сложность времени для этой операции подробно описана выше. Эта операция менее эффективна, чем сравнение нужного слова с каждым словом в списке слов. Метод Сумуду - это оптимизация в С, а не в алгоритме.
Больше объяснения 2
Всего 4500 слов (потому что список слов предварительно фильтруется по 5 буквенным буквам еще до того, как их передают в алгоритм), пересекаясь со 125 однобуквенными словами. Казалось, вы говорили, что пересечение - это log (меньше) или в других словах log(125, 2). Сравните это с тем, чтобы снова предположить, что вы сказали, что, сравнивая разрывы слов в L / 2 буквах, я округлю это до 2, даже если для 5-буквенного слова это, скорее всего, равно 3. Это сравнение выполняется 4500 раз, поэтому 9000. log(125,2) составляет около 6,9, а log(4500,2) - около 12. Позвольте мне знать, если я неверно истолковал ваши цифры.
Чтобы создать пересечение 125 однобуквенных слов со словарем в 4500, нужно сделать 125 * 4500 сравнений. Это не лог (125,2). В лучшем случае это 125 * log(4500, 2) при условии, что словарь предварительно отсортирован. Там нет волшебного ярлыка для наборов. Вы также делаете здесь строку за строкой вместо сравнения символов с помощью символов.
Для такой простой функции, которая имеет такое большое влияние на производительность, я бы, вероятно, сделал бы библиотеку C и вызывал бы ее, используя ctypes. Один из основателей Reddit утверждает, что они сделали сайт в 2 раза быстрее, используя эту технику.
Вы также можете использовать psyco для этой функции, но помните, что она может съесть много памяти.
Я не знаю, сильно ли это повлияет на вашу скорость, но вы могли бы начать с превращения понимания списка в выражение генератора. Это все еще итерация, поэтому не должно сильно отличаться в использовании:
def getchildren(word, wordlist):
return [ w for w in wordlist if distance(word, w) == 1 ]
в
def getchildren(word, wordlist):
return ( w for w in wordlist if distance(word, w) == 1 )
Основная проблема заключается в том, что понимание списка будет создаваться в памяти и занимать довольно много места, в то время как генератор создаст ваш список на лету, поэтому нет необходимости хранить все это.
Также, следуя неизвестному ответу, это может быть более "питонический" способ написания расстояния ():
def distance(word1, word2):
difference = 0
for x,y in zip (word1, word2):
if x == y:
difference += 1
return difference
Но это сбивает с толку то, что предназначено, когда len (word1)!= Len (word2), в случае zip он вернет только столько символов, сколько самого короткого слова. (Что может оказаться оптимизацией...)
Попробуй это:
def distance(word1, word2):
return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])
Кроме того, у вас есть ссылка на вашу игру? Мне нравится быть уничтоженным играми в слова
Для этого фрагмента:
for x,y in zip (word1, word2):
if x != y:
difference += 1
return difference
я бы использовал это:
return sum(1 for i in xrange(len(word1)) if word1[i] == word2[i])
тот же шаблон будет следовать всему предоставленному коду...
Первое, что пришло мне в голову:
from operator import ne
def distance(word1, word2):
return sum(map(ne, word1, word2))
который имеет приличный шанс продвинуться быстрее, чем другие публикуемые функции, потому что у него нет интерпретируемых циклов, только вызовы примитивов Python. И он достаточно короткий, чтобы вы могли разумно вставить его в вызывающую сторону.
Что касается вашей проблемы более высокого уровня, я бы посмотрел на структуры данных, разработанные для поиска сходства в метрических пространствах, например, в этой статье или в этой книге, которые я не читал (они пришли в поисках статьи, которую я прочитал) но не могу вспомнить).
Все остальные сосредоточились только на явном расчете расстояния, не делая ничего о построении кандидатов на расстояние 1. Вы можете улучшить с помощью хорошо известной структуры данных, называемой Trie, для объединения неявного вычисления расстояния с задачей генерации всех соседних слов расстояния 1. Trie - это связанный список, где каждый узел обозначает букву, а поле "next" - это поле, содержащее до 26 записей, указывающих на следующий узел.
Вот псевдокод: ирите трие для вашего данного слова; в каждом узле добавьте всех соседей по расстояниям 0 и 1 к результатам; сохранить счетчик расстояния и уменьшить его. Вам не нужна рекурсия, просто функция поиска, которая принимает дополнительный целочисленный аргумент distance_so_far.
Незначительный компромисс дополнительной скорости для увеличения пространства O(N) может быть получен путем создания отдельных попыток для слов длины 3, длины 4, длины 5 и т. Д.