Message414219
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))' |
|
Date |
User |
Action |
Args |
2022-02-28 19:47:31 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson, benrg |
2022-02-28 19:47:30 | tim.peters | set | messageid: <1646077650.96.0.738076407872.issue46868@roundup.psfhosted.org> |
2022-02-28 19:47:30 | tim.peters | link | issue46868 messages |
2022-02-28 19:47:30 | tim.peters | create | |
|