python 中树节点的大量变化字典

Question

我正在尝试实现一个分层树结构，其中每个节点都有一个略有变化的字典版本。我的问题是，与 R 中的类似结构不同，python 字典只是外部变量的标签，而不是真正的 'value containers'。因此，在其中一个节点所做的任何更改也会影响所有其他节点的字典。

鉴于 dict 的这种行为，在 python 中实现它的正确方法是什么？这似乎是一种常见的方法，所以我觉得我一定遗漏了一些东西，但我已经用头撞墙好几个小时了。

背景： 我正在尝试在 python 中使用棋盘状态字典为基于回合的完美信息对抗性棋盘游戏实施 Minimax 方法。我根据所有可能的移动创建了节点和子级的层次树结构，到目前为止，我一直在尝试修改每个节点的字典。我不清楚 python 中字典的真实性质，所以我一直在与我的方法的奇怪结果作斗争，因为每个节点的更改也应用于所有其他节点。

例子

#Create some original state (dict of dicts)
state_original = {'field1' : {'player':1, 'count':2}, 'field2' : {'player':2, 'state': 4}}
print(state_original)

#Define object for the tree nodes
class Node(object):
  def __init__(self, depth, state, field=None):
    self.depth = depth
    self.state = state
    self.field = field
    self.subnodes = []
    if self.depth > 0:
      self.SpawnSubnodes()
  def SpawnSubnodes(self):
    for field in self.state:
      depth_new = self.depth -1
      state_new = self.state
      state_new[field]['count'] += 1
      self.subnodes.append(Node(depth_new, state_new, field))

#Build tree
nodes = Node(3, state_original)
nodes.subnodes

#But: This is a mess now
print(state_original)

#This is a mess, too. Results are not meaningful :( 
print(nodes.subnodes[1].state)

它适用于 deepcopy，但对于我的（较大的）树来说太慢了

from copy import deepcopy

#Define object for the tree nodes
class Node(object):
  def __init__(self, depth, state, field=None):
    self.depth = depth
    self.state = state
    self.field = field
    self.subnodes = []
    if self.depth > 0:
      self.SpawnSubnodes()
  def SpawnSubnodes(self):
    for field in self.state:
      depth_new = self.depth -1
      state_new = deepcopy(self.state)
      state_new[field]['count'] += 1
      self.subnodes.append(Node(depth_new, state_new, field))

编辑： 我意识到复制对我不起作用，因为我的董事会状态是字典的字典而不是简单的字典。我更新了我的示例代码以准确反映这一点。虽然一个潜在的解决方法是尝试提出一个更简单的董事会表示（可能将其分成 "board shape" 字典和 "board state" 字典），但我觉得应该有更多 pythonic如何解决这个问题？

Answer 1

而不是 copy.deepcopy，请使用 copy.copy（浅拷贝），因为您并不真正需要 deep copy。

import copy

#Define object for the tree nodes
class Node(object):
  def __init__(self, depth, state, field=None):
    self.depth = depth
    self.state = state
    self.field = field
    self.subnodes = []
    if self.depth > 0:
      self.SpawnSubnodes()
  def SpawnSubnodes(self):
    for field in self.state:
      depth_new = self.depth -1
      state_new = copy.copy(self.state)
      state_new[field] += 1
      self.subnodes.append(Node(depth_new, state_new, field))

浅拷贝比深拷贝快得多。这是一个简单的计时测试：

In [5]: %timeit copy.deepcopy(state_original)
The slowest run took 6.96 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 4.97 µs per loop

In [6]: %timeit copy.copy(state_original)
The slowest run took 8.84 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 709 ns per loop

注意：上述解决方案仅在有问题的字典是简单时有效，即它不包含其他字典。

如果开头的字典包含其他字典 simple-dicts，迭代地执行其内容的浅拷贝可能比深拷贝操作更快。

def mycopy(d):
    return {k: copy.copy(v) for k, v in d.items()}

对 mycopy 的初步性能分析使我大致比 copy.deepcopy 有了 order-of-magnitude 的改进。

python 中树节点的大量变化字典

large number of changing dictionaries for tree nodes in python

python

tree

dictionary

minimax