for_some(), for_all()?

[aurora]

I am trying to test a list to see if some or all elements pass a test. For
example I can use reduce() to test if any element is 0.
[color=blue][color=green][color=darkred]
>>> lst = [1,2,0,3]
>>> test = lambda x: x == 0
>>> reduce(operator .__or__,[test(x) for x in lst])[/color][/color][/color]
True

However I bet reduce() does not exploit the short circuit logic. Also it
is a little clumsy to create another list to pass into reduce. Is there
some equivalent of

for_some(test, lst)
or
for_all(test, lst)?

[Larry Bates]

Re: for_some(), for_all()?

Use list comprehension and then test for what you want:

for_some

result=[x for x in lst if <insert your test here>]

if result:
#
# At least some of the items passed the test
#
else:
#
# None passed
#

for_all

result=[x for x in lst if <insert your test here>]

if len(result) == len(lst):
#
# All items passed the test
#
else:
#
# At least one didn't pass
#

I think it is easier to read and maintain.

Larry Bates





"aurora" <aurora00@gmail .com> wrote in message
news:opseqmpvg8 6yt6e7@news.cis co.com...[color=blue]
>I am trying to test a list to see if some or all elements pass a test. For
>example I can use reduce() to test if any element is 0.
>[color=green][color=darkred]
>>>> lst = [1,2,0,3]
>>>> test = lambda x: x == 0
>>>> reduce(operator .__or__,[test(x) for x in lst])[/color][/color]
> True
>
> However I bet reduce() does not exploit the short circuit logic. Also it
> is a little clumsy to create another list to pass into reduce. Is there
> some equivalent of
>
> for_some(test, lst)
> or
> for_all(test, lst)?
>
>[/color]

[Michael Hoffman]

Re: for_some(), for_all()?

aurora wrote:
[color=blue]
> However I bet reduce() does not exploit the short circuit logic. Also
> it is a little clumsy to create another list to pass into reduce. Is
> there some equivalent of
>
> for_some(test, lst)
> or
> for_all(test, lst)?[/color]

There are some recipes for any() and all() in the itertools documents
that do what you want:

http://www.python.org/doc/current/lib/itertools-example.html

[color=blue][color=green][color=darkred]
>>> import itertools, timeit, operator[/color][/color][/color]
[color=blue][color=green][color=darkred]
>>> def any(seq, pred=bool):[/color][/color][/color]
.... "Returns True if pred(x) is True at least one element in the
iterable"
.... return True in imap(pred, seq)
....[color=blue][color=green][color=darkred]
>>> def equals_0(x): return x == 0[/color][/color][/color]
....[color=blue][color=green][color=darkred]
>>> items = range(500000)[/color][/color][/color]
[color=blue][color=green][color=darkred]
>>> timeit.Timer("r educe(operator. __or__, [equals_0(x) for x in[/color][/color][/color]
items])", setup="from __main__ import operator, equals_0, items").timeit( 3)
4.1040000915527 344[color=blue][color=green][color=darkred]
>>> #timeit.Timer(" any(items, equals_0)", setup="from __main__ import[/color][/color][/color]
itertools, any, equals_0, items").timeit( 3)
....[color=blue][color=green][color=darkred]
>>> timeit.Timer("a ny(items, equals_0)", setup="from __main__ import[/color][/color][/color]
itertools, any, equals_0, items").timeit( 3) # short-circuit
0.0[color=blue][color=green][color=darkred]
>>> del items[0][/color][/color][/color]
[color=blue][color=green][color=darkred]
>>> timeit.Timer("a ny(items, equals_0)", setup="from __main__ import[/color][/color][/color]
itertools, any, equals_0, items").timeit( 3) # no short-circuit, still faster
1.6640000343322 754
--
Michael Hoffman

[Alex Martelli]

Re: for_some(), for_all()?

aurora <aurora00@gmail .com> wrote:
[color=blue]
> I am trying to test a list to see if some or all elements pass a test. For
> example I can use reduce() to test if any element is 0.
>[color=green][color=darkred]
> >>> lst = [1,2,0,3]
> >>> test = lambda x: x == 0
> >>> reduce(operator .__or__,[test(x) for x in lst])[/color][/color]
> True
>
> However I bet reduce() does not exploit the short circuit logic. Also it
> is a little clumsy to create another list to pass into reduce. Is there
> some equivalent of
>
> for_some(test, lst)
> or
> for_all(test, lst)?[/color]

Simplest:

def for_some(test, lst):
for item in lst:
if test(item): return True

def for_all(test, lst):
for item in lst:
if not test(item): return False
return True

You can play tricks, but you can't beat the simplicity of these, and
even with the cleverest tricks you can't beat their speed by much. And
simplicity is a great quality for software to have.


Alex

[Raymond Hettinger]

Re: for_some(), for_all()?

[Michael Hoffman][color=blue]
> There are some recipes for any() and all() in the itertools documents
> that do what you want:
>
> http://www.python.org/doc/current/li...s-example.html
>[color=green][color=darkred]
> >>> import itertools, timeit, operator[/color][/color]
>[color=green][color=darkred]
> >>> def any(seq, pred=bool):[/color][/color]
> ... "Returns True if pred(x) is True at least one element in the
> iterable"
> ... return True in imap(pred, seq)[/color]

I chose that one for the docs because it gave the best balance of clarity and
speed.

For pure speed, the following is faster and gives short-circuit behavior:
[color=blue][color=green][color=darkred]
>>> from itertools import ifilter
>>> def any(seq, pred=None):[/color][/color][/color]
.... for elem in ifilter(pred, seq):
.... return True
.... return False


Raymond Hettinger

[Michael Hoffman]

Re: for_some(), for_all()?

Raymond Hettinger wrote:
[color=blue]
> For pure speed, the following is faster and gives short-circuit behavior:
>[color=green][color=darkred]
>>>>from itertools import ifilter
>>>>def any(seq, pred=None):[/color][/color]
>
> ... for elem in ifilter(pred, seq):
> ... return True
> ... return False[/color]

Nice! I've always found the itertools examples exceptionally useful. Is
there a reason why they aren't in the standard library? I find myself
copying and pasting the snippets all the time.
--
Michael Hoffman

[Michele Simionato]

Re: for_some(), for_all()?

"Raymond Hettinger" <vze4rx4y@veriz on.net> wrote in message news:<2Pt4d.556 9$sa.1897@trndn y05>...[color=blue][color=green]
> >
> > http://www.python.org/doc/current/li...s-example.html
> >[color=darkred]
> > >>> import itertools, timeit, operator[/color][/color]
>[color=green][color=darkred]
> > >>> def any(seq, pred=bool):[/color]
> > ... "Returns True if pred(x) is True at least one element in the
> > iterable"
> > ... return True in imap(pred, seq)[/color]
>
> I chose that one for the docs because it gave the best balance of clarity and
> speed.
>[/color]

I always wondered why "any" and "all" are given as recipes but are not
part of the itertools module. What is the rationale?
I think they are so common that they deserve to be in the module.
At least, we would have standard names.


Michele Simionato

[Steven Bethard]

Re: for_some(),for_ all()?

Raymond Hettinger <vze4rx4y <at> verizon.net> writes:[color=blue]
> For pure speed, the following is faster and gives short-circuit behavior:
>[color=green][color=darkred]
> >>> from itertools import ifilter
> >>> def any(seq, pred=None):[/color][/color]
> ... for elem in ifilter(pred, seq):
> ... return True
> ... return False[/color]

So, the other one also has short-circuit behavior:
[color=blue][color=green][color=darkred]
>>> def any(seq, pred=bool):[/color][/color][/color]
.... return True in imap(pred, seq)
....[color=blue][color=green][color=darkred]
>>> def pred(x):[/color][/color][/color]
.... return x > 3
....[color=blue][color=green][color=darkred]
>>> i = iter(range(10))
>>> any(i, pred)[/color][/color][/color]
True[color=blue][color=green][color=darkred]
>>> list(i)[/color][/color][/color]
[5, 6, 7, 8, 9]

Could you explain what makes the second one faster? I'm guessing it's
something like that comparing True to each element in the iterable costs more
than binding each element in the iterable to elem...?

Thanks,

STeve

[Raymond Hettinger]

Re: for_some(), for_all()?

[Michael Hoffman][color=blue]
> Nice! I've always found the itertools examples exceptionally useful. Is
> there a reason why they aren't in the standard library? I find myself
> copying and pasting the snippets all the time.[/color]

[Michele Simionato][color=blue]
> I always wondered why "any" and "all" are given as recipes but are not
> part of the itertools module. What is the rationale?
> I think they are so common that they deserve to be in the module.
> At least, we would have standard names.[/color]


Random thoughts on itertools recipes and module design:

* The recipes are formatted to make it easy to paste the whole thing into a
module (it's already there for the taking).

* Adding more tools to the basic set makes the module itself harder to learn. I
theorize that the difficulty of creating a new composite tool grows
exponentially with the number of available fundamental building blocks.

* The recipes have as much value as a teaching tool as they do for practical
applications. Study the page of recipes and you've mastered itertools for life.

* Once in the standard library, the API is set in concrete. But as part of the
docs, I'm free to backport, improve variable names, improve function names,
substitute alternate approaches, and drop recipes that don't prove themselves in
battle.

* Publishing the recipes is a step toward standardizing the naming and
collecting best practices. IOW, we already get some of the benefits without
having to include the functions in the standard library.

* If included in the library, some of the functions would grow more complex.
For example, the pred=bool default needs to be followed by "if pred is bool:
pred=None" to take advantage of the ifilter's faster internal call to bool.

* Until now, there has been no popular demand. If the demand grows, I'll oblige
and include some of them in Py2.5. I prefer to be careful. Being conservative
about what goes in the module has contributed substantially to its success.

* Some derived tools like padnone() arise infrequently and are rarely the right
solution for a problem (not many functions respond well to a data stream where
one field suddenly starts yielding None). This function takes more than a
modicum of skill to use correctly. It is there to show how it is done and to
provide an iterator solution for folks relying on map()'s None fill-in feature.
IOW, it is not deserving of being in the standard library.

* Leaving the derived tools as recipes creates a sense that that more
combinations are open for invention. Putting them in the module suggests that
the problem is closed. This of course isn't strictly true, but it does affect
the mood.



Raymond Hettinger

[Raymond Hettinger]

Re: for_some(),for_ all()?

> > For pure speed, the following is faster and gives short-circuit behavior:[color=blue][color=green]
> >[color=darkred]
> > >>> from itertools import ifilter
> > >>> def any(seq, pred=None):[/color]
> > ... for elem in ifilter(pred, seq):
> > ... return True
> > ... return False[/color][/color]

[Steven Bethard][color=blue]
> So, the other one also has short-circuit behavior:[/color]

Right. It was the reduce(operator .__or__) version that didn't short-circuit.

[color=blue][color=green][color=darkred]
> >>> def any(seq, pred=bool):[/color][/color]
> ... return True in imap(pred, seq)
> ...[color=green][color=darkred]
> >>> def pred(x):[/color][/color]
> ... return x > 3
> ...[color=green][color=darkred]
> >>> i = iter(range(10))
> >>> any(i, pred)[/color][/color]
> True[color=green][color=darkred]
> >>> list(i)[/color][/color]
> [5, 6, 7, 8, 9]
>
> Could you explain what makes the second one faster? I'm guessing it's
> something like that comparing True to each element in the iterable costs more
> than binding each element in the iterable to elem...?[/color]

Close. The imap() version has two layers of iteration:

for elem in seq:
yield pred(elem)

for elem in imapresults:
if elem == True:
return True
return False

The ifilter() version has only one layer:

for elem in seq:
if pred(elem):
yield elem

Note, it make look like there is an outer layer in the ifilter() version, but
closer inspection shows that it never runs more than one iteration:

for elem in ifilterresults:
return True # because this returns, the for never loops back
return False



Raymond Hettinger

[Alex Martelli]

Re: for_some(), for_all()?

Raymond Hettinger <vze4rx4y@veriz on.net> wrote:
[color=blue]
> [Michele Simionato][color=green]
> > I always wondered why "any" and "all" are given as recipes but are not
> > part of the itertools module. What is the rationale?
> > I think they are so common that they deserve to be in the module.
> > At least, we would have standard names.[/color]
>
> Random thoughts on itertools recipes and module design:[/color]

[snipped lots of valuable considerations]

and one more, specific thing...: 'any' and 'all', like (say) other
potentially useful functions such as count, average, etc, are
_accumulators_ -- they _consume_ an iterator, producing a 'scalar'
result.

itertools is about filters and producers -- calling itertools.whate ver
_returns_ an iterator.

I'd like a small module of accumulators. But putting accumulators into
itertools is the wrong placing. A general rule that helps users
remember what-goes-where, such as 'itertools stuff returns iterators',
is too precious to throw away lightly, IMHO.


Alex