python - 如何在不达到递归限制的情况下 pickle 具有子对象或邻居关系的 class() 对象并在加载时保留对象

Question

底部有一个 TLDR。我有一个如下的 python 类，用于为 D* 寻路创建节点(不包括寻路过程):

import numpy as np
from tqdm import tqdm 
import sys
class Node():
    
    """A node class for D* Pathfinding"""

    def __init__(self,parent, position):
        self.parent = parent
        self.position = position
        self.tag = "New"
        self.state = "Empty"
        self.h = 0
        self.k = 0
        self.neighbours = []

    def __eq__(self, other):
        if type(other) != Node : return False
        else: return self.position == other.position
    def __lt__(self, other):
        return self.k < other.k

def makenodes(grid):
    
    """Given all the enpoints, make nodes for them"""
    endpoints = getendpoints(grid) 
    nodes = [Node(None,pos) for pos in endpoints]
    t = tqdm(nodes, desc='Making Nodes') #Just creates a progress bar
    for node in t:
        t.refresh()
        node.neighbours = getneighbours(node,grid,nodes)
    return nodes

def getneighbours(current_node,grid,spots):
'''Given the current node, link it to it's neighbours''' 
    neighbours = []
    for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # Adjacent nodes

            # Get node position
            node_position = (int(current_node.position[0] + new_position[0]), int(current_node.position[1] + new_position[1]))

            # Make sure within range
            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
                continue

            # Create new node
            new_node = spots[spots.index(Node(None, node_position))]
            neighbours.append(new_node)
    return neighbours

def getendpoints(grid):
    
    """returns all locations on the grid"""
    
    x,y = np.where(grid == 0)
    endpoints = [(x,y) for (x,y) in zip(x,y)]
    return endpoints

"""Actually Making The Nodes Goes as Follows"""
grid = np.zeros((100,100))
spots = makenodes(grid)

sys.setrecursionlimit(40000)
grid = np.zeros((100,100))
spots = makenodes(grid)

with open('100x100 Nodes Init 4 Connected', 'wb') as f:
    pickle.dump(spots, f)
print('Done 100x100')

该程序运行良好，但此节点制作过程在 100x100 上需要 3 分钟，但在 1000x1000 上需要一个多星期。为了解决这个问题，我使用 pickle.dump()保存所有节点，然后当我运行我的程序时，我可以使用 spots = pickle.load(...) .在 grid=np.zeros((40,50))我必须将递归限制设置为 16000 左右，在 100x100 上，我将递归限制增加到 40000 但内核死机了。

为了帮助您直观地了解节点是什么以及它们与邻居的连接方式，请参阅我绘制的图像，其中黑色:节点和白色:连接。

如果我改变，getneighbours()返回 (x,y) 坐标的元组(而不是节点对象)然后我可以 pickle 节点，因为它们不再递归。这种方法会减慢程序的其余部分，因为每次我想引用一个节点时，我都必须重建它并在列表 spots 中搜索它。 . (我已经简化了这部分的解释，因为问题已经很长了)。

如何保存这些节点对象，同时将它们的邻居保持为更大网格的节点？

TLDR: 我有一个递归的节点类，因为每个节点都包含对其邻居的引用，使其高度递归。我可以使用 pickle 为 grid = np.zeros((40,50)) 保存节点并设置相当高的递归限制 16000。对于较大的网格，我在调用 pickle.dump 时达到了最大系统递归的程度。

Answer 1

再次包含 TLDR(只是为了让您检查这是否适合您)。我找到了一种解决方法，它保留了 pickling 的省时优势，但允许节点即使在更大的尺寸下也能被 pickle。包括用于证明这一点的测试:

我更改了 makenodes() 中每个 Node() 的结构，通过剥离它的邻居来进行 pickle ，从而减少递归。使用问题中提到的方法，grid = np.zeros((40,50)) 将需要 sys.setrecursionlimt(16000) 左右。使用这种方法，Python 的内置递归限制 1000 永远不会达到，并且可以在加载 pickle 文件时重建预期的结构。

基本上 pickle 时，遵循以下程序。

1. 列出所有节点及其相应的索引，以便:

In [1]: nodes
Out [1]: [[0, <__main__.Node at 0x7fbfbebf60f0>],...]

1. 对邻居做同样的事情:

In [2]: neighbours
Out [2]: [[0, [<__main__.Node at 0x7fbfbebf6f60>, <__main__.Node at 0x7fbfbec068d0>]],...]

以上是任何大小的迷宫的节点和邻居的外观示例。 '...' 表示列表会继续包含它所包含的尽可能多的元素，另外需要注意的是 len(nodes) 应该等于 len(neighbours。索引不是必需的，但我已将其作为附加检查包括在内。

变化如下:

def makenodes(grid):
    
    """Given all the enpoints, make nodes for them"""
    
    endpoints = getendpoints(grid)
    spots = [Node(None,pos) for pos in endpoints]
    neighbours = []
    nodes = []
    t = tqdm(spots, desc='Making Nodes')
    i = 0
    for node in t:
        t.refresh()
        neighbour = getneighbours(node,grid,spots)
        nodes.append([i,node])
        neighbours.append([i,neighbour])
        i+=1
            
    return nodes, neighbours

"""Actually Making the Nodes"""
grid = np.zeros((100,100))
nodes, neighbours = makenodes(grid)
arr = np.array([nodes,neighbours])
with open('100x100 Nodes Init 4 Connected.pickle', 'wb') as f:
    pickle.dump(arr,f)
print('Done 100x100')

def reconstruct(filename):

'''Reconstruct the relationships by re-assigning neighbours'''
    with open(filename, 'rb') as file:
        f = pickle.load(file)
    nodes = f[0]
    neighbours = f[1]
    reconstructed = []
    for node in nodes:
        i = node[0]
        for neighbour in neighbours[i][1]:
            node[1].neighbours.append(neighbour)
            reconstructed.append(node[1])
    return reconstructed

nodes_in = reconstruct('100x100 Nodes Init 4 Connected.pickle')

这实现了预期的输出，并且可以在重新加载(重建)时重新建立邻居/ child 关系。此外，每个节点的邻居列表中的对象直接指向它们对应的节点，这样如果您只在选取的数组上运行它而不重建它:

In [3]: nodes2[1][1] is neighbours2[0][1][0]
Out[3]: True

时差创建和保存 50x50 网格的平均时间是。这样做 60 次的平均时间:

1. 原始方式:9.613s
2. 自适应方式(重构):9.822s

平均加载时间:

1. 原始方式:0.0582s
2. 适应方式:0.04071s

两种文件大小:410KB
结论

适应的方式可以处理更大的尺寸并且从时代来看，具有相同的性能。这两种方法都会创建相同大小的文件，因为 pickle 只存储每个对象一次，请阅读相关文档。请注意，选择使用 50x50 网格是为了防止原始方法达到递归限制。我能够用适应的方式 pickle 的最大尺寸是 500x500。我没有做得更大，仅仅是因为节点制作过程在我的机器上花费了将近 2 天的时间。然而，加载 500x500 只需要不到 1 秒的时间，因此优势更加明显。

**TLDR:**我设法将节点及其相应的邻居保存为 np.array([nodes.neighbours]) 的数组，以便在 pickling 时，在取消 pickling 时重新建立关系所需的数据可用。本质上，必要的数据以不需要提高递归限制的方式计算和保存。然后，您可以在加载时快速重建数据。