short-circuiting any/all ?

[kj]

I have a list of items L, and a test function is_invalid that checks
the validity of each item. To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L, even though
the value returned by any() is fully determined by the first True
in its argument. In other words, all calls to is_invalid after
the first one to return True are superfluous. Is there a
short-circuiting counterpart to any(map(is_invalid, L)) that avoids
these superfluous calls?

OK, there's this one, of course:

def _any_invalid(L):
for i in L:
if is_invalid(i):
return True
return False

But is there anything built-in? (I imagine that a lazy version of
map *may* do the trick, *if* any() will let it be lazy.)

TIA!

~K

 

[Tim Golden]

I have a list of items L, and a test function is_invalid that checks
the validity of each item. To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L, even though
the value returned by any() is fully determined by the first True
in its argument. In other words, all calls to is_invalid after
the first one to return True are superfluous. Is there a
short-circuiting counterpart to any(map(is_invalid, L)) that avoids
these superfluous calls?

OK, there's this one, of course:

def _any_invalid(L):
for i in L:
if is_invalid(i):
return True
return False

But is there anything built-in? (I imagine that a lazy version of
map *may* do the trick, *if* any() will let it be lazy.)

Have I missed the point of your question, perhaps? This seems
to work as lazily as you'd like...

<code>
def less_than_five (x):
print "testing", x
return x < 5

L = range (10)
print any (less_than_five (i) for i in L)
print all (less_than_five (i) for i in L) # for symmetry

</code>

TJG

 

[Jean-Michel Pichavant]

I have a list of items L, and a test function is_invalid that checks
the validity of each item. To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L, even though
the value returned by any() is fully determined by the first True
in its argument. In other words, all calls to is_invalid after
the first one to return True are superfluous. Is there a
short-circuiting counterpart to any(map(is_invalid, L)) that avoids
these superfluous calls?

OK, there's this one, of course:

def _any_invalid(L):
for i in L:
if is_invalid(i):
return True
return False

But is there anything built-in? (I imagine that a lazy version of
map *may* do the trick, *if* any() will let it be lazy.)

TIA!

~K

Sounds like unnecessary optimization. Just write

def _any_valid(L):
return bool([i for i in L if is_valid(i)])

If you really care about speed, meaning if the user experiences some
execution duration increase, then the solution you proposed is fine.


JM

 

[Tim Wintle]

I have a list of items L, and a test function is_invalid that checks
the validity of each item. To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L,

any( is_invalid(a) for a in L )

.... generator expression will be lazily computed.

Tim

 

[nn]

I have a list of items L, and a test function is_invalid that checks
the validity of each item. To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L, even though
the value returned by any() is fully determined by the first True
in its argument. In other words, all calls to is_invalid after
the first one to return True are superfluous. Is there a
short-circuiting counterpart to any(map(is_invalid, L)) that avoids
these superfluous calls?

OK, there's this one, of course:

def _any_invalid(L):
for i in L:
if is_invalid(i):
return True
return False

But is there anything built-in? (I imagine that a lazy version of
map *may* do the trick, *if* any() will let it be lazy.)

TIA!

~K

If you are in Python 3 "any(map(is_invalid, L))" should short circuit.
If you are in Python 2 use "from itertools import imap;
any(imap(is_invalid, L))"

 

[Raymond Hettinger]

I have a list of items L, and a test function is_invalid that checks
the validity of each item.  To check that there are no invalid
items in L, I could check the value of any(map(is_invalid, L)).
But this approach is suboptimal in the sense that, no matter what
L is, is_invalid will be executed for all elements of L, even though
the value returned by any() is fully determined by the first True
in its argument.  In other words, all calls to is_invalid after
the first one to return True are superfluous.  Is there a
short-circuiting counterpart to any(map(is_invalid, L)) that avoids
these superfluous calls?

OK, there's this one, of course:

def _any_invalid(L):
    for i in L:
        if is_invalid(i):
            return True
    return False  

But is there anything built-in?  (I imagine that a lazy version of
map *may* do the trick, *if* any() will let it be lazy.)

Yes, that will work:

from itertools import imap # lazy version of map
any(imap(is_invalid, L) # short-circuits on first True

Yet another approach (slightly faster):

from itertools import ifilter
any(ifilter(is_invalid, L))


Raymond

 

[kj]

If you are in Python 3 "any(map(is_invalid, L))" should short circuit.
If you are in Python 2 use "from itertools import imap;
any(imap(is_invalid, L))"

Thanks! I'm glad to know that one can get the short circuiting
using a map-type idiom. (I prefer map over comprehensions when I
don't need to define a function just for the purpose of passing it
to it.)

And thanks also to the other repliers for pointing out that the
comprehension version does what I was asking for.

~K

 

[Tim Golden]

Thanks! I'm glad to know that one can get the short circuiting
using a map-type idiom. (I prefer map over comprehensions when I
don't need to define a function just for the purpose of passing it
to it.)

In what way does "map" over "comprehensions" save you defining a function?

any (map (is_invalid, L))
any (is_invalid (i) for i in L)

TJG

 

[kj]

In what way does "map" over "comprehensions" save you defining a function?

any (map (is_invalid, L))
any (is_invalid (i) for i in L)

I was talking in the *general* case. map at the very least requires
a lambda expression, which is a one-time function defintion.

~K

 

[Steven D'Aprano]

In <[email protected]> Tim Golden




I was talking in the *general* case. map at the very least requires a
lambda expression, which is a one-time function defintion.

But keep in mind that instead of this:


map(lambda x,y: x+y, somelist)

you can do this:

import operator
map(operator.add, somelist)


In any case, the once-off cost of creating or importing a function is
usually quite cheap. As usual, the best advise is not to worry about
optimization until you have profiled the code and learned where the
actual bottlenecks are. Write what reads best, not what you guess might
be faster, until you really know you need the speed and that it is an
optimization and not a pessimation.

 

[kj]

In any case, the once-off cost of creating or importing a function is
usually quite cheap. As usual, the best advise is not to worry about
optimization until you have profiled the code and learned where the
actual bottlenecks are. Write what reads best, not what you guess might
be faster, until you really know you need the speed and that it is an
optimization and not a pessimation.

My preference for map in this case is not due to performance
considerations, but to avoid unnecessary code-clutter. I just
find, e.g.,

x = map(int, y)

slightly easier on the eyes than

x = [int(z) for z in y]

This tiny improvement in readability gets negated if one needs to
define a function in order to use map. Hence, e.g., I prefer

x = [_[0] for _ in y]

over

x = map(lambda _: _[0], y)

and certainly over

def _first(seq):
return seq[0]
x = map(_first, y)

Arguably, Knuth's "premature optimization is the root of all evil"
applies even to readability (e.g. "what's the point of making code
optimally readable if one is going to change it completely next
day?") If there were the equivalent of a profiler for code clutter,
I guess I could relax my readability standards a bit...

~K

 

[Jean-Michel Pichavant]

Arguably, Knuth's "premature optimization is the root of all evil"
applies even to readability (e.g. "what's the point of making code
optimally readable if one is going to change it completely next
day?")

The guy who will change it will have to read it. The only waste would be
if the code would never be read again.

If there were the equivalent of a profiler for code clutter,
I guess I could relax my readability standards a bit...

~K

Don't relax, just keep up )

JM