Python3: on removing map, reduce, filter

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

  1. Andrey Tatarinov, Jan 9, 2005
    #1
    1. Advertising

  2. Andrey Tatarinov

    Paul Rubin Guest

    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
    #2
    1. Advertising

  3. 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
    #3
  4. Andrey Tatarinov

    Paul Rubin Guest

    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
    #4
  5. Andrey Tatarinov

    Robert Kern Guest

    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
    #5
  6. Andrey Tatarinov

    Steve Holden Guest

    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
    #6
  7. 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?"

    but earlier I got answers about speed of list comprehensions, though
    they need to be proved.
     
    Andrey Tatarinov, Jan 9, 2005
    #7
  8. Andrey Tatarinov

    Robert Kern Guest

    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
    #8
  9. 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
    #9
  10. Andrey Tatarinov

    John Roth Guest

    "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
    #10
  11. Andrey Tatarinov

    John Machin Guest

    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])
    7 LOAD_GLOBAL 1 (xrange)
    10 LOAD_FAST 0 (n)
    13 CALL_FUNCTION 1
    16 GET_ITER
    >> 17 FOR_ITER 17 (to 37)

    20 STORE_FAST 2 (x)
    23 LOAD_FAST 1 (_[1])
    26 LOAD_FAST 2 (x)
    29 LOAD_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)
    6 LOAD_FAST 3 (blist)
    9 LOAD_ATTR 1 (append)
    12 STORE_FAST 2 (blapp)

    3 15 SETUP_LOOP 34 (to 52)
    18 LOAD_GLOBAL 3 (xrange)
    21 LOAD_FAST 0 (n)
    24 CALL_FUNCTION 1
    27 GET_ITER
    >> 28 FOR_ITER 20 (to 51)

    31 STORE_FAST 1 (x)

    4 34 LOAD_FAST 2 (blapp)
    37 LOAD_FAST 1 (x)
    40 LOAD_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
    #11
  12. Andrey Tatarinov

    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
    #12
  13. Andrey Tatarinov

    Steve Holden Guest

    wrote:
    > Steve Holden wrote:
    >

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

    [...]
    >
    > 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
    #13
  14. Andrey Tatarinov

    Terry Reedy Guest

    "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
    #14
  15. 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
    #15
  16. 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
    #16
  17. Andrey Tatarinov

    Nick Coghlan Guest

    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
    #17
  18. 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
    #18
  19. 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
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ben

    map, filter & reduce...

    Ben, Nov 16, 2003, in forum: Python
    Replies:
    4
    Views:
    422
    Inyeol Lee
    Nov 20, 2003
  2. Tom Anderson
    Replies:
    186
    Views:
    2,603
    Terry Reedy
    Jul 9, 2005
  3. Jp Calderone
    Replies:
    1
    Views:
    287
    Scott David Daniels
    Jul 3, 2005
  4. Raymond Hettinger
    Replies:
    3
    Views:
    227
    Raymond Hettinger
    Apr 26, 2011
  5. Andrew Berg
    Replies:
    0
    Views:
    337
    Andrew Berg
    Jun 16, 2012
Loading...

Share This Page