-1

Assume that I have a list, and I have an element that I want to remove from it. Now suppose I have the index of that element, and I also know exactly what element it is. Would it be faster to do del myList[index] or myList.remove(element)?

Ryan Fu
  • 349
  • 1
  • 5
  • 22
  • 6
    ... why not just [perform the benchmark](https://stackoverflow.com/questions/1593019/is-there-any-simple-way-to-benchmark-python-script) yourself...? – esqew Aug 03 '21 at 22:07
  • 2
    You can bet that `del` is faster. `remove()` has to find the element, *and* then delete it, practically with `del`. – tevemadar Aug 03 '21 at 22:12
  • 2
    If you are removing elements from a list so frequently that the difference would be noticeable, you should probably be using a different data structure anyway. – chepner Aug 03 '21 at 22:12
  • 1
    @tevemadar although, algorithmically, these are both the same – juanpa.arrivillaga Aug 03 '21 at 22:15
  • 1
    Just be sure you don't do either in a loop that's iterating over that list. – Fred Larson Aug 03 '21 at 22:15
  • 1
    Does this answer your question? [How is Python's List Implemented?](https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented) – tevemadar Aug 03 '21 at 22:16
  • 1
    @juanpa.arrivillaga absolutely not, a CPython list is a flat array, you really index it directly. Also, `remove()` will remove the first matching element of the list. With `del` you can remove any. – tevemadar Aug 03 '21 at 22:20
  • 1
    @tevemadar so what? `del` and `remove` both require O(N) time. Merely *indexing* a list, i.e `mylist[idx]`, which will call `list.__getitem__` is constant time (because it is essentially a random-access lookup of an item in an underlying buffer). However, `del mylist[idx]`, which will call `list.__delitem__` still require O(N) time (at least, if you are "near the beginning") because *everything after that must move*. [This is a basic fact of the array list data structure](https://en.wikipedia.org/wiki/Dynamic_array) – juanpa.arrivillaga Aug 03 '21 at 22:21
  • 1
    @juanpa.arrivillaga Complexity is not actual runtime. – tevemadar Aug 03 '21 at 22:24
  • @tevemadar did I ever claim, *anywhere* that "complexity is actual runtime"? I stated that *algorithmically*, i.e. their time complexity, is the same. And indeed runtime wise, these will be very, very similar in CPython. – juanpa.arrivillaga Aug 03 '21 at 22:25
  • 1
    @juanpa.arrivillaga they can't be similar if one algorithm has to do a loop first, then execute the other algorithm completely. Removing the first element is practically the same for them, but removing the last one is N step longer than the absolutely 0 work required from the other. On average I would expect `remove()` being 50% slower than `del`. – tevemadar Aug 03 '21 at 22:36
  • @tevemadar yes, indeed, I agree that removing from the beginning will result in small differences, whereas removing from the end will result in large differences. However, the *average case* will still be O(N) for both, and both will suffer from polynomial behavior if done in a loop whose size will vary as well. – juanpa.arrivillaga Aug 03 '21 at 22:42

3 Answers3

1

If you know the index already, you'd use del.

Otherwise, remove first needs to traverse the list, find the (first) index for the element, then del it. This would, therefore, make it slower.

OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
1

Without any knowledge on how del or remove() performs, we can write a test using the timeit library to determine which one is faster. In this example, I simulate using both methods 10,000 times and print the average time required:

import timeit

num_runs = 10000

del_method = 'lst = [1, 2, 3]; del lst[i]'
del_setup = 'i = 0'
print(timeit.Timer(del_method, setup=del_setup).timeit(number=num_runs))

remove_method = 'lst = [1, 2, 3]; lst.remove(ele)'
remove_setup = 'ele = 1'
print(timeit.Timer(remove_method, setup=remove_setup).timeit(number=num_runs))

Ouput:

0.0005947000000000036
0.0007260000000000044

As we can see, del performs faster in this simple scenario. This makes sense knowing that remove() performs a search before removing the element. I can imagine with an even larger list the difference between the times would only grow.

VoidTwo
  • 569
  • 1
  • 7
  • 26
  • Yes, but my point is that at these small sizes, these benchmarks are very misleading. note, `ele` is always the first element, so the time difference will actually *get smaller* as the list gets bigger, because *both* `del` and `remove` have to touch every element that comes after the element that is removed, and the cost of finding the first element stays the same, and the internal re-arranging starts to dominate the time it takes to perform both operations.\ – juanpa.arrivillaga Aug 03 '21 at 22:32
  • And it's not a useless comment, it's a warning to anyone reading this not to extrapolate based on these test cases. – juanpa.arrivillaga Aug 03 '21 at 22:33
  • @juanpa.arrivillaga My comment was pointing out that stating something is useless and not providing evidence nor an argument does not help future readers. I would like to thank you for clarifying your claim, and I agree that the test case is not useful for all scenarios. I made sure to state in my original answer that this is a "simple scenario" and I never meant for it to be the one and only solution to this question. Ideally, anyone who reads my answer should write a test case for their own situation and move on from there. – VoidTwo Aug 03 '21 at 22:38
0

Short answer: del is remarkably faster than remove.

Scott
  • 4,974
  • 6
  • 35
  • 62