Comment #32 on issue 2607 by asmeurer: as_numer_denom() is too slow
http://code.google.com/p/sympy/issues/detail?id=2607
(those benchmarks are done with cache off, so maybe this is the
difference?).
Ah, that's it. Here's what I get with the cache off:
In [1]: numers, denoms = zip(*((Symbol('n%d'%i),Symbol('d%d'%i)) for i in
xrange(1000)))
In [2]: a = Add(*(n/d for n, d in zip(numers, denoms)))
In [3]: %timeit together(a)
1 loops, best of 3: 185 s per loop
In [4]: %timeit a.as_numer_denom4()
1 loops, best of 3: 182 s per loopIn [1]: numers, denoms =
zip(*((Symbol('n%d'%i),Symbol('d%d'%i)) for i in xrange(1000)))
In [2]: a = Add(*(n/d for n, d in zip(numers, denoms)))
In [3]: %timeit together(a)
1 loops, best of 3: 185 s per loop
In [4]: %timeit a.as_numer_denom4()
1 loops, best of 3: 182 s per loop
This just illuminates something I've noticed here, which is that we are not
really testing algorithms for their own sake, but against the current
implementation of things like Mul.flatten. For example, as_numer_denom1()
is so slow because *= is slow in SymPy (I guess it's quadratic, as it
recomputes Mul.flatten each time, which makes as_numer_denom1() worse than
as_numer_denom_orig()).
Therefore, I think we maybe shouldn't ignore that enormous speedup that the
cache gives us for as_numer_denom4(). Perhaps as we optimize Mul.flatten
and others in different ways, other options will become faster, but we
should reconsider this when that heppens.
But the fact is, when the cache is on (as it usually is), as_numer_denom4()
is very fast and together() is slow, And when it's off, they are both
about the same.
together() computes structural lcm of denominators (not algebraic as
lcm() does). This guarantees that the resulting denominator is minimal
with respect to the structure of the input (as I said before). It also
removes numerical contents.
So far, none of the as_numer_denom options do this, but I think they should
(see comments 22 and 24), because this kind of preprocessing would be very
fast and would result in smaller answers (ultimately making the whole thing
faster). As for numerical factors, we would have to have to handle this
anyway in as_numer_denom4 because of the issue noted in 20.
3) make as_numer_denom() call together() and return (numer, denom)
without any further computations.
I disagree. The computation should happen in as_numer_denom() and
together() should call that. See the last paragraph in comment 28. It
doesn't make sense for together to compute the numerator and denominator,
put them together, and then have as_numer_denom pull them apart again.
This sort of putting things together and pull them apart again has led to
wrong results with as_real_imag and expand(complex=True) (I again refer you
to issue 1985). I could easily see this happening here too.
--
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.
