#6484: sage.combinat.ranker improvements
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: nthiery
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: rank, unrank | Merged in:
Authors: Nicolas M. Thiéry | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/nthiery/sage_combinat_ranker_improvements|
32d5cea664e153895d663b5913e45d03b8c0a305
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nthiery):
I Travis!
Replying to [comment:11 tscrim]:
> I'm okay with the hashability as we assume all elements to be hashable
Well, this hashabilitiy assumption was not there before this ticket. So
technically speaking that's a backward incompatible change. I agree that
in all use cases I can think of, the objects are hashable, so it probably
is not a big deal.
>, nor is picklability important to me. However this now makes
`rank_from_list` to be the `O(n)` function, and the function itself is not
cached. So for large lists (or worse, say for a crystal where iteration is
relatively expensive), this could lead to a pretty large slowdown. How
about we just return the original implementation of `rank` as a cached
function?
When `rank_from_list` is called, that's usually with the intention of
calling it intensively afterward; in particular the ranker is typically
stored in the calling object for all later reuse. At least, that's the
case in all the current calls in the Sage library.
Being completely lazy and implementhing `rank_from_list` as a cached
function on top of `list.index` would imply an overhead of `O(n^2)`
instead of `O(n)` before we reach the limit state where the complexity in
`O(1)`; not great. We could introduce some partial lazyness, making sure
that the first time an object `x` is looked up, the cache is set for all
objects before `x` in the list. What do you think? Is it worth it?
A note: the name `from_list` makes it relatively explicit that the
iterable will be expanded anyway.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/ticket/6484#comment:12>
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.
