python - 创建列表的多个副本的最快方法

Question

问题

我正在为我的迷宫解算器开发广度优先搜索算法，目前它正在运行。我通过复制前一个堆栈并将当前值附加到它来跟踪当前堆栈。

由于复制列表需要花费大量时间，所以我想在一次操作中创建列表的多个副本。

到目前为止我尝试了什么

• 复制列表并将其分配给多个变量。

  l = [1, 2, 3]
  a = b = c = l[:]  # Just creates references and no individual lists
  

• 将 numpy 数组与 copy 函数结合使用(比 list[:] 更快)。

问题

创建一个列表的多个副本的最快方法是什么？

Answer 1

不要为您的堆栈使用普通的 Python 列表。使用 Lisp 风格的链表，所以你的栈彼此共享它们的大部分结构，并且用一个额外的元素构建一个新的栈是常数时间的:

def empty_stack():
    return ()
def push(stack, item):
    return (item, stack)
def stack_to_list(stack):
    l = []
    while stack:
        item, stack = stack
        l.append(item)
    return l[::-1]

这里，push 以恒定时间运行并产生一个新堆栈，而不会改变旧堆栈，因此您可以在旧堆栈上重复调用 push 而无需复制它。