2

Problem

I am working on a breadth-first search algorithm for my maze solver and it is working so far. I am keeping track of the current stack by copying the previous one and appending the current value to it.

Since copying list takes a great amount of time I would like to create multiple copies of the list within one operation.

What I've tried so far

  • Copy the list and assign it to multiple variables.

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

  • Use numpy arrays with copy function (faster than list[:]).

Question

What is the fastest way to create multiple copies of one list?

jsmolka
  • 780
  • 6
  • 15
  • Do you really need lists? I usually go for a [spaghetti stack](https://en.wikipedia.org/wiki/Parent_pointer_tree) for applications like this and only build a list once I've found the goal, if I need a list. – user2357112 Aug 31 '17 at 08:04
  • You're using `l[:]`, so I assume you want a shallow copy? – stelioslogothetis Aug 31 '17 at 08:05
  • @user2357112 I do not need lists necessarily. Which datastructure would I use the keep track of such a stack? A dictionary? – jsmolka Aug 31 '17 at 08:10
  • @jsmolka: I've posted an answer describing how you'd do it with a spaghetti stack. – user2357112 Aug 31 '17 at 08:12

2 Answers2

5

Don't use ordinary Python lists for your stacks. Use Lisp-style linked lists, so your stacks share most of their structure with each other and building a new stack with an additional element is constant time:

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]

Here, push runs in constant time and produces a new stack, without mutating the old, so you can call push on the old stack repeatedly without copying it.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • 1
    Can I ask, what this is? Are you modelling a stack with python? – cs95 Aug 31 '17 at 08:18
  • 2
    @cᴏʟᴅsᴘᴇᴇᴅ: It's a stack implementation where an empty stack is represented by an empty tuple and a non-empty stack is represented as a `(top item, stack containing the rest of the items)` pair. It's probably more familiar if you have experience with a functional language; in some functional languages, it's even the language's core data structure. – user2357112 Aug 31 '17 at 08:23
0

You can just bulk copy it:

def copyList(thelist, number_of_copies):
    return tuple(thelist[:] for _ in xrange(number_of_copies))

a, b, c = copyList(range(10), 3)

Here you have a live example

Netwave
  • 40,134
  • 6
  • 50
  • 93
  • @Avión, it is jut because of the unpacking, if you use more the either you capture all the copies in the tuple in a variable or you unpack with more variables. – Netwave Aug 31 '17 at 08:09