Python 中递归数据结构的好处？

Question

我正在尝试将一些数据结构实现为类 in Python（链表、二叉树、尝试等）。对于这些结构中的一些，我可以尝试将它们实现为字典的字典（例如，trie 为其子元素提供了嵌套层），或者我可以将它们实现为具有包含另一个实例的“下一个”变量对象。

我想知道递归数据结构与将所有子数据存储在成员变量中的优缺点。有速度或内存优势吗？更好的缓存？可读性？

下面是一些示例代码，说明了我在说什么，但我更感兴趣的是理论上的好处，而不是对我的伪代码的批评:)

class Trie:
    def __init__(self) -> None:
        self._trie = {}

    def insert(self, text: str) -> None:
        trie = self._trie
        for char in text:
            if char not in trie:
                trie[char] = {}
            trie = trie[char]
        trie["END"] = True

    def search(self, prefix: str) -> bool:
        trie = self._trie
        for char in prefix:
            if char not in trie:
                return False
            trie = trie[char]
        return True

class RecursiveTrie:
    def __init__(self) -> None:
        self.children: List[Optional[RecursiveTrie]] = [None] * 26
        self.end_of_word = False

    def insert(self, key: str) -> None:
        """
        If not present, inserts key into trie.
        If the key is prefix of trie node, just marks leaf node.
        """
        if not key:
            self.end_of_word = True
            return

        index = self.char_to_index(key[0])
        if self.children[index] is None:
            self.children[index] = RecursiveTrie()

        child = self.children[index]
        child.insert(key[1:])

    def search(self, key: str) -> bool:
        """ Search key in the trie. Returns true if key is present in trie. """
        if not key:
            return True

        index = self.char_to_index(key[0])
        if self.children[index] is None:
            return False

        return self.children[index].search(key[1:])

Answer 1

IMO 这两种方法中的哪一种实际上取决于您要编写的代码是真正的生产代码还是练习。

对于生产代码，您应该选择第一个版本，它更小且更易于阅读。它把 dict 当作一块基本的砖块（就像在 Python 中一样）并且嵌套的字典完全没有问题（考虑到 python 中的每个对象属性都在 dict...使用指向另一个实例的成员而不是使用 dict 乍一看似乎不是一个好主意）。

为了理解尝试，第二个版本不依赖于字典（明确地），这是你用 C 甚至 C++ 编写它的方式，其中数组与 std::map 相比可能有意义（它应该是通过对真实数据和实际生产硬件的分析证明，如今的 CPU 太复杂了，无法预测复杂算法的性能）。如果您将来需要用 low-level 语言实现 trie 或 trie 的变体，这些知识将很有用。

生产中的第二个版本 python 软件只是让同事 and/or 以后自己的日子更难过。

Python 中递归数据结构的好处？

Benefits to Recursive Data Structures in Python?

python

data-structures

trie

recursive-datastructures