#12362: Improvement of GNP generators for graphs and digraphs
----------------------------+-----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords: directed graphs, generators
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooo !!!
Nice speedup `:-D`
During the Sage week we also found a similar speedup in a Poset code, by
replacing a ``m[i][j]`` by a ``m[i,j]`` `:-P`
About the length of the code : it can be divided by two at no cost by
removing the "else" on the "loops" argument. If you try to build an edge
between i and i in a graph that that has been built with loops = False the
edge is silently *not* created. And there should be no noticeable
difference in the runtime if the code with loops is applied to the case
where loops are forbidden.
It is also possible to write the two codes
{{{
for 0 <= i < n:
for 0 <= j < n:
if random() < pp:
G.add_edge(i,j)
}}}
and
{{{
# Standard GNP generator for graphs
for 0 <= i < n-1:
for i+1 <= j <n:
if random() < pp:
G.add_edge(i,j)
}}}
as
{{{
for 0 <= i < n-1:
for (i+1 if directed else 0) <= j <n:
if random() < pp:
G.add_edge(i,j)
}}}
Same thing here, a "if" in a loop (with branch prediction !) should not
weigh much `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:6>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
