26

I was wondering if there was an easy solution to the the following problem. The problem here is that I want to keep every element occurring inside this list after the initial condition is true. The condition here being that I want to remove everything before the condition that a value is greater than 18 is true, but keep everything after. Example

Input:

p = [4,9,10,4,20,13,29,3,39]

Expected output:

p = [20,13,29,3,39]

I know that you can filter over the entire list through

[x for x in p if x>18] 

But I want to stop this operation once the first value above 18 is found, and then include the rest of the values regardless if they satisfy the condition or not. It seems like an easy problem but I haven't found the solution to it yet.

0

5 Answers 5

50

You can use itertools.dropwhile:

from itertools import dropwhile

p = [4,9,10,4,20,13,29,3,39]

p = dropwhile(lambda x: x <= 18, p)
print(*p) # 20 13 29 3 39

In my opinion, this is arguably the easiest-to-read version. This also corresponds to a common pattern in other functional programming languages, such as dropWhile (<=18) p in Haskell and p.dropWhile(_ <= 18) in Scala.


Alternatively, using walrus operator (only available in python 3.8+):

exceeded = False
p = [x for x in p if (exceeded := exceeded or x > 18)]
print(p) # [20, 13, 29, 3, 39]

But my guess is that some people don't like this style. In that case, one can do an explicit for loop (ilkkachu's suggestion):

for i, x in enumerate(p):
    if x > 18:
        output = p[i:]
        break
else:
    output = [] # alternatively just put output = [] before for
4
  • 4
    Nice use of warlus here. It's worthy mentioning it only exists in Python 3.8+
    – Daniel Hao
    Commented Feb 3, 2022 at 1:47
  • 1
    I feel what you said about the walrus. For some reason the last one still looks a bit annoying (it might be just me). Since we're taking a tailing part of the list, using p[i:] to bypass the temp var seems inviting. Something like for i, x in enumerate(p): if x > 18: out = p[i:]; break (with appropriate white space).
    – ilkkachu
    Commented Feb 3, 2022 at 13:01
  • @ilkkachu Nice point! I've included that.
    – j1-lee
    Commented Feb 3, 2022 at 18:49
  • 4
    @NewbieAF, well, mostly an explicit loop is likely to be immediately readable to pretty much anyone, while a tight one-liner may take some more decoding. I'm not saying the one in the other answer is wrong, and if I did, I'd probably get chewed on how it's the Pythonic way or whatever. No idea about performance either. Just that I felt the explicit loop here could be simplified while still keeping it readable.
    – ilkkachu
    Commented Feb 3, 2022 at 22:16
23

You could use enumerate and list slicing in a generator expression and next:

out = next((p[i:] for i, item in enumerate(p) if item > 18), [])

Output:

[20, 13, 29, 3, 39]

In terms of runtime, it depends on the data structure.

The plots below show the runtime difference among the answers on here for various lengths of p.

If the original data is a list, then using a lazy iterator as proposed by @Kelly Bundy is the clear winner:

enter image description here

But if the initial data is a ndarray object, then the vectorized operations as proposed by @richardec and @0x263A (for large arrays) are faster. In particular, numpy beats list methods regardless of array size. But for very large arrays, pandas starts to perform better than numpy (I don't know why, I (and I'm sure others) would appreciate it if anyone can explain it).

enter image description here

Code used to generate the first plot:

import perfplot
import numpy as np
import pandas as pd
import random
from itertools import dropwhile

def it_dropwhile(p):
    return list(dropwhile(lambda x: x <= 18, p))

def walrus(p):
    exceeded = False
    return [x for x in p if (exceeded := exceeded or x > 18)]

def explicit_loop(p):
    for i, x in enumerate(p):
        if x > 18:
            output = p[i:]
            break
    else:
        output = []
    return output

def genexpr_next(p):
    return next((p[i:] for i, item in enumerate(p) if item > 18), [])

def np_argmax(p):
    return p[(np.array(p) > 18).argmax():]

def pd_idxmax(p):
    s = pd.Series(p)
    return s[s.gt(18).idxmax():]

def list_index(p):
    for x in p:
        if x > 18:
            return p[p.index(x):]
    return []

def lazy_iter(p):
    it = iter(p)
    for x in it:
        if x > 18:
            return [x, *it]
    return []

perfplot.show(
    setup=lambda n: random.choices(range(0, 15), k=10*n) + random.choices(range(-20,30), k=10*n),
    kernels=[it_dropwhile, walrus, explicit_loop, genexpr_next, np_argmax, pd_idxmax, list_index, lazy_iter],
    labels=['it_dropwhile','walrus','explicit_loop','genexpr_next','np_argmax','pd_idxmax', 'list_index', 'lazy_iter'],
    n_range=[2 ** k for k in range(18)],
    equality_check=np.allclose,
    xlabel='~n/20'
)

Code used to generate the second plot (note that I had to modify list_index because numpy doesn't have index method):

def list_index(p):
    for x in p:
        if x > 18:
            return p[np.where(p==x)[0][0]:]
    return []

perfplot.show(
    setup=lambda n: np.hstack([np.random.randint(0,15,10*n), np.random.randint(-20,30,10*n)]),
    kernels=[it_dropwhile, walrus, explicit_loop, genexpr_next, np_argmax, pd_idxmax, list_index, lazy_iter],
    labels=['it_dropwhile','walrus','explicit_loop','genexpr_next','np_argmax','pd_idxmax', 'list_index', 'lazy_iter'],
    n_range=[2 ** k for k in range(18)],
    equality_check=np.allclose,
    xlabel='~n/20'
)
6
  • 8
    such a beautiful, elegant use of only built-ins, that doesn't run more than it has to! Generator expressions rock ! Commented Feb 3, 2022 at 14:51
  • 4
    @Graipher Are you sure about that? ideone.com/UAVscC Commented Feb 4, 2022 at 1:56
  • @Unmitigated true, the if condition prevents the statement to be executed in the first place, and it only operates on the item.
    – Graipher
    Commented Feb 4, 2022 at 5:59
  • Could you please include my solutions in your benchmarks? I think they'll be the fastest in your first benchmark, didn't try the other. Commented Feb 12, 2022 at 16:07
  • 1
    Thanks for the update. The itertools.dropwhile is slow due to the function calls. Looks like using 18 .__ge__ instead of the lambda would make it significantly faster, but in my experience, people tend to dislike that for some reason. Commented Feb 12, 2022 at 20:23
8

Great solutions here; just wanted to demonstrate how to do it with numpy:

>>> import numpy as np
>>> p[(np.array(p) > 18).argmax():]
[20, 13, 29, 3, 39]

Since there are a lot of nice answers here, I decided to run some simple benchmarks. The first one uses the OP's sample array ([4,9,10,4,20,13,29,3,39]) of length 9. The second uses randomly generated array of length 20 thousand, where the first half is between 0 and 15, and the second half is between -20 and 30 (so that the split wouldn't occur right in the center).

Using the OP's data (array of length 9):

%timeit enke()
650 ns ± 15.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit j1lee1()
546 ns ± 4.22 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit j1lee2()
551 ns ± 19 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit j2lee3()
536 ns ± 12.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%timeit richardec()
2.08 µs ± 16 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Using an array of length 20,000 (20 thousand):

%timeit enke()
1.5 ms ± 34.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit j1lee1()
1.95 ms ± 43 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit j1lee2()
2.1 ms ± 53.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit j2lee3()
2.33 ms ± 96.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit richardec()
13.3 µs ± 461 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Code to generate second array:

p = np.hstack([np.random.randint(0,15,10000),np.random.randint(-20,30,10000)])

So, for the small case, numpy is a slug and not needed. But the large case, numpy is almost 100x times faster and the way to go! :)

3
  • 3
    Thank you very much for this answer! I do notice a pretty big difference in output time for the actual use case (which was a rather large pandas dataframe) over the other solutions posted. Commented Feb 3, 2022 at 2:45
  • @cinderashes was this the fastest for your real use case? :)
    – user17242583
    Commented Feb 3, 2022 at 22:59
  • @cinderashes If your real use case is a DataFrame, it would have been better (for you, though maybe not for other people) if you had asked your question about a DataFrame, rather than about a list as you did. As you can see from this answer, the performance can vary significantly between them!
    – David Z
    Commented Feb 4, 2022 at 9:59
7

I noticed the OP mention under an answer that p is actually a Pandas DataFrame. Here is a method of filtering all elements up to the first instance of a number greater than 18 using Pandas:

import pandas as pd
df = pd.DataFrame([4,9,10,4,20,13,29,3,39])
df = df[df[0].gt(18).idxmax():]
print(df)

Outputs:

    0
4  20
5  13
6  29
7   3
8  39

Note: I'm blind to the actual structure of your DataFrame so I just used exactly what was given.

1

In my experience, at least for lists of ints, using enumerate just to find one index and throwing all other indexes away is so wasteful that it's faster to first only find the element and then use list.index to find its index. Based on some testing, I expect it to be about factor 1.44 faster than the explicit_loop solution (which uses enumerate) in @enke's benchmark.

def start_over_18(p):
    for x in p:
        if x > 18:
            return p[p.index(x):]
    return []

Another solution, using an iterator so I don't have to bother with indexes at all. Seems to be about twice as fast as the explicit_loop solution:

def start_over_18(p):
    it = iter(p)
    for x in it:
        if x > 18:
            return [x, *it]
    return []

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.