Pop a list from beginning ? and memory saving...
James T. Dennis
jadestar at idiom.com
Tue Jun 18 05:12:08 CEST 2002
Shagshag13 <shagshag13 at yahoo.fr> wrote:
> I had a huge list containing consuming data, as i only need a one pass in a
> for statement,
> i'm wondering if by doing this with a pop i could save memory ? (as i think
> that python
> free it after the pop...)
> and is there a way to pop from the beginning of the list ? (i think i could
> use reverse but
> i don't know if this memory consuming)
The problem with l.pop(0) is that it will run at O(n) time
(linearly proportional to the list's size).
From what I gather the underlying C structure of a list allows
things to be appended and popped (from the end) in constant time.
So the obvious answer would be to build the list in reverse order
and then pop() them all off the end with a simple:
If that's not feasible (you can't build the list in reverse order)
then you might try profiling list.reverse() (it might be implemented
as an inplace reversal in the underlying C or Java. If so the reverse()
method will be O(n) and the processing will be O(1) for each item
for a total of 2 * O(n). That may not be ideal but it's much better
than ~ O(n) * 1/2 * 0(n) (which is the roughly the result of the
original approach where each iteration takes O(n)).
So, the critical question is:
Is the list's reverse() method done in place and does it
run in linear time (or better? if so, how)?
More information about the Python-list