Python中Tuple打包解包性能差异：两类栈实现为何差2000倍？

有两个使用Tuple、打包（packing）和解包（unpacking）实现的栈类，二者性能差异高达2000倍。请问*self.stack, outitem = self.stack这行代码是否是导致性能差距的关键原因？

代码实现 #

from time import time


class StackT:
    def __init__(self):
        self.stack = tuple()

    def push(self, otheritem):
        self.stack = (*self.stack, otheritem)

    def pop(self):
        *self.stack, outitem = self.stack
        return outitem


class Stack:
    def __init__(self):
        self._items = None
        self._size = 0

    def push(self, item):
        self._items = (item, self._items)

    def pop(self):
        (item, self._items) = self._items
        return item


def timer(func):
    def wrapper(*args, **kwargs):
        print("starting count.")
        now = time()
        result = func(*args, **kwargs)
        print(f"counted {time() - now} seconds")
        return result
    return wrapper


@timer
def f(cls, times):
    print(f"class {cls.__name__}, {times} times")
    stack = cls()
    for i in range(times):
        stack.push(i)
    for i in range(times):
        stack.pop()

运行结果 #

f(StackT, 100_000)
f(Stack, 100_000)

# starting count.
# class StackT, 100000 times
# counted 63.61870002746582 seconds
# starting count.
# class Stack, 100000 times
# counted 0.02500009536743164 seconds

结论与分析 #

是的，*self.stack, outitem = self.stack这行代码是导致性能差距的核心原因之一，再加上StackT的push方法的低效实现，共同造成了极端的性能差异：

1. Stack类的高效逻辑 #

Stack采用链式元组结构：

• push时仅创建一个包含新元素和当前栈顶的二元组，无需复制整个栈，时间复杂度为O(1)
• pop时仅拆解这个二元组，取出栈顶元素并更新栈顶指针，同样是O(1)操作

无论栈的大小如何，每次操作都只处理单个元组，总时间复杂度为O(n)（n为操作次数）。

2. StackT类的低效逻辑 #

StackT错误地将元组当作可变列表使用，每次操作都需要复制整个栈的元素：

• push方法：self.stack = (*self.stack, otheritem)会遍历现有元组的所有元素，复制后拼接新元素创建全新元组，栈大小为k时时间复杂度为O(k)
• pop方法：*self.stack, outitem = self.stack同样需要遍历整个元组，将除最后一个元素外的所有元素重新打包成新元组，时间复杂度也是O(k)

当执行10万次push+pop操作时，StackT的总时间复杂度为O(n²)（每次操作的元素量从1累加至10万），这直接导致了它比Stack慢数千倍。

本质差异 #

Stack利用元组的不可变特性实现链式存储，符合元组的设计场景；而StackT把元组当成可动态扩容/缩容的容器使用，完全违背了元组适合存储固定长度数据的初衷，必然导致性能灾难。

内容的提问来源于stack exchange，提问作者Vairuotojo Pazymejimas