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

Question

问题

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

由于复制列表需要花费大量时间,因此我希望在一次操作中创建列表的多个副本.

到目前为止我尝试过的

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

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

• 使用具有copy函数的numpy数组(快于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重复调用旧堆栈而无需复制它.