Opened 7 years ago

Closed 7 years ago

#13972 closed enhancement (fixed)

Implement the inverse of the method area_dinv_to_bounce_area_map in dyck_word.py

Reported by: zabrocki Owned by: zabrocki
Priority: minor Milestone: sage-5.7
Component: combinatorics Keywords: dyck_words
Cc: dorota@…, stumpc5 Merged in: sage-5.7.beta1
Authors: Mike Zabrocki Reviewers: Christian Stump, Dorota Mazur
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by zabrocki)

In ticket #13550 we implemented Haglund's map which sends dinv/area to area/bounce but did not implement the inverse. This ticket adds the method bounce_area_to_area_dinv_map to dyck_word.py.

Attachments (1)

trac_13972_dyck_word_bounce_area_dinv_inverse-mz.patch (3.5 KB) - added by zabrocki 7 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 follow-up: Changed 7 years ago by zabrocki

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by zabrocki

  • Cc stumpc5 added
  • Description modified (diff)

I restored the code for area_dinv_to_bounce_area_map because of the following timing tests. Original:

sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(8)]') 
5 loops, best of 3: 62.3 ms per loop
sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(9)]') 
5 loops, best of 3: 220 ms per loop
sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(10)]')
5 loops, best of 3: 793 ms per loop

My version:

sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(8)]')
5 loops, best of 3: 82.2 ms per loop
sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(9)]')
5 loops, best of 3: 303 ms per loop
sage: timeit('[D.area_dinv_to_bounce_area_map() for D in DyckWords(10)]')
5 loops, best of 3: 1.1 s per loop

The difference is probably due to the fact that my version had to call to_area_sequence and then output the DyckWord using the area sequence that it constructed.

comment:3 Changed 7 years ago by zabrocki

I just figured a way to speed up bounce_area_to_area_dinv_map based on my last comment. Its not a major difference, but it helps.

comment:4 in reply to: ↑ 1 Changed 7 years ago by stumpc5

Replying to zabrocki:

Hi Mike,

I am happy with the patch and give it a positive review once the patchbot is happy as well. The only suggested change would be: could you add a combinatorial decorator, so we can use this map in the statistic finder?

Cheers, Christian

comment:5 Changed 7 years ago by zabrocki

Hi Christian, Doesn't that require #11641 to add combinatorial decorator? What is the status of that patch? I looked at the patch and it seems that (a) it needs a review (b) it doesn't have most of the combinatorial decorators that were there before. -Mike

comment:6 Changed 7 years ago by DorotaMazur

Hi Mike,

I agree with Christian. It passed all the tests and the documentation also seems ok. Dorota

comment:7 Changed 7 years ago by DorotaMazur

  • Status changed from needs_review to positive_review

comment:8 follow-up: Changed 7 years ago by jdemeyer

Please write your real names in the Author resp. Reviewer fields.

comment:9 in reply to: ↑ 8 Changed 7 years ago by stumpc5

  • Authors changed from zabrocki to Mike Zabrocki
  • Reviewers set to Christian Stump, Dorota Mazur

Replying to zabrocki:

Doesn't that require #11641 to add combinatorial decorator?

Hi Mike (sorry for the delay...),

That's right, I was somewhat loosing track of the tickets and thought that #11641 was merged in in some 5.6 release.

+1 for the positive review...

Replying to jdemeyer:

Please write your real names in the Author resp. Reviewer fields.

I was actually doing that while you were writing this message...

Christian

comment:10 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.7.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.