7

The list.remove() function serves to remove the first time an item appears in a list. Is there a built-in function to remove the last time? For instance if I have a list, say:

X = ['sf', 'cc', 'ch', 'sc', 'sh', 'ch']

and I want to remove the last 'ch' from the list, is there a better method than what I'm currently doing, which is:

X.reverse()
X.remove('ch')
X.reverse()

I will soon also have to worry about cases where the item being removed is potentially not in the list. So methods that do not throw errors in this case would be preferred.

Toerktumlare
  • 12,548
  • 3
  • 35
  • 54
mlg4080
  • 413
  • 2
  • 4
  • 8
  • 1
    "Better" in what sense? Shorter? Easier to understand? Faster? – abarnert May 08 '15 at 01:52
  • 2
    "More pythonic" is a good catch-all. – TigerhawkT3 May 08 '15 at 01:55
  • There's really nothing wrong with this… except that I'd wrap it up in a function. I'd also probably write a non-mutating version that works on _any_ iterator, but that wouldn't be appropriate in exactly the same use cases as this, so I wouldn't call it "better", just "difference", with some overlap… – abarnert May 08 '15 at 01:58
  • I intended "better" to mean faster. And, as I'm pretty new to programming and have been slowly learning off google, I don't know what "more pythonic" would entail... but if that's a good thing, then that may be what I mean. Built-in is not required.. i Just kind of thought something should already exist and I just couldn't find the right search terms to find it. – mlg4080 May 08 '15 at 02:00
  • Not really a duplicate, but see this answer on finding them item to remove http://stackoverflow.com/questions/6890170/how-to-find-the-last-occurrence-of-an-item-in-a-python-list – Peter Gibson May 08 '15 at 02:02
  • 2
    Do you _really_ care about faster? Because you can almost certainly make this faster, but it'll be less readable, harder to understand, easier to get wrong… all for saving a few microseconds you'll probably never notice. But if faster is really what you want, edit the question to say that. – abarnert May 08 '15 at 02:05
  • 1
    Usually, if you want to do things faster, operations like "remove the last occurrence of an item from a list" should be avoided. – user2357112 May 08 '15 at 02:06
  • Also, "faster" for something like this is likely to depend quite a bit on your data. How big are your lists? How often will the value be not found? How far into the list will it be on average? (Or, you could put those another way—e.g., the list is 10000 values randomly chosen from a set of 158, one of which is the one we're searching for.) Then you can write a real benchmark. – abarnert May 08 '15 at 02:08

7 Answers7

8
if 'ch' in X:
    X.reverse()
    X.remove('ch')
    X.reverse()

The most pythonic way would be to do a try: except around remove:

X.reverse()
try:
    X.remove('ch')
except:
    pass
X.reverse()

As per your comment on speed, both of these methods are O(N), as x in list and list.reverse() are both O(N), so there's not much between them. If you expect the element to usually be there, you can save the x in list check by using try: catch, however if you expect it to usually not be there, you can save the 2 reverse()s by checking for membership first.

skolsuper
  • 629
  • 1
  • 6
  • 21
6

There's really nothing wrong with your code at all. It works, it's clear why it works, it's hard to get wrong or misunderstand.

Yes, you could make it faster, but only by a constant factor. (Your algorithm does a two reverses, for N steps each, and one remove, which is N-1 steps, so O(N). And since your data aren't sorted or anything that would help us find a value faster, it's obvious that the ideal algorithm would also be O(N).) And at the cost of making it more complicated.

The obvious probably-faster way to do it is to just manually iterate from the end until we find a value, then delete that value. That also avoids having to deal with the ValueError. Using enumerate might help… but getting it right (without copying the whole thing) may be tricky.

So, let's compare these to your existing code, both wrapped it in a try/except, and in an if:

def f_rev_ex(xs, s):
    xs.reverse()
    try:
        xs.remove(s)
    except ValueError:
        pass
    xs.reverse()

def f_rev_if(xs, s):
    if s in xs:
        xs.reverse()
        xs.remove(s)
        xs.reverse()

def f_for(xs, s):
    for i in range(len(xs)-1, -1, -1):
        if s == xs[i]:
            del xs[i]
            break

def f_enum(xs, s):
    for i, x in reversed(list(enumerate(xs))):
        if x == s:
            del xs[i]
            break

For a list as tiny as yours, the test isn't even worth running, so I invented my own random data (in real life you have to know your data, of course):

In [58]: xs = [random.choice(string.ascii_lowercase) for _ in range(10000)]
In [59]: %timeit y = x[:]; f_rev_ex(y, 'a')
10000 loops, best of 3: 34.7 µs per loop
In [60]: %timeit y = x[:]; f_rev_if(y, 'a')
10000 loops, best of 3: 35.1 µs per loop
In [61]: %timeit y = x[:]; f_for(y, 'a')
10000 loops, best of 3: 26.6 µs per loop
In [62]: %timeit y = x[:]; f_enum(y, 'a')
1000 loops, best of 3: 604 µs per loop

Well, that last one wasn't a very good idea… but the other one is about 25% faster than what we started with. So we've saved a whole 9 microseconds, on data 4 orders of magnitude larger than your actual data. It's up to you whether that's worth the less-readable, easier-to-screw up code. (And I'm not going to show you my enumerate-based implementation without copying, because I got it wrong. :P)

abarnert
  • 354,177
  • 51
  • 601
  • 671
  • 3
    Thanks for this! This is a great answer in that it demonstrates why you asked if I *really* care about it being faster... worrying about efficiency on such a small scale seems like a waste of time. I just didn't know it was so small scale. Would you say (to a beginner like me) that I should always wait until I have working code to worry about trying to optimize it, and then after it works decide if it (or a piece of it) is slow enough I care about trying to optimize it? – mlg4080 May 08 '15 at 02:39
  • 2
    @mlg4080: The rule of thumb is: major algorithmic improvements—like taking 2*N steps (linear) instead of N*N (quadratic) are usually worth doing up-front; constant-factor improvements—like taking 2*N steps instead of 3*N (both linear), don't optimize until you know you have a problem. But it's just a rule of thumb. Sometimes, there are well-known patterns that are just as simple and usually 20% faster, so you might as well do the faster one; sometimes quadratic time is fine because N will never be more than 7; etc. – abarnert May 08 '15 at 02:44
  • This really should be the accepted answer. Good explanation and testing walkthrough – Isaac Sep 22 '21 at 14:18
2

Produce a reversed list, preserving the original indexes and remove the first instance you find.

X = ['sf', 'cc', 'ch', 'sc', 'sh', 'ch']

print X

for i, e in reversed(list(enumerate(X))):
    if e == 'ch':
        del X[i]
        break

print X

If it doesn't find the string it leaves the list untouched.

Paul Rooney
  • 20,879
  • 9
  • 40
  • 61
  • I'd expect this to much slower than the original code. – abarnert May 08 '15 at 02:24
  • Fair enough its got a few intermediate objects. Not for large data sets. Interesting nonetheless. – Paul Rooney May 08 '15 at 02:33
  • Yeah, for the question as originally asked, this is more concise, about as simple… and it shows off how useful `enumerate` is, which every novice Python programmer needs to see early. :) And since he hasn't actually edited the question to specifically say "faster" is what he was interested in, I'm not taking back my upvote. – abarnert May 08 '15 at 02:49
2

Without reverse() and similar to one answer above:

def RightRemove(alist, x):
    for i in range(len(alist), 0, -1): # from end to begin
        if alist[i-1] == x: # element x exists
            alist.pop(i-1) # remove it
            break # return
EngiDev
  • 41
  • 6
1

Well first you can check if the item is in the list using a if in statement. Then you can reverse the list and remove the element.

if "ch" in X:
    X.reverse()
    X.remove("ch")
    X.reverse()
michaelpri
  • 3,521
  • 4
  • 30
  • 46
0

Yet another answer...

def remove_last_occurrence(lst, element):
    '''
    Removes the last occurrence of a given element in a list (modifies list in-place).

    :return bool:
        True if the element was found and False otherwise.
    '''
    for i, s in enumerate(reversed(lst)):
        if s == element:
            del lst[len(lst) - 1 - i]
            return True
    return False
Fabio Zadrozny
  • 24,814
  • 4
  • 66
  • 78
0

Yet another one ..

def remove_last_occurrence_one_liner(lst, element):
    """
    Removes the last occurrence of a given element in a list (modifies list in-place).
    Raises same exception than lst.index(element) if element can not be found.
    """
    del lst[len(lst) - lst[::-1].index(element) - 1]

But it does not beat the for loop from abarnert

x = [random.choice(string.ascii_lowercase) for _ in range(10000)]
%timeit y = x[:]; f_rev_ex(y, 'a')
34.3 µs ± 219 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit y = x[:]; f_rev_if(y, 'a')
34.9 µs ± 195 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit y = x[:]; f_for(y, 'a')
26.9 µs ± 109 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit y = x[:]; f_enum(y, 'a')
699 µs ± 4.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit y = x[:]; remove_last_occurrence_one_liner(y, 'a')
49 µs ± 375 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
smarie
  • 4,568
  • 24
  • 39