Профилирование показывает, что это самый медленный сегмент моего кода для небольшой словесной игры, которую я написал:
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
Optimization2:
Добавлен отдельный метод для различий по-одному в дополнение к методу расстояния (который мне все еще нужен в других местах для эвристики 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
Optimization3:
Большой победитель здесь должен был использовать 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» и сделал сравнение другим способом, когда меня поразило, что я искал пересечение 2 списков. Я заменяю это на set-intersection на буквы :
return set(oneoff) & set(wordlist)
Bam! 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.