Adding a Par construct to Python?

Terry Reedy tjreedy at
Fri Jun 5 17:38:19 EDT 2009

Lawrence D'Oliveiro wrote:
> In message <77as23F1fhj3uU1 at>, Diez B. Roggisch wrote:
>>> But reduce()? I can't see how you can parallelize reduce(). By its
>>> nature, it has to run sequentially: it can't operate on the nth item
>>> until it is operated on the (n-1)th item.
>> That depends on the operation in question. Addition for example would
>> work. My math-skills are a bit too rusty to qualify the exact nature of
>> the operation, commutativity springs to my mind.
> Associativity:
>     ((A op B) op C) = (A op (B op C))
> So for example
>    A op B op C op D
> could be grouped into
>   (A op B) op (C op D)
> and the two parenthesized subexpressions evaluated concurrently. But this 
> would only give you a speedup that was logarithmic in the number of op's.

It is worth noting, I think, that many realistic operations are not 
associative.  If op combines a summary and an item to create an updated 
summary, it will probably croak or give a wrong answer when given a 
summary and a summary.  Combining two summaries might be possible, but 
would be a different operation.

For a specific example, consider list.append(some_list, some_item) 
versus list.extend(some_list, another_list).  Imagine for that moment 
that these methods returned some_list.  Then

[].append(a).append(b).append(c).append(d) # parentheses left out

would have to be conceptually converted to the associative


before being grouped something like


Of course, one would not do the conversion to the slower associative 
operation unless one knew that there would be a compensating speedup due 
to the grouping.

Terry Jan Reedy

More information about the Python-list mailing list