Morning!
I have being trying to find the right idiom for look-up and reverse look
ups in large enumerated sets. Prior to sage, I simply would have made a
large list of the elements in the enumerated set and then just used
__getitem__ (implictly) and index().
I thought that in sage here might be an approved and efficient way of doing
this but instead I have been surprised. Consider:
sage: parts=Partitions(50)
sage: parts.category()
Category of finite graded enumerated sets
sage: mu=parts.unrank(204225);mu
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: parts.rank(mu)
204225
which looks fine except that unrank is very quick whereas rank is very
slow. Certainly, rank() could be made more efficient by caching the result
)although what to do if the object has multiple parents), but I don't see
any way of making unrank() faster until you create a list of elements. Here
are the timing for this example:
sage: %timeit Partitions(50).unrank(204225)
625 loops, best of 3: 13.7 µs per loop
sage: %timeit Partitions(50).rank(mu)
5 loops, best of 3: 3.66 s per loop
Actually, this is a slight lie: initially, rank and unrank both just run
through the iterator until they hit their match -- and this is slow -- but
after doing something like Partitions(50)[50], in the background
Partitions(50)._list has been created and unrank() has been replaced by
_list[ rank] whereas rank() is still using the iterator. The culprit seems
to be __getitem__ which is initially defined as
try:
return super(Parent, self).__getitem__(n)
except AttributeError:
return self.list()[n]
With other (ungraded?) enumerated sets such as StandardTableaux(10) the
iterator is always used, and this is slow.
I think that the behaviour of Partitions(n) above is a bug, but I am
getting side-tracked.
The question that is want to ask is:
If I have a (large but not hugely large) enumerated set for which I will be
doing frequent rank() and unrank() calls what is the recommended way of
playing with it?
My inclination now is just to turn the enumerated set into a list, as
_list[2832] and _list.index(mu) are as efficient as you get. Does anyone
know of a better way?
Cheers,
Andrew
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/sage-combinat-devel/-/15SYSOpz5PQJ.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
