Как я могу оптимизировать этот код Python для генерации всех слов с расстоянием в 1? - PullRequest
Новая
       70

Как я могу оптимизировать этот код Python для генерации всех слов с расстоянием в 1?

31 голосов
/ 25 апреля 2009

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

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.

Ответы [ 12 ]

0 голосов
/ 25 апреля 2009

Попробуйте это: 

def distance(word1, word2):
  return sum([not c1 == c2 for c1, c2 in zip(word1,word2)])

Кроме того, у вас есть ссылка на вашу игру? Мне нравится быть уничтоженным играми в слова

0 голосов
/ 25 апреля 2009

Я не знаю, сильно ли это повлияет на вашу скорость, но вы могли бы начать с превращения понимания списка в выражение генератора. Он по-прежнему повторяем, поэтому не должен сильно отличаться в использовании: 

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 он вернет только столько символов, сколько самого короткого слова. (Что может оказаться оптимизацией ...)

Страница:
...