问题描述
我有一个包含81个顶点（每个顶点顶点类的实例），一个漂亮的图表（列表）。每个顶点有20个邻居。每个顶点具有多个可能值（从1到9）其中，由于一些初始约束的问题将在平均4或5。我实现了一个简单的DFS在这个曲线图中，该开出节点具有较少可能的值，的foreach价值构建具有唯一可能的值中的一个又一个deepcopied图形，最后又传递到DFS的deepcopied图递归。这个问题是关于速度; cProfiling我的code我发现的641秒我的Mac需要解决这个问题的635所使用的copy.deepcopy。有没有解决方法这个问题？这是我的DFS：
高清DFS（图）：
全球initial_time_counter
如果所有（LEN（i.possible_values）== 1我图）：
sys.exit（完成于：％的％（time.time（） - initial_time_counter））
#find出非解决顶点具有最小可能的值
min_vertex =排序（滤波器（拉姆达X：LEN（x.possible_values）大于1，曲线图），
键=拉姆达X：LEN（x.possible_values））[0]
在min_vertex.possible_values值：
sorted_graph_copy =排序（copy.deepcopy（图），键=拉姆达X：LEN（x.possible_values））
min_vertex_copy =滤波器（拉姆达X：LEN（x.possible_values）大于1，sorted_graph_copy）[0]
sorted_graph_copy.remove（min_vertex_copy）
如果min_vertex_copy.try_value（值）：#Can这个顶点接受的价值 - ＆GT;值？
min_vertex_copy.set_value（值）#Yes，设置它。
sorted_graph_copy.append（min_vertex_copy）#Append它的曲线图。
DFS（sorted_graph_copy）#Run的DFS了。
返回False
P.S。作为最聪明的你可能已经意识到这个问题通常被称为数独。请注意，我不是在寻找特定的数独的答案，分析问题的一种抽象的方式。
同样的问题，走近纯弦重新顶点presentations，拿了＆LT; 0.75秒来解决。我张贴了整个code，以供参考，如果有人经历，今后类似的问题：
进口SYS，时间
高清srange（）：
返回[x的范围（9），用于的y范围[X，Y]（9）]
DEF重新present_sudoku（数独）：
打印\ N。加入（[|。加入（[STR（ELEM）为ELEM本着]）在数独行]）
#Hard数独
独= [[4，0，0，0，0，0，8,0，5〕，〔0,3，0，0，0，0，0，0，0]，[0，0，0， 7，0，0，0，0，0]，[0，2，0，0，0，0，0，6，0]，[0，0，0，0，8,0，4,0， 0]，[0，0，0，0，1，0，0，0，0]，[0，0，0，6，0,3，0，7，0]，[5，0,0， 2，0，0，0，0，0]，[1，0,4，0，0，0，0，0，0]]
再present_sudoku（数独）
高清get_nbs（X，Y，数独，also_incomplete = FALSE）：
line_nbs =总和（[ELEM为的elem在数独[y]的，如果（（ELEM！= [0]和len（ELEM）== 1）或also_incomplete）]，[]）
column_nbs =总和（[独[构造线] [X]为构造线中的范围（9）如（（独[构造线] [X]！= [0]和len（独[构造线] [X]）== 1）或also_incomplete）]，[]）
area_nbs = [[J的j I [（X / 3）* 3：（X / 3）* 3 + 3]如果（！（J = [0]和len（j）条== 1）或also_incomplete）]因为我的数独[（Y / 3）* 3：（Y / 3）* 3 + 3]
area_nbs = SUM（SUM（area_nbs，[]），[]）
如果不是also_incomplete：
返回列表（集（line_nbs + column_nbs + area_nbs））
返回line_nbs + column_nbs + area_nbs
的x，y在srange（）：
数独[Y] [X] = [数独[Y] [X]
高清base_cleanup（数独）：
而1：
something_changed =假
的x，y在srange（）：
如果数独[Y] [X] == [0]或len个（数独[Y] [X]）→1：
possible_values =范围（1,10），如果数独[Y] [X] == [0]其他的数独[Y] [X]
数独[Y] [X] =列表（集（possible_values）-set（get_nbs（X，Y，数独）））
如果数独[Y] [X] == []：
返回False
something_changed = true如果possible_values！=数独[Y] [X]否则返回False
其他：
数独[Y] [X] =数独[Y] [X]
如果不是something_changed：
打破
回数独
高清DFS（图表）：
全球小号
如果图==错误：
返回False
如果所有（SUM（[LEN（ELEM）== 1 ELEM本着]在图线]，[]））：
再present_sudoku（图）
sys.exit（完成于：％的％（time.time（） - S））
enumerated_filtered_sudoku =滤波器（拉姆达X：LEN（X [1]）大于1，枚举（总和（图中，[]）））
sorted_enumerated_sudoku =排序（enumerated_filtered_sudoku，键=拉姆达X：LEN（X [1]））
min_vertex = sorted_enumerated_sudoku [0]
possible_values = [值在min_vertex值[1]
在possible_values值：
graph_copy = [[ELEM为ELEM本着]在图线]
Y，X = elements_position [min_vertex [0]]
如果没有任何（价值==我为我的get_nbs（X，Y，graph_copy））：
graph_copy [Y] [X] = [值]
如果base_cleanup（graph_copy）=假！
graph_copy = base_cleanup（graph_copy）
如果graph_copy：
DFS（graph_copy）
返回False
数独= base_cleanup（数独）
elements_position = {我：srange（）[我]为我的range（81）}
S = time.time（）
DFS（数独）
解决方案
的DeepCopy可以的很多的慢不是简单的复制，因为所有的努力同样的数据量，presumably的去到检测环路。如果要复制你的图表自己，避免循环（容易，因为你知道网络的拓扑结构），而不是委托给的DeepCopy的方式，很可能给你一个严肃的加速。我得到了50％的加速比复制一个非常简单的数据结构元素智能（使用COM prehensions），并且它不会让我感到吃惊，如果复杂的给了更大的节约。
当然，还有一个更大的加速可以得到的，如果你能避免使整个国家的完整副本在每一步。例如，因为你第一次搜索的深度，你可以切换你的方法来维持撤消堆栈：只是记录你选择的每个选项列表，你原路返回还原它们
。I have a nice graph (a list) containing 81 vertices (each vertex is an instance of a Vertex class). Each vertex has 20 neighbors. Each vertex has a number of possible values (ranging from 1 to 9) which, given some initial constraints to the problem will be on average 4 or 5. I implemented a simple DFS on this graph, that takes the node with less possible values, foreach value builds another "deepcopied" graph having only one of the possible value, and finally passes the "deepcopied" graph again into the DFS recursively. The issue is about speed; cProfiling my code I found out that 635 of the 641 second that my Mac takes to solve this problem are used by copy.deepcopy. Are there any workarounds for this issue? Here is my DFS:
def dfs(graph):
global initial_time_counter
if all(len(i.possible_values)==1 for i in graph):
sys.exit("Done in: %s" % (time.time()-initial_time_counter))
#find out the non-solved vertex with minimum possible values
min_vertex=sorted(filter(lambda x: len(x.possible_values)>1,graph),
key=lambda x: len(x.possible_values))[0]
for value in min_vertex.possible_values:
sorted_graph_copy=sorted(copy.deepcopy(graph), key=lambda x: len(x.possible_values))
min_vertex_copy=filter(lambda x: len(x.possible_values)>1,sorted_graph_copy)[0]
sorted_graph_copy.remove(min_vertex_copy)
if min_vertex_copy.try_value(value): #Can this vertex accept value -> value?
min_vertex_copy.set_value(value) #Yes, set it.
sorted_graph_copy.append(min_vertex_copy) #Append it to the graph.
dfs(sorted_graph_copy) #Run the DFS again.
return False
P.S. as the smartest of you might have understood this problem is usually called sudoku. Please note that I'm not looking for answers specific to sudoku, analyze the problem in an abstract way.
[Edit]
The same problem, approached with pure string representations of vertices, took < 0.75 sec to be solved. I'm posting the whole code for reference if anyone experiences a similar problem in the future:
import sys,time
def srange():
return [[x,y] for x in range(9) for y in range(9)]
def represent_sudoku(sudoku):
print "\n".join(["|".join([str(elem) for elem in line]) for line in sudoku])
#Hard sudoku
sudoku=[[4, 0, 0, 0, 0, 0, 8, 0, 5], [0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0], [0, 2, 0, 0, 0, 0, 0, 6, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 7, 0], [5, 0, 0, 2, 0, 0, 0, 0, 0], [1, 0, 4, 0, 0, 0, 0, 0, 0]]
represent_sudoku(sudoku)
def get_nbs(x,y,sudoku,also_incomplete=False):
line_nbs=sum([elem for elem in sudoku[y] if ((elem!=[0] and len(elem)==1) or also_incomplete)],[])
column_nbs=sum([sudoku[xline][x] for xline in range(9) if ((sudoku[xline][x]!=[0] and len(sudoku[xline][x])==1) or also_incomplete)],[])
area_nbs=[[j for j in i[(x/3)*3:(x/3)*3+3] if ((j!=[0] and len(j)==1) or also_incomplete)] for i in sudoku[(y/3)*3:(y/3)*3+3]]
area_nbs=sum(sum(area_nbs,[]),[])
if not also_incomplete:
return list(set(line_nbs+column_nbs+area_nbs))
return line_nbs+column_nbs+area_nbs
for x,y in srange():
sudoku[y][x]=[sudoku[y][x]]
def base_cleanup(sudoku):
while 1:
something_changed=False
for x,y in srange():
if sudoku[y][x]==[0] or len(sudoku[y][x])>1:
possible_values=range(1,10) if sudoku[y][x]==[0] else sudoku[y][x]
sudoku[y][x]=list(set(possible_values)-set(get_nbs(x,y,sudoku)))
if sudoku[y][x]==[]:
return False
something_changed=True if possible_values!=sudoku[y][x] else False
else:
sudoku[y][x]=sudoku[y][x]
if not something_changed:
break
return sudoku
def dfs(graph):
global s
if graph==False:
return False
if all(sum([[len(elem)==1 for elem in line] for line in graph],[])):
represent_sudoku(graph)
sys.exit("Done in: %s" % (time.time()-s))
enumerated_filtered_sudoku=filter(lambda x: len(x[1])>1, enumerate(sum(graph,[])))
sorted_enumerated_sudoku=sorted(enumerated_filtered_sudoku,key=lambda x: len(x[1]))
min_vertex=sorted_enumerated_sudoku[0]
possible_values=[value for value in min_vertex[1]]
for value in possible_values:
graph_copy=[[elem for elem in line] for line in graph]
y,x=elements_position[min_vertex[0]]
if not any(value==i for i in get_nbs(x,y,graph_copy)):
graph_copy[y][x]=[value]
if base_cleanup(graph_copy)!=False:
graph_copy=base_cleanup(graph_copy)
if graph_copy:
dfs(graph_copy)
return False
sudoku = base_cleanup(sudoku)
elements_position = {i:srange()[i] for i in range(81)}
s = time.time()
dfs(sudoku)
解决方案
Deepcopy can be a lot slower than simply copying the same amount of data, presumably because of all the effort that goes into detecting loops. If you copy your graph yourself in a way that avoids loops (easy, since you know the network topology) instead of delegating to deepcopy, it's likely to give you a serious speed-up. I got a 50% speedup for copying a very simple data structure element-wise (using comprehensions), and it wouldn't surprise me if complex ones gave even bigger savings.
Of course there's a bigger speedup to be gained if you can avoid making a complete copy of your entire state at each step. For example, since you're searching depth first, you could switch your approach to maintaining an undo stack: just record each list of choices you selected from, and restore them as you backtrack.