#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:
----------------------------+-----------------------------------------------
Comment(by dcoudert):
Thank you Nathann for the good advices.
I have changed accordingly the standard GNP algorithm.
I have also contracted the fast algorithm but it is a bit more difficult
to read now. The extra cost for N = 10000 and p=0.0001 is 5ms which is
acceptable ;-)
Some running time. The fast algorithm is better for large sparse graphs.
Otherwise, the standard GNP algorithm is now fast enough.
{{{
sage: %timeit G =
digraphs.RandomDirectedGNP(1000,0.001,loops=True,fast=True)
5 loops, best of 3: 55.8 ms per loop
sage: %timeit G = digraphs.RandomDirectedGNP(1000,0.001,loops=True)
25 loops, best of 3: 15.8 ms per loop
sage: %timeit G =
digraphs.RandomDirectedGNP(10000,0.0001,loops=True,fast=True)
5 loops, best of 3: 558 ms per loop
sage: %timeit G = digraphs.RandomDirectedGNP(10000,0.0001,loops=True)
5 loops, best of 3: 1.07 s per loop
sage: %timeit G =
digraphs.RandomDirectedGNP(10000,0.001,loops=True,fast=True)
5 loops, best of 3: 5.31 s per loop
sage: %timeit G = digraphs.RandomDirectedGNP(10000,0.001,loops=True)
5 loops, best of 3: 1.5 s per loop
}}}
D.
PS: concerning m[i][j] versus m[i,j], is it for python or cython ? which
kind of data structure ?
PS2: in general in C, m[i][j] is faster than m[i*N+j], so if you have a
NxN matrix encoded in a 1D array A, it is interesting to create a **B
array of size N and to assign B[i]=A+i*N. Then, we have B[i,j]==A[i*N+j].
OK, I had real C course.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:7>
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.
