Comment #15 on issue 2607 by asmeurer: as_numer_denom() is too slow
http://code.google.com/p/sympy/issues/detail?id=2607
Here's what I've got so far:
def as_numer_denom(self):
return self.as_numer_denom_orig()
def as_numer_denom_orig(self):
numers, denoms = [],[]
for n,d in [f.as_numer_denom() for f in self.args]:
numers.append(n)
denoms.append(d)
r = xrange(len(numers))
return Add(*[Mul(*(denoms[:i]+[numers[i]]+denoms[i+1:]))
for i in r]), Mul(*denoms)
def as_numer_denom1(self):
"""
Combine pairwise.
"""
numers, denoms = zip(*[f.as_numer_denom() for f in self.args])
num = [numers[0]]
dom = denoms[0]
for n, d in zip(numers[1:], denoms[1:]):
for i in xrange(len(num)):
num[i] *= d
num.append(n*dom)
dom *= d
return Add(*num), dom
def as_numer_denom2(self):
"""
Combine pariwise; don't Mul until the end.
"""
numers, denoms = zip(*[f.as_numer_denom() for f in self.args])
num = [[numers[0]]]
dom = [denoms[0]]
for n, d in zip(numers[1:], denoms[1:]):
for i in xrange(len(num)):
num[i].append(d)
num.append([n] + dom)
dom.append(d)
return Add(*(Mul(*n) for n in num)), Mul(*dom)
def as_numer_denom3(self):
"""
Combine pairwise; don't distribute the denominator.
"""
numers, denoms = zip(*[f.as_numer_denom() for f in self.args])
num = numers[0]
dom = denoms[0]
for n, d in zip(numers[1:], denoms[1:]):
num *= d
num += n*dom
dom *= d
return num, dom
as_numer_denom() is the current implementation and as_numer_denom3() does
what I suggested in comment 14.
This is super fast for the expression I gave above where the denominators
are all just 1, but it's slow for actual expressions.
This seems to be wrong. It's slower for smaller expressions, but it must be
asymptotically faster, because it's way faster for large expressions. For
example:
In [9]: numers, denoms = zip(*((Symbol('n%d'%i),Symbol('d%d'%i)) for i in
xrange(10)))
In [10]: a = Add(*(n/d for n, d in zip(numers, denoms)))
In [11]: a.as_numer_denom3()
Out[11]:
(d₀⋅d₁⋅d₂⋅d₃⋅d₄⋅d₅⋅d₆⋅d₇⋅d₈⋅n₉ + d₉⋅(d₀⋅(d₁⋅d₂⋅d₃⋅d₅⋅d₆⋅d₇⋅d₈⋅n₄ +
d₄⋅(d₁⋅d₂⋅d₃⋅d₆⋅d₇⋅d₈⋅n₅ + d₅⋅(d₁⋅d₂⋅d₃⋅d₇⋅d₈⋅n₆ + d₆⋅(d₁⋅d₃⋅d₇⋅d₈⋅n₂ +
d₂⋅(d₁⋅d₃⋅d₇⋅n₈ + d₈⋅(d₁⋅d₇⋅n₃ + d₃⋅(d₁⋅
n₇ + d₇⋅n₁))))))) + d₁⋅d₂⋅d₃⋅d₄⋅d₅⋅d₆⋅d₇⋅d₈⋅n₀),
d₀⋅d₁⋅d₂⋅d₃⋅d₄⋅d₅⋅d₆⋅d₇⋅d₈⋅d₉)
In [12]: %timeit a.as_numer_denom()
1000 loops, best of 3: 939 us per loop
In [13]: %timeit a.as_numer_denom1()
100 loops, best of 3: 1.39 ms per loop
In [14]: %timeit a.as_numer_denom2()
1000 loops, best of 3: 2.27 ms per loop
In [15]: %timeit a.as_numer_denom3()
100 loops, best of 3: 2.19 ms per loop
In [16]: numers, denoms = zip(*((Symbol('n%d'%i),Symbol('d%d'%i)) for i in
xrange(1000)))
In [17]: a = Add(*(n/d for n, d in zip(numers, denoms)))
In [18]: %timeit a.as_numer_denom()
1 loops, best of 3: 5.79 s per loop
In [19]: %timeit a.as_numer_denom1()
(oo; I had to interrupt it after a long time)
In [20]: %timeit a.as_numer_denom2()
1 loops, best of 3: 6 s per loop
In [21]: %timeit a.as_numer_denom3()
1 loops, best of 3: 121 ms per loop
I'm hoping I can discover a fast way to created unnested expressions, as
the expressions like the one in Out[11] are far slower when used by other
things (like the printer for example). I might say to call expand on it,
if expand weren't so slow also. Also, being highly nested, they tend to
create "recursion depth exceeded" errors (e.g., try printing the output of
[21]; indeed, I can't even figure out how to expand it without getting that
error).
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy-issues?hl=en.
