Comment #27 on issue 683 by [email protected]: speedup of sum(x**i/i,i=1..400)
http://code.google.com/p/sympy/issues/detail?id=683
The algorithm is almost the same (the mathematics). However, some technical details are different. First of all, terms are stored in a dictionary. There is no sorting by default and args are computed lazily when needed. For trivial cases, like Add(...) + c, flatten() uses zero-copy techniques (which I will further optimize).
We always say that it's more efficient to use Add(*args) than any other construct. That's wrong and I try to prove it wrong in this branch. Even using _new_rawargs() is wrong most of the time. Add(*args) is efficient only when there is no relationship between elements of args. But in most cases there is some. For example in the case Add(*args) + c, currently what we do is more or less Add(*(args + (c,))), which means that we lose all information Add.flatten() collected (using a lot of computing time) for Add(*args). In my branch all information is preserved, so Add(*args) + c has O(1) complexity.
Unfortunately, this branch makes only this particular case much faster, but in general tests run about 5% slower. This is because Add uses currently a mixture of old and new approaches, which makes some old speed improvements tricks less effective. To overcome this, I will slowly transition to the new approach only and then we should see general speed improvements. By this transition I mean avoiding a = Add(*args); b = Add(*a.args) and replacing this with dedicated efficient Add's API, which will all us to do most common operations on Add without need for computing args (which is slow, because you have to sort and even sorting by hash is extremely slow).
I started with Add, but the same has to be done with Mul. Just Add case is much simpler to experiment with, because Add.flatten() is much simpler than Mul.flatten() and you don't have to deal so much with non-commutative objects.
-- 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.
