我正在制作一个拼字生成器,由于我缺乏编码技巧,效率极低。在这个程序中,用户输入一系列字母,程序使用蛮力查找每个有效的拼字。为了加快这个过程,我想实现多处理,但无法使其成功工作。工作的非多重处理代码如下所示
from multiprocessing import Process
usrList = input("type the letters you have ")
usrList = list(usrList.upper())
usrList.sort()
print(usrList)
storedList = []
def word2 (usrList):
print('trying to find two letter words')
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
if i != j:
if str(usrList[i])+str(usrList[j]) not in storedList and str(usrList[i])+str(usrList[j])+'\n' in dicList:
print(str(usrList[i])+str(usrList[j]))
storedList.append(str(usrList[i])+str(usrList[j]))
def word3(usrList):
print('trying to find three leter words')
if len(usrList) > 2:
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
for k in range(0,len(usrList)):
if i != j and i != k and j != k:
if str(usrList[i])+str(usrList[j])+str(usrList[k]) not in storedList and str(usrList[i])+str(usrList[j])+str(usrList[k])+'\n' in dicList :
print(str(usrList[i])+str(usrList[j])+str(usrList[k]))
storedList.append(str(usrList[i])+str(usrList[j])+str(usrList[k]))
def word4(usrList):
print('trying to find four letter words')
if len(usrList) > 3:
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
for k in range(0,len(usrList)):
for l in range(0,len(usrList)):
if i !=j and i != k and i!= l and j!= k and j!= l and k != l:
if str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l]) not in storedList and str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+'\n' in dicList:
print(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l]))
storedList.append(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l]))
def word5(usrList):
print('trying to find five letter words')
if len(usrList) > 4:
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
for k in range(0,len(usrList)):
for l in range(0,len(usrList)):
for m in range(0,len(usrList)):
if i !=j and i != k and i!= l and i != m and j!= k and j!= l and j!= m and k != l and k != m and l !=m:
if str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m]) not in storedList and str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+'\n' in dicList:
print(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m]))
storedList.append(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m]))
def word6(usrList):
print('trying to find six letter words')
if len(usrList) > 5:
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
for k in range(0,len(usrList)):
for l in range(0,len(usrList)):
for m in range(0,len(usrList)):
for n in range(0,len(usrList)):
if i !=j and i != k and i!= l and i != m and i != n and j!= k and j!= l and j!= m and j !=n and k != l and k != m and k != n and l !=m and l != n and m!= n:
if str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n]) not in storedList and str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n])+'\n' in dicList:
print(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n]))
storedList.append(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n]))
def word7(usrList):
print('trying to find seven letter words')
if len(usrList) > 6:
for i in range(0,len(usrList)):
for j in range(0,len(usrList)):
for k in range(0,len(usrList)):
for l in range(0,len(usrList)):
for m in range(0,len(usrList)):
for n in range(0,len(usrList)):
for o in range(0,len(usrList)):
if i !=j and i != k and i!= l and i != m and i != n and i != 0 and j!= k and j!= l and j!= m and j !=n and j != o and k != l and k != m and k != n and k!= o and l !=m and l != n and l != 0 and m!= n and m != o and n != o:
if str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n])+str(usrList[o]) not in storedList and str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n])+str(usrList[o])+'\n' in dicList :
print(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n])+str(usrList[o]))
storedList.append(str(usrList[i])+str(usrList[j])+str(usrList[k])+str(usrList[l])+str(usrList[m])+str(usrList[n])+str(usrList[o]))
f = 'ScrabbleDic.txt'
with open(f,'r') as file:
dicList=[]
for line in file:
dicList.append(line)
file.close()
if __name__ == '__main__':
word7(usrList)
word6(usrList)
word5(usrList)
word4(usrList)
word3(usrList)
word2(usrList)
一般来说,重新设计算法通常比使用多处理更有价值
下面是代码的一个简短实现。我已经对usrList进行了硬编码,由于我无法访问您正在使用的字典文件,因此我使用MacOS附带的默认字典文件。我没有编写嵌套循环和检查重复索引,而是使用itertools模块生成给定长度的usrList的所有排列。这不会有意义地加快代码的速度,但会使演示可能的更改变得更容易:
在我的Macbook上运行大约需要47.4秒。为了加快速度,让我们按照您的建议添加多处理。有几种方法可以使用多处理,但最容易实现的可能是创建一个池并调用其
map()
函数如果您不习惯使用将其他函数作为参数的函数,那么这种语法可能看起来有点奇怪。实际上,我们正在创建一个工作人员池,然后为该池提供一个函数和一系列用于该函数的参数。然后,各个函数调用在池中拆分,而不是按顺序调用:
这在我的Macbook上运行时间为32.3秒。我们缩短了四分之一的时间!也许有一些方法可以从这种方法中挤出更多的性能,但也值得研究一下算法,看看是否有其他方法可以加快速度
现在,您正在创建字典单词列表。当您检查列表中是否有潜在单词时,Python必须扫描整个列表,直到找到匹配项或到达末尾。我的内置字典有235K个单词,这意味着它必须对它生成的每个无意义字母组合进行235K字符串比较
如果从使用列表切换到使用集合,Python可以通过使用哈希函数在几乎恒定的时间内查找值,而不是一次扫描一个条目。让我们尝试一下,而不是多处理:
仅更改两个字符后,此版本将在0.005秒内运行
总之,多处理是一个有用的工具,但它可能不应该是您尝试的第一件事。通过仔细考虑您正在使用的数据结构和算法以及瓶颈可能在哪里,您通常会得到更好的结果
解决此类难题的经典解决方案不是检查所有可能的排列,而是将字典中的示例字母和单词转换为一致的可搜索排列-通过对其字符进行排序
现在,您不必在字典中搜索“python”的每个排列,只需对字母进行排序以创建键“HNOPSTY”,就可以在地图中找到具有相同键的所有有效单词
使用defaultdict,很容易创建字典中所有单词的查找映射。我们使用
defaultdict(list)
而不是dict,因为多个单词可能排序到同一个键相关问题 更多 >
编程相关推荐