Python3中类与字典访问时间复杂度对比及Trie实现性能差异

问题背景 #

我分别用类和字典实现了Trie树，在处理约10万个整数的大数据集时，字典实现的运行速度比类实现快约2.5倍。最初用类实现时多次出现超时错误，改用字典后性能大幅提升。我想了解原因：字典的键值访问是O(1)，但类实现更慢，类的属性访问是否也是O(1)？

基于类的Trie实现 #

class TrieNode:
    def __init__(self):
        self.children={}

class Trie:
    def __init__(self):
        self.root=TrieNode()

    def addNum(self,num):
        node=self.root
        for i in range(31,-1,-1):
            bit=(num>>i)&1
            if bit not in node.children:
                node.children[bit]=TrieNode()
            node=node.children[bit]

    def getMax(self,num,cur,bit,node):
        if not node.children:
            return cur
        numbit=(num>>bit)&1
        res=-1
        if numbit^1 in node.children:
            res=self.getMax(num,cur*2+1,bit-1,node.children[numbit^1])
        elif numbit^0 in node.children:
            res=self.getMax(num,cur*2,bit-1,node.children[numbit^0])
        return res

基于字典的Trie实现 #

class Trie:
    def __init__(self):
        self.root={}

    def addNum(self,num):
        node=self.root
        for i in range(31,-1,-1):
            bit=(num>>i)&1
            node.setdefault(bit,{})
            node=node[bit]

    def getMax(self,num,bit):
        cur,node=0,self.root
        for i in range(31,-1,-1):
            numbit=(num>>i)&1
            if numbit^1 in node:
                cur,node=cur*2+1,node[numbit^1]
            elif numbit^0 in node:
                cur,node=cur*2,node[numbit^0]
        return cur

性能差异原因解析 #

1. 类属性访问的间接开销 #

类的属性访问确实是O(1)，但底层实现比字典键访问多了一层间接性：

• 类实例的属性默认存储在__dict__字典中，访问node.children本质是先从实例的__dict__中取出children对应的字典，再进行后续操作，相当于多了一次字典查找。
• 字典的键访问是直接操作哈希表，没有额外的间接层，执行路径更短。

2. 实例创建的额外成本 #

类实现中每次新增节点都要创建TrieNode实例，而字典实现仅创建空字典：

• 创建类实例涉及元类调用、属性初始化、内存元数据分配等步骤，开销远大于创建内置字典。
• 字典是Python原生优化的数据结构，创建和初始化的成本极低。

3. 递归与迭代的执行效率差 #

类实现的getMax采用递归，字典实现用迭代：

• 递归调用会产生栈帧开销，每次调用都要保存上下文、传递参数，处理大量数据时，累积的栈操作成本非常显著。
• 迭代避免了栈帧的创建与销毁，执行流程更连贯，效率更高。

4. 内存布局与缓存利用率 #

类实例带有额外的元数据（如类型指针、__dict__引用等），相比字典内存占用更高：

• 更多的内存占用会增加垃圾回收的压力，频繁的GC操作会拖慢整体速度。
• 类实例的内存布局更零散，CPU缓存命中率更低，无法有效利用缓存加速数据访问。

内容的提问来源于stack exchange，提问作者Ahmet Cicek