#18485: Make function to generate *all* independent sets.
-------------------------------------+-------------------------------------
Reporter: Rudi | Owner: Rudi
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Rudi Pendavingh | Reviewers: Vincent Delecroix
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/Rudi/make_function_to_generate__all__independent_sets_|
d55832d5131672ba1d82ed4866ad606d6957f11a
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by Rudi):
Replying to [comment:29 vdelecroix]:
> {{{cdef long r = self.full_rank()}}}
>
> BTW, is this full rank intended to be huge? Doing `r+1` malloc/free of
size `X` is much slower than one malloc/free of size `(r+1)*X`.
Full_rank is not huge, never more than the sizes of bitsets themselves.
Creating an array of bitset_t is what I do in most places, even if the
lenght of that array is huge. Typically the work in computing the contents
of the individual bitsets outweighs the time to allocate them in my
application. The advantage is that each entry is an individual bitset to
which I can apply bitset methods. And in theory (I don't seem to do it
anywhere in practice) you can swap pointers in such an array stead of
copying their contents. So once you've paid for all the memory allocation,
you will only benefit while using it.
But perhaps if we design a new dense hypergraph, we can have our cake and
eat it, by doing mass allocation of the bitset contents and have an array
of pointers on the side. It's just that calling bitset_free has to be
avoided then.
--
Ticket URL: <http://trac.sagemath.org/ticket/18485#comment:33>
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.
