#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 | 1181090c4d48f10b1bc20daa517c5396b6d27083
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17112 |
Dependencies: |
#17711 |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Replying to [comment:5 ncohen]:
> Hello David,
>
> A short review before going to sleep:
>
> 1) You do not seem to do anything at all with `max_prefix_number`.
Now used. I forgot some parts. Surprizingly you are less efficient when
the heating system of your building is broken during winter time...
Also I'm now only recording 1 boolean per prefix. We don't need to store
the cost.
> 2) You add parameters in `path_decomposition` but you don't do
> anything with them.
Fixed
> 3) Given that you seem to only store sets of integers, I am
> tempted to think that you should prefer `FrozenBitset` objects
> over `frozenset`. They should give you a faster hash/equality
> test.
My tests gives better performances with `frozenset`. But if you have
better ideas...
> 4) There are many empty docstrings in the methods of
> `PrefixStorage`. And to be honest, considering the amount of doc
> it takes to implement all of that, I wonder if it would not be
> better to leave it all in the code, without creating a new
> class. "Just a dictionary whose keys are bitsets".
>
> In order to not have too many things in the actual
> branch-and-bound, it may be enough to have just a couple of
> functions (your update/is_known_prefix) taking a dictionary as an
> additional argument.
The main advantage of the class is to hide all the parameters. It is very
useful to be able to tune these parameters according the amount of memory
you have. Passing the dict as parameter, we would also have to pass other
parameters.
I'm not convinced that it would really be shorter to have 2 functions
instead of this class.
We could however save the `enable_prefix_storage` parameter since we can
obtain the same behavior setting `max_prefix_length=0`.
> Good night,
>
> Nathann
If you want to know the kind of speedup we get for a quite hard instance:
{{{
sage: G = graphs.MycielskiGraph(5)
sage: %timeit vs, seq = VS.vertex_separation_BAB(G,
enable_prefix_storage=True)
1000 loops, best of 3: 1.3 ms per loop
sage: %timeit vs, seq = VS.vertex_separation_BAB(G,
enable_prefix_storage=False)
100 loops, best of 3: 2.19 ms per loop
sage: G = graphs.MycielskiGraph(6)
sage: %timeit vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=20)
1 loops, best of 3: 1.05 s per loop
sage: %timeit vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=10)
1 loops, best of 3: 1.84 s per loop
sage: %timeit vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=8)
1 loops, best of 3: 12 s per loop
sage: %timeit vs, seq = VS.vertex_separation_BAB(G, max_prefix_length=7)
1 loops, best of 3: 40.8 s per loop
}}}
I have not tested {{{VS.vertex_separation_BAB(G,
enable_prefix_storage=False)}}} with this version of the prefix storage.
With a former version (using trees and so much more ugly code) it was
around 40min, so with dict should be more than 1h
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17712#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 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.
