Simple del[] list question

[Martijn Faassen]

Gregoire Welraeds <greg at perceval.be> wrote:
> In reply to the message of Martijn Faassen sent on Apr 26 (see below) :

>> Note that another strategy which tends to avoid these troubles is to
>> construct a new list if you modify one. That is, usually if you're going

> Isn't it time and memory consuming when working on big list (eg with 1000
> or above elements) ?

Yes, probably, depending on what you do. If you're going to delete 
a lot of elements in a 1000 element list, the list will internally be
copied several times as well, each time it's resized, if I understand it
well. This happens in fast C code, though. Still, this is going to add up.
At some point it may start to be faster to construct a new list (using
the cheap 'append()' operation) and just leave those elements out. I don't
know when that's the case, however. It depends on the cost of each 
for loop iteration, the length of the list, the amount of elements that
are deleted. If it's really speed critical, just try out both strategies,
I suppose. I think there's no difference in memory consumption; the
copy the list strategy will generally be cheaper, unless you're only going
to delete a single element, and in that case it won't matter, I think.

I think for shorter lists with multiple deletes the 'construct a new list'
strategy will often be clearer and faster. Note that in the deletion case
the program needs to find out which elements to delete; this often involves
going through the lists already.

All this said, I think it's far more important in general that the 
'construct a new list' idiom produces code that's easier to understand;
efficiency is a secondary concern.

Regards,

Martijn
-- 
History of the 20th Century: WW1, WW2, WW3?
No, WWW -- Could we be going in the right direction?