Hi Andrew!
On Wed, Dec 12, 2012 at 05:37:19PM -0800, Andrew Mathas wrote:
> 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 Aus 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?
Short answer for now: if you have a finite enumerated set S and you do
S.list(), then this list is cached and used for most other operations
(counting, unranking, and probably random generation as a side
effect). It would be natural to extend this feature to ranking by
building a reverse dictionary (possibly with some level of lazyness,
so that the dictionary only gets built if unranking is actually used).
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
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.
