From 4fa9eb3e28a4b87be7c92b35cf7f77260c48329a Mon Sep 17 00:00:00 2001 From: Kirill Smelkov Date: Sun, 10 Aug 2008 11:50:39 +0400 Subject: [PATCH] Add: optimize collect of poly terms (2*x*y + 3*x*z) + general speedup MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The main speedup is achieved bu carefully not recreating Mul the dumb way, e.g. s = Mul(*o.args[1:]) but leveraging our knowledge of arguments nature and using ._new_rawargs() and Mul.as_two_terms() /which is now too converted to us ._new_rawargs()/ in performance critical points, e.g. if o.is_Mul: ... # o=3*x*y -- this will call ._new_rawargs(*o.args[1:]) behind the scene # o= x*y -- this will just return y s = o.as_two_terms()[1] Also, general cleanup/speedup is done: - we don't do seq.pop(0) anymore (this is slow), instead we just iterate over seq - we don't do terms.has_key(s) -- this is slower than "s in terms" Timings (cache: off) -------------------- d = [2*x*y, 3*x*y] q = [2*x*y, 3*x*z] p = [x, 3, y] Add(*d) Add(*q) (x+y+z+1)**40 Add(*p) fem_test.py .expand() old: 922 µs 1200 µs 27.8 s 173 µs 5.72 s new: 325 µs 354 µs 13.7 s 160 µs 5.35 s speedup: 2.83x 3.39x 2.03x 8% 7% Signed-off-by: Kirill Smelkov Signed-off-by: Ondrej Certik Signed-off-by: Riccardo Gori --- sympy/core/add.py | 29 ++++++++++++++++++++--------- sympy/core/mul.py | 10 ++++++++-- 2 files changed, 28 insertions(+), 11 deletions(-) diff --git a/sympy/core/add.py b/sympy/core/add.py index b03e266..fa89aae 100644 --- a/sympy/core/add.py +++ b/sympy/core/add.py @@ -30,8 +30,8 @@ class Add(AssocOp): coeff = S.Zero # standalone term # e.g. 3 + ... order_factors = [] - while seq: - o = seq.pop(0) + + for o in seq: # O(x) if o.is_Order: @@ -45,17 +45,18 @@ class Add(AssocOp): continue # 3 - if o.is_Number: + elif o.is_Number: coeff += o continue # Add([...]) - if o.is_Add: - seq = list(o.args) + seq + elif o.is_Add: + # NB: here we assume Add is always commutative + seq.extend(o.args) # TODO zerocopy? continue # Mul([...]) - if o.is_Mul: + elif o.is_Mul: c = o.args[0] # 3*... @@ -63,7 +64,8 @@ class Add(AssocOp): if c is S.One: s = o else: - s = Mul(*o.args[1:]) + s = o.as_two_terms()[1] + else: c = S.One s = o @@ -82,7 +84,7 @@ class Add(AssocOp): # let's collect terms with the same s, so e.g. # 2*x**2 + 3*x**2 -> 5*x**2 - if terms.has_key(s): + if s in terms: terms[s] += c else: terms[s] = c @@ -101,7 +103,16 @@ class Add(AssocOp): newseq.append(s) # c*s else: - newseq.append(Mul(c,s)) + if s.is_Mul: + # Mul, already keeps it's arguments in perfect order. + # so we can simply put c in slot0 and go the fast way. + cs = s._new_rawargs(*((c,) + s.args)) + newseq.append(cs) + + else: + # alternatively we have to call all Mul's machinery (slow) + newseq.append(Mul(c,s)) + noncommutative = noncommutative or not s.is_commutative # nan diff --git a/sympy/core/mul.py b/sympy/core/mul.py index d1c0202..6c17614 100644 --- a/sympy/core/mul.py +++ b/sympy/core/mul.py @@ -291,9 +291,15 @@ class Mul(AssocOp): @cacheit def as_two_terms(self): - if len(self.args) == 1: + args = self.args + + if len(args) == 1: return S.One, self - return self.args[0], Mul(*self.args[1:]) + elif len(args) == 2: + return args + + else: + return args[0], self._new_rawargs(*args[1:]) @cacheit def as_coeff_terms(self, x=None): -- 2.11.4.GIT