6

Suppose I have a list TruncList with some number of elements greater than n. If I want to remove n elements from the end of that list, is it faster to redefine the list as a slice of itself preserving the desired elements, as by TruncList = TruncList[:-n], or to delete the slice of unwanted elements from the list, as by del TruncList[-n:]?

Does the answer change if I was removing the first n elements from TruncList instead, as in TruncList = TruncList[n:] versus del TruncList[:n]?

Besides speed, is one of these methods more Pythonic than the other?

I would imagine that the redefinition method might be slower, since it iterates through TruncList and then reassigns it, while del truncates the list in place, but I'm not sure if either of these are the case.

I would also suppose del is the better route, because it seems like the natural use of the function.

5
  • 3
    Why don't you try it? See the timeit module.
    – mhawke
    Mar 22, 2015 at 10:16
  • @mhawke That may be the best question of all. :v I'll do that now.
    – Augusta
    Mar 22, 2015 at 10:17
  • 2
    @Augusta And then submit an answer to your question with your results so that future generations will learn :)
    – halex
    Mar 22, 2015 at 10:20
  • @halex I'll do just that!
    – Augusta
    Mar 22, 2015 at 10:25
  • Depends what you what to do with the list afterwards. If you pop() each item then that will leave the list in-place with "empty" entries that can be reused. In CPython it is more efficient to pop from the right. Subsequent appends to the list will use the entries without a resize (if the same number of elements, or less). Of course the performance effect will vary depending on the size of the list. Deleting a slice on the left will mean a resize (realloc or equivalent).
    – cdarke
    Mar 22, 2015 at 10:46

2 Answers 2

7

It'll depend entirely on how many elements you delete.

In CPython, the list type uses a dynamic overallocation strategy to avoid having to resize the underlying C array too often. There is an array to hold the elements, and it is kept slightly too large at all times.

Deletion then (using del TruncList[-n:]) could be a virtually free operation, provided n is sufficiently small. In fact, you can safely delete up to half the size of the over-allocated array, before a resize occurs. Resizing requires copying across all existing references to a new array.

Using a slice is always going to create new list object, requiring allocation of memory and copying across of the elements involved. This is slightly more work than re-allocation of data.

So, without measuring time performance (using timeit), I'd expect the del option to be faster than slicing; in the case of n < len(TruncList) // 2 (less than half the length) in many cases you don't even incur a resize, and even if you did, slightly less work needs to be done as only the internal array has to be recreated.

When you remove items from the front, you'll always have to recreate the internal array. The differences won't be a stark then, but creating a slice is still going to result in allocation for an entirely new object.

3
  • I have a list that (for external reasons) has twice the elements I need (which are "packages" of 3). When I want to get rid of the duplicates using def deldup(al): for i in reversed(range(len(al))): if i%6>2: del al[i]; return al, it's almost instant and takes up no memory. when i do def deldup(al): return [x for i,x in enumerate(al) if i%6>2] it takes forever and crashes my computer because of the memory usage (even if I del(al)).... what am I doing wrong in the second approach?
    – BUFU
    Oct 1, 2020 at 14:06
  • @BUFU your list comprehension copies the second half (all 4th,5th and 6th elements), where the first version deletes those elements to only keep the first half. I have no idea how big your input is here but I would expect something else to be different apart from the implementation of deldup() shown here to have problems like you described, however. Sorry, this is not something I can help with in comments.
    – Martijn Pieters
    Oct 1, 2020 at 22:45
  • yeah, I've tried i%6<3 as well, no difference there. But thanks anyways. I was just wondering if there was some obvious stupidity on my part that led to my demise. :D I'll just go with del then.
    – BUFU
    Oct 2, 2020 at 8:20
5

So I tested it out myself using timeit with these samples:

  ## Make a list of 500 elements and then remove the first 80...
def slice_front():
    "Make the list equal to all but the first eighty elements."
    trunc = 80
    TruncList = range(500)
    TruncList = TruncList[trunc:]

def del_front():
    "Use del to remove the first eighty elements."
    trunc = 80
    TruncList = range(500)
    del TruncList[:trunc]


  ## Make a list of 500 elements and then remove the last 80...
def slice_end():
    "Make the list equal to all but the last eighty elements."
    trunc = 80
    TruncList = range(500)
    TruncList = TruncList[:-trunc]

def del_end():
    "Delete the last eighty elements from the list using del."
    trunc = 80
    TruncList = range(500)
    del TruncList[-trunc:]

...and got these results:

>>> timeit.timeit(slice_front, number = 66666)
1.3381525804258112
>>> timeit.timeit(del_front, number = 66666)
1.0384902281466895
>>> timeit.timeit(slice_end, number = 66666)
1.3457694381917094
>>> timeit.timeit(del_end, number = 66666)
1.026411701603827

It looks like del is faster, and by quite a broad margin.


EDIT

If I run the same samples but with trunc = 2 instead, these are the results:

>>> timeit.timeit(slice_front, number = 66666)
1.3947686585537422
>>> timeit.timeit(del_front, number = 66666)
1.0224893312699308
>>> timeit.timeit(slice_end, number = 66666)
1.4089230444569498
>>> timeit.timeit(del_end, number = 66666)
1.042288032264116

del is still faster.

Here's a test where nearly all of the list elements are removed: trunc = 80 and TruncList = range(81)...

>>> timeit.timeit(slice_front, number = 66666)
0.25171681555993247
>>> timeit.timeit(del_front, number = 66666)
0.2696609454136185
>>> timeit.timeit(slice_end, number = 66666)
0.2635454769274057
>>> timeit.timeit(del_end, number = 66666)
0.294670910710936

In this case, del is somewhat slower than the redefinition method.

11
  • You are removing far fewer than half the elements, so no (internal) resize takes place.
    – Martijn Pieters
    Mar 22, 2015 at 10:53
  • @MartijnPieters I thought that the lengths involved might have something to do with it right after I posted the first set of numbers, so I ran a few more tests with different parameters. It's about as you say.
    – Augusta
    Mar 22, 2015 at 11:01
  • Timings would be improved if you could create the test lists up front; create N lists of equal size for N timeit tests and have each test truncate one of those objects. It'll illustrate better what the difference is between the two.
    – Martijn Pieters
    Mar 22, 2015 at 11:01
  • 2
    You can use from __main__ import ... in the setup argument (the second argument to timeit to import names from the interactive interpreter, then use a string for the first argument to use those names. from __main__ import slice_front as test, long_list_of_lists; testdata = iter(long_list_of_lists) for example, and the first argument could be test(next(testdata)) to pass in each element of long_list_of_lists to slice_front each iteration of the timeit run.
    – Martijn Pieters
    Mar 22, 2015 at 11:19
  • 1
    you can do that; the whole list is still created up front though. The list comprehension is executed first before calling iter().
    – Martijn Pieters
    Mar 22, 2015 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.