Python3: on removing map, reduce, filter

Discussion in 'Python' started by Andrey Tatarinov, Jan 9, 2005.

1. Andrey TatarinovGuest

Andrey Tatarinov, Jan 9, 2005

2. Paul RubinGuest

Andrey Tatarinov <> writes:
> How does GvR suggestions on removing map(), reduce(), filter()
> correlate with the following that he wrote himself (afaik):
>
> http://www.python.org/doc/essays/list2str.html

I think that article was written before list comprehensions were added
to Python.

Paul Rubin, Jan 9, 2005

3. Andrey TatarinovGuest

Paul Rubin wrote:
>>How does GvR suggestions on removing map(), reduce(), filter()
>>correlate with the following that he wrote himself (afaik):
>>http://www.python.org/doc/essays/list2str.html

>
> I think that article was written before list comprehensions were added
> to Python.

anyway list comprehensions are just syntaxic sugar for

>>> for var in list:
>>> smth = ...
>>> res.append(smth)

(is that correct?)

so there will be no speed gain, while map etc. are C-implemented

Andrey Tatarinov, Jan 9, 2005
4. Paul RubinGuest

Andrey Tatarinov <> writes:
> anyway list comprehensions are just syntaxic sugar for
> >>> for var in list:
> >>> smth = ...
> >>> res.append(smth)

>
> (is that correct?)

I would expect lc's to work more like map does.

Paul Rubin, Jan 9, 2005
5. Robert KernGuest

Andrey Tatarinov wrote:

> anyway list comprehensions are just syntaxic sugar for
>
> >>> for var in list:
> >>> smth = ...
> >>> res.append(smth)

>
> (is that correct?)
>
> so there will be no speed gain, while map etc. are C-implemented

It depends.

Try

def square(x):
return x*x
map(square, range(1000))

versus

[x*x for x in range(1000)]

Hint: function calls are expensive.

--
Robert Kern

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

Robert Kern, Jan 9, 2005
6. Steve HoldenGuest

Andrey Tatarinov wrote:

> Hi.
>
> How does GvR suggestions on removing map(), reduce(), filter() correlate
> with the following that he wrote himself (afaik):
>
> http://www.python.org/doc/essays/list2str.html
>
> ?

It promotes the sensible realization that when optimization is the goal
code may well tend to get ugly, sometimes uglier than necessary. Note
that the first version is completely straightforward and comprehensible.

And note that the summary in the conclusiogn BEGINS with "Rule number
one: only optimize when there is a proven speed bottleneck", which seems
to adequately imply that straightforward code is to be preferred unless
speed requirements override that.

regards
Steve
--
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/
Holden Web LLC +1 703 861 4237 +1 800 494 3119

Steve Holden, Jan 9, 2005
7. Andrey TatarinovGuest

Steve Holden wrote:
> Andrey Tatarinov wrote:
>
>> Hi.
>>
>> How does GvR suggestions on removing map(), reduce(), filter()
>> correlate with the following that he wrote himself (afaik):
>>
>> http://www.python.org/doc/essays/list2str.html

>
> And note that the summary in the conclusiogn BEGINS with "Rule number
> one: only optimize when there is a proven speed bottleneck", which seems
> to adequately imply that straightforward code is to be preferred unless
> speed requirements override that.

My main question was: "how could be this advices applied, when map,
reduce and filter would be removed?"

they need to be proved.

Andrey Tatarinov, Jan 9, 2005
8. Robert KernGuest

Andrey Tatarinov wrote:
> Steve Holden wrote:
>
>> Andrey Tatarinov wrote:
>>
>>> Hi.
>>>
>>> How does GvR suggestions on removing map(), reduce(), filter()
>>> correlate with the following that he wrote himself (afaik):
>>>
>>> http://www.python.org/doc/essays/list2str.html

>
> >

>
>> And note that the summary in the conclusiogn BEGINS with "Rule number
>> one: only optimize when there is a proven speed bottleneck", which
>> seems to adequately imply that straightforward code is to be preferred
>> unless speed requirements override that.

>
>
> My main question was: "how could be this advices applied, when map,
> reduce and filter would be removed?"

Since Python 3.0 is currently mythical and will involve a complete
rewrite of the language and interpreter, I don't think that you should
expect any optimization advice to carry over.

--
Robert Kern

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

Robert Kern, Jan 9, 2005
9. Steven BethardGuest

Robert Kern wrote:
> Andrey Tatarinov wrote:
>
>> anyway list comprehensions are just syntaxic sugar for
>>
>> >>> for var in list:
>> >>> smth = ...
>> >>> res.append(smth)

>>
>> (is that correct?)
>>
>> so there will be no speed gain, while map etc. are C-implemented

>
>
> It depends.
>
> Try
>
> def square(x):
> return x*x
> map(square, range(1000))
>
> versus
>
> [x*x for x in range(1000)]
>
> Hint: function calls are expensive.
>

Some timings to verify this:

\$ python -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
1000 loops, best of 3: 693 usec per loop

\$ python -m timeit -s "[x*x for x in range(1000)]"
10000000 loops, best of 3: 0.0505 usec per loop

Note that list comprehensions are also C-implemented, AFAIK.

Steve

Steven Bethard, Jan 9, 2005
10. John RothGuest

"Andrey Tatarinov" <> wrote in message
news:...
> Hi.
>
> How does GvR suggestions on removing map(), reduce(), filter() correlate
> with the following that he wrote himself (afaik):
>
> http://www.python.org/doc/essays/list2str.html

This is fairly old. Note that the fastest version
uses the array module, and is quite comprehensible -
if you know the array module and how it works.
It doesn't use the map function.

John Roth
>
> ?

John Roth, Jan 9, 2005
11. John MachinGuest

Steven Bethard wrote:
> Note that list comprehensions are also C-implemented, AFAIK.

Rather strange meaning attached to "C-implemented". The implementation
generates the code that would have been generated had you written out
the loop yourself, with a speed boost (compared with the fastest DIY
approach) from using a special-purpose opcode LIST_APPEND. See below.

>>> def afunc(n):

.... return [x*x for x in xrange(n)]
....
>>> afunc(3)

[0, 1, 4]
>>> import dis
>>> dis.dis(afunc)

2 0 BUILD_LIST 0
3 DUP_TOP
4 STORE_FAST 1 (_[1])
13 CALL_FUNCTION 1
16 GET_ITER
>> 17 FOR_ITER 17 (to 37)

20 STORE_FAST 2 (x)
32 BINARY_MULTIPLY
33 LIST_APPEND
34 JUMP_ABSOLUTE 17
>> 37 DELETE_FAST 1 (_[1])

40 RETURN_VALUE
>>> def bfunc(n):

.... blist=[]; blapp=blist.append
.... for x in xrange(n):
.... blapp(x*x)
.... return blist
....
>>> bfunc(3)

[0, 1, 4]
>>> dis.dis(bfunc)

2 0 BUILD_LIST 0
3 STORE_FAST 3 (blist)
12 STORE_FAST 2 (blapp)

3 15 SETUP_LOOP 34 (to 52)
24 CALL_FUNCTION 1
27 GET_ITER
>> 28 FOR_ITER 20 (to 51)

31 STORE_FAST 1 (x)

43 BINARY_MULTIPLY
44 CALL_FUNCTION 1
47 POP_TOP
48 JUMP_ABSOLUTE 28
>> 51 POP_BLOCK

5 >> 52 LOAD_FAST 3 (blist)
55 RETURN_VALUE
>>>

John Machin, Jan 9, 2005
12. Guest

Steve Holden wrote:
>> def square(x):
>> return x*x
>> map(square, range(1000))

>> versus

>> [x*x for x in range(1000)]

>> Hint: function calls are expensive.

>\$ python -m timeit -s "def square(x): return x*x" "map(square,

range(1000))"
>1000 loops, best of 3: 693 usec per loop

>\$ python -m timeit -s "[x*x for x in range(1000)]"
>10000000 loops, best of 3: 0.0505 usec per loop

Functions will often be complicated enought that inlining them is not
feasible. In Fortran 95 one can define an elemental function that takes
an argument of any shape (scalar, vector, matrix etc.) but of a
specified type, returning a result of the same shape, so that one could
write

elemental function square(i) result(isq)
integer, intent(in) :: i
integer :: isq
isq = i*i
end function square

and then

print*,square((/i,i=0,999/))

The Numeric and Numarray Python modules have predefined ufunc's that
are essentially elemental functions with one or two arguments. It would
be nice if one could define new ufunc's using only Python code -- I
presume new ones can currently be added by writing C code.

, Jan 10, 2005
13. Steve HoldenGuest

wrote:
> Steve Holden wrote:
>

No he didn't. I think you will find you are attributing Steven Bethard's

[...]
>
> The Numeric and Numarray Python modules have predefined ufunc's that
> are essentially elemental functions with one or two arguments. It would
> be nice if one could define new ufunc's using only Python code -- I
> presume new ones can currently be added by writing C code.
>

regards
Steve
--
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/
Holden Web LLC +1 703 861 4237 +1 800 494 3119

Steve Holden, Jan 10, 2005
14. Terry ReedyGuest

"Andrey Tatarinov" <> wrote in message
news:...
> How does GvR suggestions on removing map(), reduce(), filter()

While GvR *might* prefer removing them completely on any given day, I think
moving them to a functional module, as others have suggested and requested,
is currently more likely. I believe that GvR has indicated at times that
this would be an acceptible compromise.

I am one of those who think the list of builtins is currently too long to
be easily grasped and should be shrunk.

Terry J. Reedy

Terry Reedy, Jan 10, 2005
15. Steven BethardGuest

John Machin wrote:
> Steven Bethard wrote:
>> Note that list comprehensions are also C-implemented, AFAIK.

>
> Rather strange meaning attached to "C-implemented". The implementation
> generates the code that would have been generated had you written out
> the loop yourself, with a speed boost (compared with the fastest DIY
> approach) from using a special-purpose opcode LIST_APPEND. See below.

Fair enough.

So you basically replace the SETUP_LOOP, CALL_FUNCTION, POP_TOP and
POP_BLOCK with a DUP_TOP and a LIST_APPEND.

Steve

Steven Bethard, Jan 10, 2005
16. Steven BethardGuest

wrote:
> Steve Bethard wrote:
>> Robert Kern wrote:
>>> def square(x):
>>> return x*x
>>> map(square, range(1000))
>>>
>>> versus
>>> [x*x for x in range(1000)]
>>>
>>> Hint: function calls are expensive.

>>
>> \$ python -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
>> 1000 loops, best of 3: 693 usec per loop
>>
>> \$ python -m timeit -s "[x*x for x in range(1000)]"
>> 10000000 loops, best of 3: 0.0505 usec per loop

>
> Functions will often be complicated enought that inlining them is not
> feasible.

True, true. However, list comprehensions still seem to be comparable in
speed (at least in Python 2.4):

\$ python -m timeit -s "def f(x): return x*x" "[f(x) for x in xrange(1000)]"
1000 loops, best of 3: 686 usec per loop

\$ python -m timeit -s "def f(x): return x*x" "map(f, xrange(1000))"
1000 loops, best of 3: 690 usec per loop

Presumably this is because the C code for the byte codes generated by a
list comprehension isn't too far off of the C code in map. I looked at
bltinmodule.c for a bit, but I'm not ambitious enough to try verify this
hypothesis.

Steve

Steven Bethard, Jan 10, 2005
17. Nick CoghlanGuest

Terry Reedy wrote:
> "Andrey Tatarinov" <> wrote in message
> news:...
>
>>How does GvR suggestions on removing map(), reduce(), filter()

>
>
> While GvR *might* prefer removing them completely on any given day, I think
> moving them to a functional module, as others have suggested and requested,
> is currently more likely. I believe that GvR has indicated at times that
> this would be an acceptible compromise.
>
> I am one of those who think the list of builtins is currently too long to
> be easily grasped and should be shrunk.

Heh. When PEP 309 hits CVS (with functional.partial), maybe it can grow aliases
for the three of them so people can get used to the idea.

It might keep partial from getting too lonely. . .

Cheers,
Nick.

--
Nick Coghlan | | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

Nick Coghlan, Jan 10, 2005
18. David M. CookeGuest

Steven Bethard <> writes:
> Some timings to verify this:
>
> \$ python -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
> 1000 loops, best of 3: 693 usec per loop
>
> \$ python -m timeit -s "[x*x for x in range(1000)]"
> 10000000 loops, best of 3: 0.0505 usec per loop

Maybe you should compare apples with apples, instead of oranges
You're only running the list comprehension in the setup code...

\$ python2.4 -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
1000 loops, best of 3: 464 usec per loop
\$ python2.4 -m timeit "[x*x for x in range(1000)]"
1000 loops, best of 3: 216 usec per loop

So factor of 2, instead of 13700 ...

--
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)physics(dot)mcmaster(dot)ca

David M. Cooke, Jan 11, 2005
19. Steven BethardGuest

David M. Cooke wrote:
> Steven Bethard <> writes:
>
>>Some timings to verify this:
>>
>>\$ python -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
>>1000 loops, best of 3: 693 usec per loop
>>
>>\$ python -m timeit -s "[x*x for x in range(1000)]"
>>10000000 loops, best of 3: 0.0505 usec per loop

>
>
> Maybe you should compare apples with apples, instead of oranges
> You're only running the list comprehension in the setup code...
>
> \$ python2.4 -m timeit -s "def square(x): return x*x" "map(square, range(1000))"
> 1000 loops, best of 3: 464 usec per loop
> \$ python2.4 -m timeit "[x*x for x in range(1000)]"
> 1000 loops, best of 3: 216 usec per loop
>
> So factor of 2, instead of 13700 ...

Heh heh. Yeah, that'd be better. Sorry about that!

Steve

Steven Bethard, Jan 11, 2005