Opened 5 years ago
Closed 5 years ago
#19577 closed enhancement (fixed)
performance improvement of mutable poset used for univariate asymptotic expansions
Reported by: | dkrenn | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.1 |
Component: | asymptotic expansions | Keywords: | |
Cc: | behackl, cheuberg | Merged in: | |
Authors: | Daniel Krenn | Reviewers: | Clemens Heuberger |
Report Upstream: | N/A | Work issues: | |
Branch: | b2af8aa (Commits) | Commit: | b2af8aa130f6d386c6a163971f37dc4ba98e4bf6 |
Dependencies: | Stopgaps: |
Description (last modified by )
Reduce the evaluation time of the topological iterator.
As a result the time evaluating
k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)
(see #19306) dramatically decreases (see comment below for some timings).
Change History (7)
comment:1 Changed 5 years ago by
- Branch set to u/dkrenn/asy/speed-topo-iter
comment:2 Changed 5 years ago by
- Commit set to b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
- Status changed from new to needs_review
comment:3 Changed 5 years ago by
- Summary changed from performance improvment of mutable poset used for univariate asymptotic expansions to performance improvement of mutable poset used for univariate asymptotic expansions
comment:4 Changed 5 years ago by
- Description modified (diff)
comment:5 Changed 5 years ago by
Before this patch:
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/17601 for details. instance = typecall(cls, *args, **options) /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/rings/asymptotic/growth_group_cartesian.py:305: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/17601 for details. GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds) 1 loops, best of 1: 1.95 s per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 1.45 s per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 1.48 s per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 1.46 s per loop
After this patch:
sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/17601 for details. instance = typecall(cls, *args, **options) /local/dakrenn/sage/7.0/local/lib/python2.7/site-packages/sage/rings/asymptotic/growth_group_cartesian.py:305: FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation. See http://trac.sagemath.org/17601 for details. GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds) 1 loops, best of 1: 1.12 s per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 543 ms per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 546 ms per loop sage: %timeit -n 1 -r 1 k=4; S = asymptotic_expansions.Stirling('n', precision=5); n = S.parent().gen(); S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S) 1 loops, best of 1: 514 ms per loop
comment:6 Changed 5 years ago by
- Milestone changed from sage-6.10 to sage-7.1
- Reviewers set to Clemens Heuberger
- Status changed from needs_review to positive_review
I can reproduce the speed-up in this particular instance and I cannot imagine bad side effects.
comment:7 Changed 5 years ago by
- Branch changed from u/dkrenn/asy/speed-topo-iter to b2af8aa130f6d386c6a163971f37dc4ba98e4bf6
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
test whether sorting is needed in topological iteration