Python:在不使用`setr​​ecursionlimit`的情况下腌制高递归对象

Question

我RuntimeError: maximum recursion depth exceeded试图挑选一个高度递归的树对象时一直在想.就像这里的提问者一样.

他通过设置更高的递归限制解决了他的问题sys.setrecursionlimit.但我不想这样做:我认为这更像是一种解决方法,而不是一种解决方案.因为我希望能够腌制树木,即使它们中有10,000个节点.(它目前在200左右失败.)

(另外,每个平台的真正的递归限制是不同的,我真的想避免打开这种罐头蠕虫.)

有没有办法在基础层面解决这个问题？如果只有咸菜模块将腌制使用循环而不是递归,我不会有这个问题.也许有人知道如何在不重写pickle模块的情况下导致这样的事情发生？

任何其他想法如何我可以解决这个问题将不胜感激.

Answer 1

我想大多数人从未使用过如此深度的递归结构。由于最简单的序列化实现是递归的，因此您只会看到它们。

如果我是你，我不会在这里使用公开的递归数据结构。相反，我会对每个节点进行编号，并使用链接表来有效地将数字转换为具有该编号的节点。每个节点都将通过该表使用数字引用其他节点（例如其子节点）。一个简单的属性将使语法变得简单。除了这些属性之外，无需更改处理树遍历的代码。节点构造函数必须分配一个数字并将其自身放入链接表中，这也很简单。

链接表可能只是一个节点列表，其中列表中的索引用作节点号；Python 列表似乎可以通过索引进行有效访问。如果插入速度很重要，我会预先分配一个足够长的列表，其中填充 None；它不会占用太多空间。如果节点存储自己的编号，则该结构将可以在两个方向上廉价地遍历。

如您所见，对这样一棵树进行酸洗和反酸洗在任何深度都是微不足道的。