Opened 3 years ago

Closed 3 years ago

#29353 closed enhancement (fixed)

fix parent of q-Catalan numbers

Reported by: chapoton Owned by:
Priority: major Milestone: sage-9.1
Component: combinatorics Keywords:
Cc: Merged in:
Authors: Frédéric Chapoton Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 045fbe6 (Commits, GitHub, GitLab) Commit: 045fbe6884eb6d8c1971a2a5666230c8554123bd
Dependencies: Stopgaps:

Status badges

Description

at n=0 and n=1

plus some pep8 details in the modified file

Change History (8)

comment:1 Changed 3 years ago by chapoton

Branch: u/chapoton/29353
Commit: 3f62bbb63f5cbcdd77e554d6ed3ced36a0c4583b
Status: newneeds_review

New commits:

3f62bbbfix parent of q_catalan numbers

comment:2 Changed 3 years ago by tscrim

Reviewers: Travis Scrimshaw

Two questions:

On a similar but technically unrelated issue: What about q_fatorial at n=0? I think that should be special-cased to be q_int(0, q). Similarly for q_binomial when using cyclotomic and n = 0,1.

Is {0, 1}: better (i.e., faster) than [0, 1]:? I have almost always seen the latter in Python code.

Otherwise LGTM.

comment:3 Changed 3 years ago by chapoton

Containment in sets seems to be faster (but I am not so sure):

sage: a = {range(200,400)}
sage: b = list(range(200,400))
sage: %timeit 123 in a
The slowest run took 28.00 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 5: 267 ns per loop
sage: %timeit 123 in b
10000 loops, best of 5: 33.2 µs per loop

sage: a = {0,1}
sage: b =[0,1]
sage: %timeit 5 in a
The slowest run took 29.97 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 5: 252 ns per loop
sage: %timeit 5 in b
The slowest run took 29.55 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 5: 307 ns per loop

I will take care of the q_factorial case too.

comment:4 Changed 3 years ago by git

Commit: 3f62bbb63f5cbcdd77e554d6ed3ced36a0c4583b045fbe6884eb6d8c1971a2a5666230c8554123bd

Branch pushed to git repo; I updated commit sha1. New commits:

045fbe6trac 29353 fix parent of q_factorial(0)

comment:5 Changed 3 years ago by chapoton

I found that page about containment in sets

https://www.geeksforgeeks.org/sets-in-python/

comment:6 Changed 3 years ago by tscrim

Containment in sets is definitely faster, but you also have to create the set every time. Now that I am in front my computer, I can test this:

sage: def test_set(i):
....:     if i in {0,1}:
....:         return True
....:     return False
sage: def test_list(i):
....:     if i in [0,1]:
....:         return True
....:     return False
sage: %timeit test_set(1)
1000000 loops, best of 5: 372 ns per loop
sage: %timeit test_set(2)
1000000 loops, best of 5: 353 ns per loop
sage: %timeit test_list(1)
1000000 loops, best of 5: 344 ns per loop
sage: %timeit test_list(2)
1000000 loops, best of 5: 346 ns per loop

Surprisingly, tuples are the most optimized:

sage: def test_tuple(i):
....:     if i in (0,1):
....:         return True
....:     return False
sage: %timeit test_tuple(1)
1000000 loops, best of 5: 322 ns per loop
sage: %timeit test_tuple(2)
1000000 loops, best of 5: 328 ns per loop

Not that this matters too much, but just a question I had because it is not something I had seen before. You can set it to a positive review if you don't care enough to change it. I don't care either way.

Sorry, I missed the parent test for q_binomial and the code does cover the (n,k) = (1,1) case by taking the k = min(k, n-k).

Thank you for fixing these bugs.

comment:7 Changed 3 years ago by chapoton

Status: needs_reviewpositive_review

ok, setting to positive. Thanks for the review

comment:8 Changed 3 years ago by vbraun

Branch: u/chapoton/29353045fbe6884eb6d8c1971a2a5666230c8554123bd
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.