2012/12/13, Nicolas M. Thiery <nicolas.thi...@u-psud.fr>: > 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).
I actually did it in #8920 and removed as it appears that it slows down everything as to test my_object in my_dictionnary the object my_object needs to be hashable and you have to catch the error. Perhaps I did it the wrong way... any advice is welcome. Best, Vincent -- 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.
