#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:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_review => needs_work
Comment:
Hello,
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.
2. Something should be done for `KeyboardInterruption`. i.e. proper
`sig_on/sig_off` and appropriate testing.
3. In the other method `independent_sets`:
- the variable `int i` is useless.
- 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`.
--
Ticket URL: <http://trac.sagemath.org/ticket/18485#comment:51>
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.
