#12888: Set new default parameters for RandomGNP
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.1
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: #12362 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by dcoudert):
* status: new => needs_review
* dependencies: => #12362
Old description:
> This patch changes the default parameters of graphs.RandomGNP, following
> discussion for patch #12362.
New description:
This patch changes the default parameters of graphs.RandomGNP.
As reported in [http://groups.google.com/group/sage-
devel/browse_thread/thread/540235c6cc032e75|here] and discussed in #12362,
patch #12362 significantly slows down the graphs.RandomGNP generator. This
is due to a change of default value of parameter ``fast`` from ``True`` to
``False``.
This patch put back this parameter to ``True`` and changes the default
method to ``Sage`` which is faster in most cases.
--
Comment:
The default method is now set to ``Sage`` since it seems faster than the
``networkx`` method, except for very sparse graphs where networkx with
``fast=True`` is faster. Bellow are some experiments from very dense to
very spare graphs.
1) When ``method="networkx"`` and ``fast=False`` (so before this patch and
after patch #12362)
{{{
sage: timeit('graphs.RandomGNP(2000, .8, method = "networkx", fast =
False)')
5 loops, best of 3: 22.5 s per loop
sage: timeit('graphs.RandomGNP(2000, .1, method = "networkx", fast =
False)')
5 loops, best of 3: 6.38 s per loop
sage: timeit('graphs.RandomGNP(2000, .01, method = "networkx", fast =
False)')
5 loops, best of 3: 4.21 s per loop
sage: timeit('graphs.RandomGNP(2000, .001, method = "networkx", fast =
False)')
5 loops, best of 3: 4.07 s per loop
}}}
2) When ``method="networkx"`` and ``fast=True``
{{{
sage: timeit('graphs.RandomGNP(2000, .8, method = "networkx", fast =
True)')
5 loops, best of 3: 19.6 s per loop
sage: timeit('graphs.RandomGNP(2000, .1, method = "networkx", fast =
True)')
5 loops, best of 3: 2.44 s per loop
sage: timeit('graphs.RandomGNP(2000, .01, method = "networkx", fast =
True)')
5 loops, best of 3: 237 ms per loop
sage: timeit('graphs.RandomGNP(2000, .001, method = "networkx", fast =
True)')
25 loops, best of 3: 27.9 ms per loop
}}}
3) When ``method="Sage"`` (with this patch)
{{{
sage: timeit('graphs.RandomGNP(2000, .8, method = "Sage")')
5 loops, best of 3: 11.3 s per loop
sage: timeit('graphs.RandomGNP(2000, .1, method = "Sage")')
5 loops, best of 3: 1.38 s per loop
sage: timeit('graphs.RandomGNP(2000, .01, method = "Sage")')
5 loops, best of 3: 166 ms per loop
sage: timeit('graphs.RandomGNP(2000, .001, method = "Sage")')
5 loops, best of 3: 49 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12888#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 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.
