DFS中（非常慢）deepcopy的任何替代方案？

Question

我有一个很好的图表（一个列表），包含81个顶点（每个顶点是顶点类的一个实例）。每个顶点有20个邻居。每个顶点都有许多可能的值（从1到9），考虑到对问题的一些初始约束将平均为4或5.我在此图上实现了一个简单的DFS，该节点的可能值较少， foreach值创建另一个只有一个可能值的“深层”图形，最后递归地将“deepcopied”图形再次传递到DFS。这个问题是关于速度的; cprofiling我的代码我发现，我的Mac用来解决这个问题的641秒中的635被copy.deepcopy使用。有没有解决这个问题的方法？这是我的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.因为你最聪明的人可能已经明白这个问题通常被称为数独。请注意，我不是在寻找特定于sudoku的答案，而是以抽象的方式分析问题。

[编辑]

同样的问题，用接近顶点的纯字符串表示，把< 0.75秒来解决。我张贴供参考整个代码，如果任何人经历在今后类似的问题：

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) 

Answer 1

deepcopy的可很多慢不是简单的拷贝大概是因为所有的努力相同的数据量，即进入检测循环。如果您自己复制图形的方式避免了循环（因为您知道网络拓扑结构，因此很容易），而不是将其委托给深层复制，它可能会使您大大加快速度。我以50％的速度复制一个非常简单的数据结构（使用理解），如果复杂的节省更多，我不会感到惊讶。

当然，如果您可以避免在每一步完成整个状态的完整副本，那么可以获得更大的加速。例如，由于您先搜索深度，您可以将您的方法切换为维护撤消堆栈：只需记录您选择的每个选项列表，并在回溯时恢复它们。

Answer 2

我没有充分认识到的数独细节的，但如果您使用图形的单个副本并给每个节点的类，它包括：

1）相邻的顶点 2）名单“visited”标志，可以用来跟踪已经看到什么，还有什么没有

？

您的深度优先搜索仍然可以递归，但不是打包修改后的图形子集，而只是标记节点“已访问”并继续，直到无处可去。如果你的图形连接好像应该可以工作...

Answer 3

你需要复制整个图吗？通常你只会在搜索的任何一步修改它的一小部分，所以使用不可变数据结构可能更有效率，并且只重建需要的部分。这不适用于循环，但我怀疑你的图是一个列表？

我解决了clojure中的一个类似问题，它具有对不可变结构的本地支持，并设法以这种方式获得合理的效率。但我不知道python的任何不可变的数据结构库（在某处有一个copy-on-write列表包 - 是否足够？）

[我只想澄清一个简单的例子 - 你说得对，元组是不可变的，所以如果你有过这样做的元组树：(1, (2, 3), (4, (5, 6)))，那么你可以通过创建一个只有两个产生这样(1, (2, 99), (4, (5, 6)))新树元组 - 您可以复制(4, (5, 6))而不进行深度复制。 clojure具有什么，以及我不知道python的更复杂的结构（如哈希表）遵循相同的原则。它使得dfs真的很容易，因为你不必担心值“上游”的变化。]

ps只有通过做你正在做的事情，并看到所涉及的成本，我明白了优雅弱势族群的做法...

Answer 4

的cPickle比deepcopy的速度更快：

线＃点击时间每命中％时间线内容

15           @profile 
16           def test(): 
17  100  967139 9671.4  95.0  b = deepcopy(a) 
18            #c = copy(a) 
19            #d = ujson.loads(ujson.dumps(a)) 
20            #e = json.loads(json.dumps(a)) 
21            #f = pickle.loads(pickle.dumps(a, -1)) 
22  100  50422 504.2  5.0  g = cPickle.loads(cPickle.dumps(a, -1))