#6484: sage.combinat.ranker improvements
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner: nthiery
Type: enhancement | Status: needs_info
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|
6fdc7e5e63016dadc4bab6bfbc47e5a5c0c0e662
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nthiery):
Replying to [comment:22 vdelecroix]:
> The fastest way to create a dictionary from a list is
> {{{
> cdef dict d = {x:i for i,x in enumerate(l)}
> }}}
> I guess it avoids the creation of the pair `(i,x)`.
I hesitated about this; however we are creating a `CallableDict` not a
dict at the end. So using this notation means we are first
constructing a dictionary and then copying it into the `CallableDict`.
This is indeed slightly faster for lists of trivial objects:
{{{
sage: l = range(1000)
sage: %timeit rank_from_list(l) # using generator expression
1000 loops, best of 3: 145 µs per loop
sage: %timeit rank_from_list(l) # using {...}
10000 loops, best of 3: 109 µs per loop
}}}
But not anymore for lists of objects with non trivial hash/eq:
{{{
sage: l = list(Permutations(8))
sage: %timeit rank_from_list(l) # using generator expression
The slowest run took 10.96 times longer than the fastest. This could mean
that an intermediate result is being cached
1 loops, best of 3: 18.8 ms per loop
sage: %timeit rank_from_list(l) # using {..}
The slowest run took 10.08 times longer than the fastest. This could mean
that an intermediate result is being cached
1 loops, best of 3: 21.7 ms per loop
}}}
Note that we can hope for the generator expression to be optimized in
the long run when ranker.py will be cythonized.
> The documentation can be more precise
> {{{
> No error is issued in case of duplicate value in ``l``. Instead,
> the rank function returns the position of some of the duplicates::
> }}}
> The rank of the '''last value''' is returned not just '''some'''.
This is on purpose: I don't want to set this behavior in stone, in
order to leave room for future reimplementations. In any cases it's
explicitly said that this function is meant for lists without
duplicates.
> Sided note: I am pretty sure that with #18330 that something better can
be done so that `__call__` becomes as fast as `__getitem__` (up to a C
function call). But not for this ticket.
Great!
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=6fdc7e5e63016dadc4bab6bfbc47e5a5c0c0e662
6fdc7e5]||{{{6484: minor documentation improvements}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/6484#comment:24>
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.
