#19662: Less wasteful management of edge labels
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: positive_review
Type: | Milestone: sage-6.10
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Andrey Novoseltsev
theory | Work issues:
Keywords: | Commit:
Authors: | 1b97eb1147e804d6d506d0ef94e0de09c6cd58e9
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/19662 |
Dependencies: |
-------------------------+-------------------------------------------------
Old description:
> I hate loops,
> I hate multiple edges,
> I hate edge labels.
>
> A colleague of mine recently reported very slow performances with our
> graphs, and he was using edge labels. There were.... Let's say "obvious
> loss of performances" to stay calm.
>
> If you are sensitive to bad algorithms, be warned -- what you will see
> while reviewing this branch may shock you.
>
> Nathann
New description:
I hate loops,
I hate multiple edges,
I hate edge labels.
A colleague of mine recently reported very slow performances with our
graphs, and he was using edge labels. There were.... Let's say "obvious
loss of performances" to stay calm.
If you are sensitive to bad algorithms, be warned -- what you will see
while reviewing this branch may shock you.
As an illustration. Before
{{{
sage: %time Graph([(u,v,1) for u,v in combinations(range(200),2)])
CPU times: user 1.82 s, sys: 0 ns, total: 1.82 s
Wall time: 1.83 s
Graph on 200 vertices
}}}
After
{{{
sage: %time Graph([(u,v,1) for u,v in combinations(range(200),2)])
CPU times: user 88 ms, sys: 12 ms, total: 100 ms
Wall time: 86.6 ms
Graph on 200 vertices
}}}
Nathann
--
Comment (by ncohen):
Thank you for the review. I added a small example, and you can increase
the number to get a speedup factor as large as you wish.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19662#comment:4>
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.
