#16453: Cythonize quiver paths
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Fix issue in bounded
Branch: | integer sequences
u/SimonKing/cythonize_quiver_paths | Commit:
Dependencies: #15820 | 73ac68974379d51ff7a4a22aed7539b480668be8
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
In my applications, I will likely use paths as dictionary keys, I will
multiply them, I will (for two-sided modules) test subpath containment or
(for right modules) detect initial segments, and I will extract sub-paths.
The following benchmark may thus be representative for what is needed for
two-sided modules:
{{{
sage: def test1(p1,p2):
....: D = {}
....: for i in range(1,100):
....: D[p2^i*p1*p2^i] = i
....: q = p2^10*p1*p2^50
....: for x in D.keys():
....: assert x.has_subpath(q) or D[x] < 50
....: q = p2*p1*p2^120
....: for x in D.keys():
....: assert q.has_initial_segment(x[(D[x]-1)*len(p2):])
....:
}}}
Let's apply this to the dense encoding:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test1(p1,p2)
1 loops, best of 3: 420 ms per loop
}}}
And for the non-dense encoding:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup(False)
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test1(p1,p2)
100 loops, best of 3: 4.26 ms per loop
}}}
The following benchmark hopefully addresses the tasks that are important
in the case of right modules:
{{{
sage: def test2(p1,p2):
....: D = {}
....: for i in range(1,100):
....: D[p2^i*p1*p2^i] = i
....: q = p2^10*p1*p2^50
....: for x in D.keys():
....: assert D[x]<10 or
(x[(D[x]-10)*len(p2):].has_initial_segment(q) or D[x]<50)
....:
}}}
In the dense encoding:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test2(p1,p2)
1 loops, best of 3: 306 ms per loop
}}}
Versus the non-dense:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup(False)
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test2(p1,p2)
100 loops, best of 3: 3.99 ms per loop
}}}
The last benchmark shows that I should certainly avoid computing overlap
(gcd) in the dense encoding:
{{{
sage: def test3(p1,p2):
....: D = {}
....: for i in range(1,100):
....: D[p2^i*p1*p2^i] = i
....: q = p2^10*p1*p2^50
....: for x in D.keys():
....: assert D[x]<10 or
(x[(D[x]-10)*len(p2):].has_initial_segment(q) or D[x]<50)
....: q = p2*p1*p2^120
....: for x in D.keys():
....: assert all(q.gcd(x))
....:
}}}
The dense encoding:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test3(p1,p2)
1 loops, best of 3: 1.44 s per loop
}}}
The non-dense encoding:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup(False)
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test3(p1,p2)
100 loops, best of 3: 9.31 ms per loop
}}}
Looks like the non-dense encoding beats the dense encoding in all tests.
However, in the following test, the dense encoding is slightly faster:
{{{
sage: def test4(p1,p2):
....: D = {}
....: for i in range(1,100):
....: D[p2^i*p1*p2^i] = i
....: q = p2^10
....: for x in D.keys():
....: assert x.has_initial_segment(q) or D[x]<10
....:
}}}
Dense:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup()
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test4(p1,p2)
1000 loops, best of 3: 1.47 ms per loop
}}}
Non-dense:
{{{
sage: S = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']},
2:{0:['e'],2:['f']}}).path_semigroup(False)
sage: S.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: p1 = a*d*c*b*f*e
sage: p2 = b*e*a*c
sage: %timeit test4(p1,p2)
1000 loops, best of 3: 1.57 ms per loop
}}}
__Conclusion__
It seems to me that the dense encoding may be an interesting idea, but for
most (if not all) applications is not better than the simpler non-dense
encoding.
__Question__
Shall I simply remove the dense implementation? Or should I turn it into a
separate element class, so that a potential user may benefit from
alternative implementations?
--
Ticket URL: <http://trac.sagemath.org/ticket/16453#comment:63>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
