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:  sage6.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:  sage6.3 → sageduplicate/invalid/wontfix 

Status:  needs_review → positive_review 
Right right...
Nathann
comment:5 Changed 9 years ago by
Milestone:  sageduplicate/invalid/wontfix → sage6.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 followup: 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 followup: 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 followup: 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 followup: 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 followup: 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 followup: 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)