#13223: Implement Poset.is_graded using a polynomial time (linear?) algorithm.
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: sd40 | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/implement_poset_is_graded_using_a_polynomial_time__linear___algorithm_|
a9896c7e9f9e8e6c6f52a25a3370c2d595e2fecf
Dependencies: #13222 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Replying to [comment:17 ncohen]:
> Now, if you really need to save some time on this function you can
change a couple of lines to avoid creating lists unnecessarily, turn the
Python list into a C arrays, things like that. But I think that the Poset
code still needs other improvements before this kind of things begin to be
the critical costs.
Yep. Should this one be marked as positive_review and moved to wontfix-
milestone?
> About definitions, though: what is implemented is not equivalent to
`return all(rf(i) == rank for i in maxes)`, for you need to do the same
with mins.
True.
> It would be interesting to compare the speed of `rank_dict` and
`is_graded` though, as their code is very similar.
I made a code that was slightly faster when calculating how many of
`Posets(8)` are graded (assuming that ranks were not already computed). IF
"going up" is cheaper than going down, i.e. poset is internally saved as
digraph of upper covers, then in principle current implementation would be
`O(n^2)` and my implementation `O(n)`. But in reality this sppedup is not
happening.
--
Ticket URL: <http://trac.sagemath.org/ticket/13223#comment:18>
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.
