copy a list

[Alex Martelli]

Yuval wrote:

> Hi,
> I have to work on a list without changing it. Specifically, in every
> iteration I have to choose an object and remove it in the end of that
> iteration, repeat it until the list is empty. However, I do not want
> to touch the list itself since I need to repeat this process many
> times (start over again once the list is empty). Therefore, in order
> to "play around" with a list A, I create a copy of it: B = A[:].
> My problem is that it slows down my program siginificantly. Is it a

The copy operation, whether you perform it in the usual way you have
written or in the equivalent and more readable way B = list(A), is
_EXTREMELY_ unlikely to account for any significant slice of your
program's running time.  The copy itself takes time k * len(A) for
a reasonably small constant k; then after each copy you _repeatedly_
"choose an object", then "remove it" -- an operation that's most
likely K * len(B) for some K > k -- repeatedly until len(B) goes
down to 0 -- which suggests that part must take time proportional
to the SQUARE of len(A) [sum of 1, 2, ..., N is proportional to
the square of N).

>From what measurements do you infer that the copy itself is taking
any significant portion of your program's running time?  It seems
such an unlikely assertion that very strong proof indeed would be
necessary.  Profiling may be difficult to perform to the tiny
granularity you require, but it's easy to check by other means --
for example, what happens to your program's overall runtime if
you do the copy TWICE, i.e.:
    B = A[:]
    B = A[:]
how much does this artificial redundancy slow your program down?
The amount of slow-down is (in most situations -- _extremely_ tight
memory might distort things) a good estimate of the copy's cost.  I
suspect that measurements such as this will easily convince you
that your assertion about the copy "slowing down your program
significantly" is unfounded, and you can then focus on what is
much more likely to be the bottleneck -- the "choice and removal"
of objects from B one at a time -- it's quite possible that far
better ways exist to perform that particular sub-task.

> common problem with that operation? Is there an alternative way of
> soing it?

There is no faster way of copying a list than copying it, and it's
quite unusual for such copies to be a program's bottleneck anyway.


Alex