473,573 Members | 2,503 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

reduce() anomaly?

This seems like it ought to work, according to the
description of reduce(), but it doesn't. Is this
a bug, or am I missing something?

Python 2.3.2 (#1, Oct 20 2003, 01:04:35)
[GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-5)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.
d1 = {'a':1}
d2 = {'b':2}
d3 = {'c':3}
l = [d1, d2, d3]
d4 = reduce(lambda x, y: x.update(y), l) Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'update' d4 = reduce(lambda x, y: x.update(y), l, {})

Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 1, in <lambda>
AttributeError: 'NoneType' object has no attribute 'update'

- Steve.
Jul 18 '05
226 12380
Duncan Booth <du****@NOSPAMr cp.co.uk> wrote in message news:<Xn******* *************** *****@127.0.0.1 >...
which can be written more concisely without the lambda:

d = {}
map(d.update, l)


Although he shouldn't be using map at all for this case; he's not
using the resulting list.

Just a plan for loop will suffice:

for otherDict in l:
d.update(otherD ict)

Jeremy
Jul 18 '05 #11
Jeremy Fincher wrote:
Duncan Booth <du****@NOSPAMr cp.co.uk> wrote in message
news:<Xn******* *************** *****@127.0.0.1 >...
which can be written more concisely without the lambda:

d = {}
map(d.update, l)
Although he shouldn't be using map at all for this case; he's not
using the resulting list.


Absolutely true.

Just a plan for loop will suffice:

for otherDict in l:
d.update(otherD ict)


And if one needs to get top performance, an _almost_ plain for loop
will give performance just as good as map (rather than, say, 15% worse
or so -- not a worry in 99.999% of the cases, of course...):

d_upda = d.update
for otherDictin l:
d_upda(otherDic t)

[the usual case of "manual constant subexpression hoisting" where the
constant subexpression is the attribute lookup for d.update ...).
Alex

Jul 18 '05 #12
At 03:41 PM 11/5/2003, Francis Avila wrote:
"Alex Martelli" <al***@aleax.it > wrote in message
news:3f******* *************@n ews1.tin.it...
Stephen C. Waterbury wrote:
If you want to abuse reduce at all costs for this purpose,
reduce(lambda x, y: x.update(y) or x, l) might work.


Just out of curiosity, for what kind of problems do we find reduce to just
be the Right Way? I mean, summing a big list of numbers is fun and all, but
I never find any use for it otherwise. I *often* try to think if reduce
would be useful when I come across some collection-of-values manipulation
task, but usually one wants to repeat an operation on a whole set of values,
not reduce the set to one value.

So, are there any *non-trivial* and *unabusive* uses of reduce, where any
other way would be tedious, repetitive, slow, unclear, etc.? I'm very
curious to see them.


One's prior programming experience can affect one's view of reduce. My
favorite language, prior to Python, was APL. APL's native data container is
the array, and reduce is a native operator in APL. So we used reduce a lot,
sometimes to add things up, other times to check for all or any conditions,
other times for other at this moment forgotten purposes. A companion of
reduce in APL is scan, which did reduce but preserved all the intermediate
values (cumulative sum for example).

To expand your reduce horizons in Python, consider reduce as a way to
examine the relationship between successive pairs of a sequence. For
example one might wants the difference between successive elements: given
seq = [1,3,4,7] we'd like a differences == [2,1,3].

differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)

Bob Gailer
bg*****@alum.rp i.edu
303 442 2625
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.532 / Virus Database: 326 - Release Date: 10/27/2003

Jul 18 '05 #13
In article <ma************ *************** *********@pytho n.org>,
Bob Gailer <bg*****@alum.r pi.edu> wrote:
To expand your reduce horizons in Python, consider reduce as a way to
examine the relationship between successive pairs of a sequence. For
example one might wants the difference between successive elements: given
seq = [1,3,4,7] we'd like a differences == [2,1,3].

differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)


seq=[1,3,4,7]
[y-x for x,y in zip(seq,seq[1:])]

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #14
seq=[1,3,4,7]
map( int.__sub__, seq[1:], seq[:-1] ) # nearly twice faster than ....zip.... for long arrays

G-:

"David Eppstein" <ep******@ics.u ci.edu> wrote in message news:ep******** *************** *****@news.serv ice.uci.edu...
In article <ma************ *************** *********@pytho n.org>,
Bob Gailer <bg*****@alum.r pi.edu> wrote:

<...>
seq = [1,3,4,7] we'd like a differences == [2,1,3].

<...>

seq=[1,3,4,7]
[y-x for x,y in zip(seq,seq[1:])]

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science


Jul 18 '05 #15
Bob Gailer wrote:
...
One's prior programming experience can affect one's view of reduce. My
favorite language, prior to Python, was APL. APL's native data container
is the array, and reduce is a native operator in APL. So we used reduce a
I've done a _lot_ of APL and APL2 (albeit well before I met Python --
basically in the 1978-1988 time frame) and I don't think that "affects
my view of reduce" _in Python_ -- any more than (e.g.) having done a
lot of Scheme would affect my view of lambda and tail recursion _in
Python_, a lot of Icon that of generators, a lot of Perl that of RE's, ...

Basically, the old quip about "coding Fortran in any language" does not
apply to Fortran _only_: you can, up to a point, code (APL, Icon, Scheme,
Perl, ...) in any language... but it's _still_ basically a bad idea.

Mastering a language means (in part) mastering the idioms thereof --
what works well/smoothly/elegantly in that language, what most of that
language's best practitioners _do_. Knowledge of other languages --
the more the merrier -- can help, giving you perspective, but in the
end it shouldn't really affect your view of the target language.

The reduce method of Numeric's ufuncs _is_ a good, close analogy
for APL's reduce (more generally, APL concepts -- though not syntax --
do help a lot with Numeric, far more than they do with base Python).
Numeric.add.red uce(xs) IS a perfect equivalent to APL's +/xs -- if
xs is a Numeric.array (else the conversion overhead's gonna kill you:-):

$ timeit.py -c -s'import Numeric' -s'import operator' -s'xs=range(9999 )'
'reduce(operato r.add, xs)'
100 loops, best of 3: 2.9e+03 usec per loop
$ timeit.py -c -s'import Numeric' -s'import operator' -s'xs=range(9999 )'
'Numeric.add.re duce(xs)'
10 loops, best of 3: 2.2e+04 usec per loop
$ timeit.py -c -s'import Numeric' -s'import operator' -s'xs=range(9999 )'
'sum(xs)'
1000 loops, best of 3: 1.15e+03 usec per loop
$ timeit.py -c -s'import Numeric' -s'import operator' -s'xs=range(9999 )'
-s'xa=Numeric.ar ray(xs)' 'Numeric.add.re duce(xa)'
10000 loops, best of 3: 54 usec per loop

Yeah, I know, speed isn't everything. But when the speed of a perfectly
analogous operation drops by two times (from reduce to sum) or even
more when it drops by 50 times (from reduce on a list to Numeric.add.
reduce on a Numeric.array) one _does_ get a sense of when one's using
a language "reasonably idiomatically" -- within the design space of that
language, within the pathways most often taken by the language's best
practitioners and therefore most likely to be solid and optimized.

companion of reduce in APL is scan, which did reduce but preserved all the
intermediate values (cumulative sum for example).
Yep, that's e.g. Numeric.add.acc umulate in Numeric + Python.

To expand your reduce horizons in Python, consider reduce as a way to
examine the relationship between successive pairs of a sequence. For
example one might wants the difference between successive elements: given
seq = [1,3,4,7] we'd like a differences == [2,1,3].

differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)


def difs_reduce(seq ):
differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)
return differences

def difs_zip(seq):
return [ b-a for a, b in zip(seq,seq[1:]) ]

import itertools
def difs_izip(seq):
return [ b-a for a, b in itertools.izip( seq,seq[1:]) ]

def difs_loop(seq):
differences = []
it = iter(seq)
a = it.next()
for b in it:
differences.app end(b-a)
a = b
return differences

$ timeit.py -c -s'import a' -s'x=range(9999) ' 'a.difs_reduce( x)'
100 loops, best of 3: 1.8e+04 usec per loop
$ timeit.py -c -s'import a' -s'x=range(9999) ' 'a.difs_zip(x)'
100 loops, best of 3: 1.8e+04 usec per loop

so, the list comprehension with zip has just the same performance
as the clever use of reduce -- and is far more concise. But if
you're looking for speed, then the humble loop...:

timeit.py -c -s'import a' -s'x=range(9999) ' 'a.difs_loop(x) '
100 loops, best of 3: 9e+03 usec per loop

....is twice as fast! Simplicity isn't to be sneered at. And
if you're keep for higher-level reasoning and expression, itertools
is quite good for that:

timeit.py -c -s'import a' -s'x=range(9999) ' 'a.difs_izip(x) '
100 loops, best of 3: 7.6e+03 usec per loop

a one-liner, and another 15% speed boost wrt the humble loop.
[I can shave another 10% performance improvement with an
experimental 'w2' type I've coded to do specifically the
window-by-two job, but that small level of acceleration is
probably not enough to justify an extra type...;-)]
Yeah, I know, sigh, I come across as a micro-optimization freak,
which most definitely _ISN'T_ the point. I'm using speed and
concision as proxies for *idiomatic use* -- simplicity and
elegance and maintainability ... "elegance" &c we could argue about
forever, so I go for numbers that aren't quite as arguable:-).
I think reduce (like apply, filter, and probably map too) has had
its day but really doesn't have enough good use cases any more, in
this day and age of list comprehensions and iterator-tools, to
justify its existence as a Python built-in except for legacy reasons.
Alex

Jul 18 '05 #16
On Thu, 06 Nov 2003 21:57:33 -0800, David Eppstein <ep******@ics.u ci.edu> wrote:
In article <ma************ *************** *********@pytho n.org>,
Bob Gailer <bg*****@alum.r pi.edu> wrote:
To expand your reduce horizons in Python, consider reduce as a way to
examine the relationship between successive pairs of a sequence. For
example one might wants the difference between successive elements: given
seq = [1,3,4,7] we'd like a differences == [2,1,3].

differences = []
def neighborDiffere nce(left, right):
differences.app end(right - left)
return right
reduce(neighbor Difference, seq)
(IMO that's an ugly way to get a global result ;-).

seq=[1,3,4,7]
[y-x for x,y in zip(seq,seq[1:])]


The OP might like to see how generators make this sort of thing easy, e.g.,
def pairs(seq): ... itseq = iter(seq)
... earlier = itseq.next()
... for later in itseq:
... yield earlier, later
... earlier = later
... seq = [1,3,4,7]
Reincarnating your list comprehension, kind of:
[later-earlier for earlier,later in pairs(seq)] [2, 1, 3]

or factoring out the first difference ...
def diff1(seq): ... for earlier,later in pairs(seq): yield later-earlier
...

that becomes
[d for d in diff1(seq)] [2, 1, 3]

or perhaps better
list(diff1(seq) ) [2, 1, 3]

And then we can play with other kinds of sequences and first differences, e.g.,
linetext = """\ ... abc
... abx
... bx
... zax
... """ import sets
for d in diff1([sets.Set(line) for line in linetext.splitl ines()]): print d ...
Set(['x'])
Set([])
Set(['a', 'z'])

That was the first differences of:
for d in ([sets.Set(line) for line in linetext.splitl ines()]): print d

...
Set(['a', 'c', 'b'])
Set(['a', 'x', 'b'])
Set(['x', 'b'])
Set(['a', 'x', 'z'])

Regards,
Bengt Richter
Jul 18 '05 #17
Alex Martelli wrote:
Yeah, I know, speed isn't everything. But when the speed of a
perfectly
analogous operation drops by two times (from reduce to sum) or even
more when it drops by 50 times (from reduce on a list to Numeric.add.
reduce on a Numeric.array) one _does_ get a sense of when one's using
a language "reasonably idiomatically" -- within the design space of
that
language, within the pathways most often taken by the language's best
practitioners and therefore most likely to be solid and optimized.


But reduce isn't simply intended for adding up numbers. It's for doing
any kind of reduction.

Yes, I'm sure specific reductions based on summing are faster than using
reduce. But that goes without saying. Furthermore, Numeric is not
builtin to Python, so that seems a red herring to me. Either you should
compare builtins to builtins, or not.

--
Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
__ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
/ \ Every time a friend succeeds, I die a little.
\__/ Gore Vidal
Jul 18 '05 #18
Erik Max Francis wrote:
But reduce isn't simply intended for adding up numbers. It's for doing
any kind of reduction.
However, so many of reduce's practical use cases are eaten up by sum,
that reduce is left without real use cases to justify its existence.

If you consider the couple of uses left in the standard library, for
example... e.g., take cvs.py:

quotechar = reduce(lambda a, b, quotes = quotes:
(quotes[a] > quotes[b]) and a or b, quotes.keys())

....a masterpiece of clarity, right? The simple Python alternative,

quotechar = None
for k in quotes:
if not quotechar or quotes[k]>quotes[quotechar]:
quotechar = k

may be deemed boring, but then why not go for speed & concision with...:

quotechar = max([ (v,k) for k,v in quotes.iteritem s() ])[-1]

....?-) All 4 uses in csv.py are similar to this, and the one
in difflib.py:

matches = reduce(lambda sum, triple: sum + triple[-1],
self.get_matchi ng_blocks(), 0)

is clearly best expressed in Python 2.3 as:

matches = sum([ triple[-1] for triple in self.get_matchi ng_blocks() ])
The only other uses are in Lib/test/ -- and even there, apart from
tests of reduce itself, all are "reduce(add ..." [i.e., sum!] save
for *one*...:

def factorial(n):
return reduce(int.__mu l__, xrange(1, n), 1)

even in that one case (and apart from the confusing choice of having
factorial(n) return the factorial of n-1...), the most simplistic
implementation:

def fac(n):
result = 1
for i in xrange(2, n):
result *= n
return result

is only 3 times slower, and, if one is in a hurry, recursion and
memoization are obviously preferable:

def facto(n, _memo={1:1}):
try: return _memo[n]
except KeyError:
result = _memo[n] = (n-1) * facto(n-1)
return result

the performance numbers being:

[alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.factorial (13)'
100000 loops, best of 3: 10.3 usec per loop

[alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.fac(13)'
10000 loops, best of 3: 32 usec per loop

[alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.facto(13) '
1000000 loops, best of 3: 1.26 usec per loop

Yes, I'm sure specific reductions based on summing are faster than using
reduce. But that goes without saying. Furthermore, Numeric is not
builtin to Python, so that seems a red herring to me. Either you should
compare builtins to builtins, or not.


If you want APL-ish functionality with Python, Numeric is where you'll
find it (one day numarray, Numeric's successor, may finally gain entrance
into the standard library, but, don't hold your breath...).

But comparing plain Python code to a built-in that's almost bereft of
good use cases, and finding the plain Python code _faster_ on such a
regular basis, is IMHO perfectly legitimate. If a built-in gives me
obfuscated or slow code, where plain good old "let's code it out in
Python" gains clarity or speed, then it's time for that built-in to
go. 'reduce' exists for purely legacy reasons, and, IMHO, would count
as a wart were it not for Python's admirable determination to keep
old code running (however, even that determination can be overdone,
and I look forwards to the 3.0 release where old by-now-unwarranted
built-ins can be put out to pasture...).
Alex

Jul 18 '05 #19
JCM
Alex Martelli <al***@aleax.it > wrote:
....various good points...
if one is in a hurry, recursion and
memoization are obviously preferable: def facto(n, _memo={1:1}):
try: return _memo[n]
except KeyError:
result = _memo[n] = (n-1) * facto(n-1)
return result the performance numbers being: [alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.factorial (13)'
100000 loops, best of 3: 10.3 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.fac(13)'
10000 loops, best of 3: 32 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import facs' 'facs.facto(13) '
1000000 loops, best of 3: 1.26 usec per loop


I'm going off topic, but it's really not fair to compare a memoized
function to non-memoized implementations using a "best of 3" timing
test.
Jul 18 '05 #20

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

181
8721
by: Tom Anderson | last post by:
Comrades, During our current discussion of the fate of functional constructs in python, someone brought up Guido's bull on the matter: http://www.artima.com/weblogs/viewpost.jsp?thread=98196 He says he's going to dispose of map, filter, reduce and lambda. He's going to give us product, any and all, though, which is nice of him.
16
2162
by: clintonG | last post by:
At design-time the application just decides to go boom claiming it can't find a dll. This occurs sporadically. Doing a simple edit in the HTML for example and then viewing the application has caused the application to go boom. Sometimes the page will compile and run using F5 and others not. So I do the web search tango looking around the...
1
2788
by: mai | last post by:
Hi everyone, i'm trying to exhibit FIFO anomaly(page replacement algorithm),, I searched over 2000 random strings but i couldnt find any anomaly,, am i I doing it right?,, Please help,,,The following is the code,, #include <iostream> #include <string> #include <stdio.h> #include <stdlib.h> #include <ctime // For time()
7
3491
by: cnb | last post by:
This must be because of implementation right? Shouldn't reduce be faster since it iterates once over the list? doesnt sum first construct the list then sum it? ----------------------- reduce with named function: 37.9864357062 reduce with nested, named function: 39.4710288598 reduce with lambda: 39.2463927678 sum comprehension: ...
0
7983
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7735
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8035
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
1
5556
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5257
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3698
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3694
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2166
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
992
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.