Comment #2 on issue 1883 by asmeurer: Recode dmp_zero_p to be non-recursive
http://code.google.com/p/sympy/issues/detail?id=1883
Looking closer at the file, I saw several other functions that were written
recursively, but were easy to convert
into non-recursive equivalents. In particular, dmp_zero, dmp_ground, and
dmp_nest were all easy to convert.
Other recursive ones that I did not change were dmp_from_dict, dmp_raise,
dmp_apply_pairs because I
couldn't figure out how to do it. If you are clever enough to convert
them, I am sure they will be faster, but I
am not right now.
Here is the full scoop. The non-recursive versions run 2-3 times faster
than their recursive variants (not to
mention the fact that they are maximum recursion error proof):
== dmp_zero ==
In [1]: from sympy.polys.densebasic import dmp_zero
In [2]: dmp_zero(4)
Out[2]: [[[[[]]]]]
In [3]: dmp_zero(0)
Out[3]: []
In [5]: def non_rec_dmp_zero(u):
...: r = []
...: for i in xrange(u):
...: r = [r]
...:
...: return r
...:
In [6]: non_rec_dmp_zero(4)
Out[6]: [[[[[]]]]]
In [8]: non_rec_dmp_zero(0)
Out[8]: []
In [9]: %timeit dmp_zero(100)
10000 loops, best of 3: 85.9 us per loop
In [10]: %timeit non_rec_dmp_zero(100)
10000 loops, best of 3: 58 us per loop
== dmp_ground==
In [2]: from sympy.polys.densebasic import dmp_ground
In [4]: from sympy.polys.densebasic import dmp_zero
In [11]: def non_rec_dmp_ground(c, u):
if not c:
return dmp_zero(u)
for i in xrange(u + 1):
c = [c]
return c
....:
In [17]: dmp_ground(1, 2)
Out[17]: [[[1]]]
In [18]: non_rec_dmp_ground(1, 2)
Out[18]: [[[1]]]
In [19]: dmp_ground(1, -2)
Out[19]: 1
In [20]: non_rec_dmp_ground(1, -2)
Out[20]: 1
In [21]: non_rec_dmp_ground(1, 0)
Out[21]: [1]
In [22]: dmp_ground(1, 0)
Out[22]: [1]
In [23]: %timeit dmp_ground(2, 100)
10000 loops, best of 3: 75.8 us per loop
In [24]: %timeit non_rec_dmp_ground(2, 100)
10000 loops, best of 3: 35.4 us per loop
== dmp_nest ==
In [13]: dmp_nest(1, 2, ZZ)
Out[13]: [[[1]]]
In [14]: dmp_nest([1], 2, ZZ)
Out[14]: [[[1]]]
In [15]: dmp_nest([1, 2], 2, ZZ)
Out[15]: [[[1, 2]]]
In [23]: def non_rec_dmp_nest(f, l, K):
if not isinstance(f, list):
return dmp_ground(f, l)
for i in xrange(l):
f = [f]
return f
....:
In [15]: non_rec_dmp_nest(1, 2, ZZ)
Out[15]: [[[1]]]
In [21]: non_rec_dmp_nest([1], 2, ZZ)
Out[21]: [[[1]]]
In [22]: non_rec_dmp_nest([1, 2], 2, ZZ)
Out[22]: [[[1, 2]]]
In [13]: %timeit dmp_nest([1, 2, 3], 100, ZZ)
10000 loops, best of 3: 103 us per loop
In [14]: %timeit non_rec_dmp_nest([1, 2, 3], 100, ZZ)
10000 loops, best of 3: 37.6 us per loop
By the way, isinstance(i, list) is slightly faster than type(i) is list
(which was used in the old recursive function),
and recommended over it in PEP 8:
In [1]: i = range(100)
In [2]: %timeit isinstance(i, list)
1000000 loops, best of 3: 405 ns per loop
In [3]: %timeit type(i) is list
1000000 loops, best of 3: 686 ns per loop
I have pushed this up to the same branch.
Unrelated questions:
- I noticed that many of the functions take K as an argument but don't use
it. Is there a reason for this? I
didn't want to go through and change the API without being sure that there
isn't some magic or something
going on here. An example of such a function is dmp_nest().
In parallel with root isolation and RootOf I'm working on more efficient
polynomial
representation, mainly dictionary based sparse distributed polynomials
with optional
ordering for computing degrees, LC, etc.
- Does this mean that the API for this file is unstable, or will that be
going in some separate sparcebasic.py
file? Otherwise, I would like to write doctests for the functions in
densebasic.py, as it would have made things
a little easier for me in doing this to have them :).
Also, to clarify on comment 0, technically that integral doesn't
spend "most" of the time in dmp_zero_p, it just
spends more time there than in any other function. Run the cProfile to see
what I mean.
--
You received this message because you are listed in the owner
or CC fields of this issue, or because you starred this issue.
You may adjust your issue notification preferences at:
http://code.google.com/hosting/settings
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To post to this group, send email to sympy-iss...@googlegroups.com.
To unsubscribe from this group, send email to
sympy-issues+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sympy-issues?hl=en.
