Tim Peters <t...@python.org> added the comment:
Too abstract for me to find compelling. I suspect the title of this report
referenced "math.prod with bignums" because it's the only actual concrete use
case you had ;-)
Here's another: math.lcm. That can benefit for the same reason as math.prod -
provoking Karatsuba multiplication. However, applying lcm to a largish
collection of ints is so rare I can't recall ever seeing it done.
Here's a related anti-example: math.gcd. Tree reduction hurts that. It
typically falls to 1 quickly, and tree reduction just delays that.
So I'm at best -0 on this, and I'll stop now.
For reference, here's a Python implementation that strives to match
functools.reduce's signature and endcase behaviors. It accepts any iterable,
and requires temp space at most about log2(number of elements the iterable
delivers in all).
That memory frugality adds a log2 factor to the runtime. The O() speed penalty
could be eliminated by using temp memory that grows to about half the number of
elements in the iterable.
def treereduce(function, iterable, initializer=None):
levels = []
if initializer is not None:
levels.append(initializer)
NULL = object()
for y in iterable:
for i, x in enumerate(levels):
if x is NULL:
levels[i] = y
break
y = function(x, y)
levels[i] = NULL
else:
levels.append(y)
y = NULL
for x in levels:
if x is not NULL:
y = x if y is NULL else function(x, y)
if y is NULL:
raise TypeError("treereduce() of empty iterable with no initial
value")
return y
Then, for example,
>>> treereduce(lambda x, y: f"({x}+{y})", "abcdefghijk")
'((((a+b)+(c+d))+((e+f)+(g+h)))+((i+j)+k))'
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue46868>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
