プロファイリングは、これが私が書いた小さな単語ゲームのコードの最も遅いセグメントであることを示しています:
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()は 500 万回以上呼び出されており、その大部分は getchildren からのもので、単語リスト内のword1 文字だけ異なるすべての単語を取得することになっています。- wordlist は、同じ数の文字を含む単語のみを持つように事前にフィルター処理されているため、同じ数の文字を持つ
wordことが保証されます。word1word2 - 私は Python を初めて使用するので (3 日前に学習を開始しました)、命名規則やその他のスタイルに関するコメントも歓迎します。
- wordlistの場合、「2+2lemma.txt」ファイルを使用して12dict の単語リストを取得します
結果：
みんなありがとう、さまざまな提案を組み合わせて、プログラムを2倍の速度で実行できるようになりました（質問する前に自分で行った最適化に加えて、最初の実装から約4倍の速度が向上しました）
AとBと呼ぶ2セットの入力でテストしました
Optimization1: word1,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
入力 A の実行時間は 11.92 から 9.18、入力 B の実行時間は 79.30 から 74.59 になりました
Optimization2: distance-method に加えて、different-by-one の別のメソッドを追加しました (これは、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
入力 A の実行時間は 9.18 から 8.83、入力 B の実行時間は 74.59 から 70.14 になりました
最適化 3: ここでの大きな勝者は、izip代わりに使用することでしたzip
入力 A の実行時間は 8.83 から 5.02 になり、入力 B の実行時間は 70.14 から 41.69 になりました
低レベル言語で書いたほうがいいかもしれませんが、今のところこれで満足しています。みんな、ありがとう！
もう一度編集: より多くの結果最初の文字が一致しないケースをチェックするマークの方法を使用して、5.02 -> 3.59 および 41.69 -> 29.82 からダウンしました。
それに基づいての代わりに組み込むiziprangeと、次のようになりました。
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 関数の代わりに wordlist にあるものを確認するというSumuduの提案を試してみると、次のようになりました。
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)
バム！3.74 -> 0.23 および 34.40 -> 2.25
これは本当に驚くべきことであり、元の素朴な実装との合計速度の差: 23.79 -> 0.23 および 180.07 -> 2.25 であり、元の実装よりも約 80 倍から 100 倍高速です。
誰かが興味を持っている場合は、プログラムを説明し、ここで言及されていないものを含めて行われた最適化について説明するブログ投稿を作成しました (コードの別のセクションにあるため)。
大論争：
わかりました、私と Unknown は大きな議論をしています。彼の回答のコメントで読むことができます。彼は、C に移植した場合、元の方法 (セットを使用する代わりに is_neighbor を使用) を使用した方が高速になると主張しています。thisとthisの例に従ってください。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 モジュールの結果を比較してください。
