Opened 9 years ago
Closed 9 years ago
#16430 closed enhancement (fixed)
Small speedup for OA(None,p^c)
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | combinatorial designs | Keywords: | |
Cc: | vdelecroix | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | 81b9448 (Commits, GitHub, GitLab) | Commit: | 81b9448a730769e28af52c3ea36faa5b8156232a |
Dependencies: | Stopgaps: |
Description
When n is a prime power we know from the start the maximum value of k. With a couple of lines, we avoid calling is_prime_power
n+1 times for nothing.
Nathann
A dishonest timing:
sage: %timeit designs.orthogonal_array(None,2**16,t=2,existence=True) # before 1 loops, best of 3: 1.16 s per loop sage: %timeit designs.orthogonal_array(None,2**16,t=2,existence=True) # after 10000 loops, best of 3: 19.9 µs per loop
This ticket also fixes a couple of bugs, i.e. designs.orthogonal_array(None,n,t=30,existence=True)
and designs.orthogonal_array(None,0,existence=True)
.
Nathann
Nathann
Change History (21)
comment:1 Changed 9 years ago by
Branch: | → u/ncohen/16430 |
---|---|
Status: | new → needs_review |
comment:2 Changed 9 years ago by
Commit: | → 03c1f4515b266f11e905136d6bda9a9de126b322 |
---|
comment:3 Changed 9 years ago by
Hi Nathann,
If the cache in #16460 is used, then this would not be needed anymore. As if is_prime_power
is called then we would set the cache directly to n+1
whatever was the value of k
from the call.
Do you still want to keep it?
Vincent
comment:4 Changed 9 years ago by
Milestone: | sage-6.3 → sage-duplicate/invalid/wontfix |
---|---|
Status: | needs_review → positive_review |
Right right...
Nathann
comment:5 Changed 9 years ago by
Milestone: | sage-duplicate/invalid/wontfix → sage-6.3 |
---|---|
Status: | positive_review → needs_work |
OOops nononono ! It fixes bugs too !!
comment:6 Changed 9 years ago by
I will update this in a second. First I send you the review of #16461
Nathann
comment:7 Changed 9 years ago by
Status: | needs_work → needs_review |
---|
comment:8 Changed 9 years ago by
Okay, actually I think that the best is to review this ticket as it is. It also fixes two bugs that need to be fixed anyway, and we will be able to remove those two specific line for prime powers when the caching mechanism will make it in.
Nathann
comment:9 follow-up: 10 Changed 9 years ago by
Status: | needs_review → needs_info |
---|
Hum
sage: designs.orthogonal_array(None,5,t=3,existence=True) 1 sage: designs.orthogonal_array(None,5,t=3) Traceback (most recent call last): ... ValueError: undefined for k less than 2
Why do you allow t=3
when existence
is set to True
?
Vincent
comment:10 Changed 9 years ago by
Yo !
Why do you allow
t=3
whenexistence
is set toTrue
?
Well, we could even return 2. Any two columns would do. Anyway, let's return 0 as we have no code to return the actual OA for the moment.
Nathann
comment:11 Changed 9 years ago by
Okayyyyyyyyy... I fixed several things, as this ticket seems to be a "small bugfixes" dictionary :-P
1) More explicit error messages in _check_pbd. This function will be rewritten in Cython later anyway, but this way we will not forget the error messages.
2) We can always build an OA(1341,0)
, i.e. the empty list
3) There is always an orthogonal_array(t,n,t=t)
. It is just the result of [k]^k
4) I fixed the "undefined for t<k
bug you mentionned, but I wondered if there was a reason to have such an exception. I mean, if you want a property to hold "for any t columns", it holds in particular when you have <t columns doesn't it ? So I would vote for removing this exception. If you agree with it I will add a commit, while in the updated branch the problem is avoided without touching this line
5) I return an OA(t,n,t)
directly to avoid calling is_orthogonal_array
. It is safe because the orthogonal array I return IS an orthogonal array, and I do it because is_orthogonal_array
does not support t>2 yet. But then, those orthogonal arrays are the only ones we can return with t>2.
Nathann
comment:12 Changed 9 years ago by
Status: | needs_info → needs_review |
---|
comment:13 Changed 9 years ago by
Commit: | 03c1f4515b266f11e905136d6bda9a9de126b322 → 162b83c0772a9c2a02eb3cea71028e8d14a6c0a7 |
---|
comment:14 follow-up: 15 Changed 9 years ago by
Hi,
Everything looks good. I have micro modifs that makes it look better at u/vdelecroix/16430. If you like it take it. And you can set to positive review whatever you choose.
Vincent
comment:15 follow-up: 16 Changed 9 years ago by
Yo !
Everything looks good. I have micro modifs that makes it look better at u/vdelecroix/16430. If you like it take it. And you can set to positive review whatever you choose.
I find weird that IntegerRange
only writes two points in {0, .., 5}
, but okay... Is there any reason for that ? :-P
.. SEEALSO:: - :func:`orthogonal_array` -- a tranversal design `TD(k,n)` is equivalent to an orthogonal array `OA(k,n,2)`.
Nathann
comment:16 follow-up: 17 Changed 9 years ago by
Replying to ncohen:
Yo !
Everything looks good. I have micro modifs that makes it look better at u/vdelecroix/16430. If you like it take it. And you can set to positive review whatever you choose.
I find weird that
IntegerRange
only writes two points in{0, .., 5}
, but okay... Is there any reason for that ?:-P
Me too. And the reason is to fit with ellipsis:
sage: [1..5] [1, 2, 3, 4, 5]
Vincent
comment:17 follow-up: 18 Changed 9 years ago by
Yo !
Me too. And the reason is to fit with ellipsis:
sage: [1..5] [1, 2, 3, 4, 5]
And yet you can't copy/paste the output of this IntegerRange into Sage code, it is not the same syntax ..
Well, if you can write back the line of the SEEALSO that you remove we can set this ticket to positive review. I have to admit that I preferred the writing [1,...,5]
to {1, ..,5}
though ...
Nathann
comment:18 follow-up: 20 Changed 9 years ago by
Branch: | u/ncohen/16430 → u/vdelecroix/16430 |
---|---|
Commit: | 162b83c0772a9c2a02eb3cea71028e8d14a6c0a7 → 81b9448a730769e28af52c3ea36faa5b8156232a |
Reviewers: | → Vincent Delecroix |
Replying to ncohen:
Yo !
Me too. And the reason is to fit with ellipsis:
sage: [1..5] [1, 2, 3, 4, 5]And yet you can't copy/paste the output of this IntegerRange into Sage code, it is not the same syntax ..
Well, if you can write back the line of the SEEALSO that you remove we can set this ticket to positive review. I have to admit that I preferred the writing
[1,...,5]
to{1, ..,5}
though ...
But I did not like the [0, ...,0]. The best thing to do would be to improve IntegerRange
;-) Sorry for the SEEALSO this is back.
Vincent
New commits:
03c1f45 | trac #16430: Small speedup for OA(None,p^c)
|
8e8a9f3 | trac #16430: Merged with 6.3.beta4
|
162b83c | trac #16430: Many bugfixes
|
3e01acb | trac #16430: micro improvements
|
81b9448 | trac #16430: put back the seealso
|
comment:19 Changed 9 years ago by
Status: | needs_review → positive_review |
---|
comment:20 Changed 9 years ago by
Yo !
But I did not like the [0, ...,0]. The best thing to do would be to improve
IntegerRange
;-)
Let's do that then.
Sorry for the SEEALSO this is back.
Cool, thanks !
Nathann
comment:21 Changed 9 years ago by
Branch: | u/vdelecroix/16430 → 81b9448a730769e28af52c3ea36faa5b8156232a |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16430: Small speedup for OA(None,p^c)