#18485: Make function to generate *all* independent sets.
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.0
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Rudi Pendavingh | Reviewers: Vincent Delecroix,
Report Upstream: N/A | Travis Scrimshaw
Branch: | Work issues:
u/tscrim/matroid_all_independent_sets-18485| Commit:
Dependencies: | 4a5bd5f18c87dbbc2c61423e13492ee384d0e5fb
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:51 vdelecroix]:
> 1. This is very bad
> {{{
> + I = <bitset_t*>sage_malloc((r + 1) * sizeof(bitset_t))
> + T = <bitset_t*>sage_malloc((r + 1) * sizeof(bitset_t))
> + for i in range(r + 1):
> + bitset_init(I[i], self._bitset_size)
> + bitset_init(T[i], self._bitset_size)
> }}}
> It calls `2(r+2)` times memory allocation for arrays of fixed size!
There should be only *one* memory allocation call for everything.
These are just my 2 cents and do not constitute an expert opinion on this
issue.
I believe it has to be the two arrays of bitsets because of the code (at
least without adding additional bitset manipulations and reimplementing
the `__closure`).
Although I don't know if it is faster to use a python list of bitsets or
the allocated block of memory. My intuition says the latter because it
avoids the Python overhead.
> 2. Something should be done for `KeyboardInterruption`. i.e. proper
`sig_on/sig_off` and appropriate testing.
Do you need a `sig_on` / `sig_off` for `cpdef` functions?
> 3. In the other method `independent_sets`:
> - the variable `int i` is useless.
Yes, it is redundant; `r` could be used in its stead.
> - replace
> {{{
> cdef list I = [frozenset() for i in range(self.full_rank()+1)]
> }}}
> with
> {{{
> cdef list I = [frozenset()] * (self.full_rank()+1)
> }}}
> - why using `frozenset` in `I`? Using `set` would allow to replace
`I[r+1] = I[r].union([e])` with
> {{{
> I[r+1] = I[r].copy()
> I[r+1].update(e)
> }}}
> It avoids a one element list to be created and `update` is much faster
than `union`.
If this switches to using `set`, then we can't do the first replacement
(which I believe you are aware, but I'm stating for the record). I'm +1
for changing to `set` and the above; it is much better in terms of memory
manipulations and should gain some speed improvements. Additionally
(mostly a note for myself), we will also need to cast the result into a
frozenset:
{{{#!diff
-self.__closure(T[i+1], self._input)
+self.__closure(frozenset(T[i+1]), self._input)
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18485#comment:52>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
