#17712: Adds memoization to the branch and bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 4cc8d7fc0550aba5fd9e03f3263ede4172ff9b73
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17712 |
Dependencies: |
#17711 |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Since we learned that "internally sets are implemented just as
dictionaries with no values", there is no reason for using dictionary. The
timing was certainly due to the order in which values were inserted in the
set and in the dictionary. Moreover, we can get different results:
{{{
sage: L = []
sage: for i in range(1, 11):
....: for z in Combinations(range(2*i), i):
....: L.append(frozenset(z))
....:
sage: shuffle(L)
sage: d = dict( (k, True) for k in L )
sage: s = set(L)
sage: elt = L[randint(0, len(L)-1)]
sage: %timeit elt in s
10000000 loops, best of 3: 66.8 ns per loop
sage: %timeit elt in d
10000000 loops, best of 3: 64.1 ns per loop
sage: d = dict()
sage: for i in range(1, 11):
for z in Combinations(range(2*i), i):
d[frozenset(z)] = True
....:
sage: %timeit elt in d
10000000 loops, best of 3: 157 ns per loop
}}}
I will change to set.
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17712#comment:21>
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.
