#19077: Greatly speed up equality check of equal graphs
-------------------------------------+-------------------------------------
Reporter: novoselt | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/novoselt/graph_eq | 6e83ae06e04597ddcf92cd981f4f690c4b57deef
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by novoselt):
* commit: => 6e83ae06e04597ddcf92cd981f4f690c4b57deef
Comment:
I've run into this problem while profiling code I am working on (face
lattice posets for reflexive polytopes). First run:
{{{
13550671 function calls (13542023 primitive calls) in 73.684 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
4319 10.815 0.003 66.951 0.016
hasse_diagram.py:24(Hasse_diagram_from_incidences)
21595 7.663 0.000 25.948 0.001 digraph.py:468(__init__)
1510140 6.001 0.000 7.231 0.000 {method 'add_edge' of
'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
148526 4.442 0.000 6.108 0.000
lattice_polytope.py:527(__eq__)
4319 3.730 0.001 73.397 0.017
lattice_polytope.py:1822(face_lattice)
17276/12957 3.532 0.000 20.710 0.002
generic_graph.py:19289(relabel)
17276 3.364 0.000 10.626 0.001
generic_graph.py:9865(add_edges)
946746 2.268 0.000 2.268 0.000 {hash}
1765714 2.156 0.000 2.156 0.000
toric_lattice.py:922(ambient_module)
1397396 2.030 0.000 2.030 0.000 {method 'intersection' of
'frozenset' objects}
}}}
second run recreating the same posets:
{{{
58955399 function calls in 216.966 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
9250954 46.562 0.000 63.004 0.000
lattice_polytope.py:527(__eq__)
13056672 43.472 0.000 101.665 0.000 {method 'has_edge' of
'sage.graphs.base.static_sparse_backend.StaticSparseBackend' objects}
13056672 38.784 0.000 140.449 0.000
generic_graph.py:10290(has_edge)
4319 23.099 0.005 166.699 0.039 generic_graph.py:392(__eq__)
9320064 11.157 0.000 11.157 0.000 {isinstance}
4319 10.888 0.003 210.421 0.049
hasse_diagram.py:24(Hasse_diagram_from_incidences)
4996396 6.084 0.000 6.084 0.000
toric_lattice.py:922(ambient_module)
4319 3.726 0.001 216.860 0.050
lattice_polytope.py:1822(face_lattice)
8638 3.073 0.000 11.644 0.001 digraph.py:468(__init__)
604056 2.673 0.000 3.296 0.000 {method 'add_edge' of
'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
8638 2.391 0.000 6.914 0.001
generic_graph.py:19295(relabel)
807792 2.049 0.000 2.049 0.000 {hash}
1397396 2.013 0.000 2.013 0.000 {method 'intersection' of
'frozenset' objects}
}}}
after my change the second run becomes
{{{
13591197 function calls in 61.236 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
4319 10.819 0.003 54.643 0.013
hasse_diagram.py:24(Hasse_diagram_from_incidences)
939270 5.871 0.000 8.093 0.000
lattice_polytope.py:527(__eq__)
4319 3.766 0.001 61.136 0.014
lattice_polytope.py:1822(face_lattice)
8638 3.065 0.000 11.563 0.001 digraph.py:468(__init__)
604056 2.653 0.000 3.282 0.000 {method 'add_edge' of
'sage.graphs.base.sparse_graph.SparseGraphBackend' objects}
8638 2.366 0.000 6.870 0.001
generic_graph.py:19289(relabel)
807792 2.045 0.000 2.045 0.000 {hash}
1397396 2.007 0.000 2.007 0.000 {method 'intersection' of
'frozenset' objects}
302028 1.833 0.000 5.092 0.000 {method 'has_edge' of
'sage.graphs.base.static_sparse_backend.StaticSparseBackend' objects}
1436908 1.760 0.000 1.760 0.000
toric_lattice.py:922(ambient_module)
}}}
so there is actually speed gain due to posets being stored...
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=6e83ae06e04597ddcf92cd981f4f690c4b57deef
6e83ae0]||{{{Speed up equality check of graphs with no multiple
edges.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19077#comment:2>
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.
