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:

Status badges

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 ncohen

Branch: u/ncohen/16430
Status: newneeds_review

comment:2 Changed 9 years ago by git

Commit: 03c1f4515b266f11e905136d6bda9a9de126b322

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

03c1f45trac #16430: Small speedup for OA(None,p^c)

comment:3 Changed 9 years ago by vdelecroix

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 ncohen

Milestone: sage-6.3sage-duplicate/invalid/wontfix
Status: needs_reviewpositive_review

Right right...

Nathann

comment:5 Changed 9 years ago by ncohen

Milestone: sage-duplicate/invalid/wontfixsage-6.3
Status: positive_reviewneeds_work

OOops nononono ! It fixes bugs too !!

comment:6 Changed 9 years ago by ncohen

I will update this in a second. First I send you the review of #16461

Nathann

comment:7 Changed 9 years ago by ncohen

Status: needs_workneeds_review

comment:8 Changed 9 years ago by ncohen

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 Changed 9 years ago by vdelecroix

Status: needs_reviewneeds_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 in reply to:  9 Changed 9 years ago by ncohen

Yo !

Why do you allow t=3 when existence is set to True?

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 ncohen

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 ncohen

Status: needs_infoneeds_review

comment:13 Changed 9 years ago by git

Commit: 03c1f4515b266f11e905136d6bda9a9de126b322162b83c0772a9c2a02eb3cea71028e8d14a6c0a7

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

8e8a9f3trac #16430: Merged with 6.3.beta4
162b83ctrac #16430: Many bugfixes

comment:14 Changed 9 years ago by vdelecroix

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 in reply to:  14 ; Changed 9 years ago by 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

     .. SEEALSO::

-        :func:`orthogonal_array` -- a tranversal design `TD(k,n)` is equivalent to an
         orthogonal array `OA(k,n,2)`.

Nathann

comment:16 in reply to:  15 ; Changed 9 years ago by vdelecroix

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 in reply to:  16 ; Changed 9 years ago by 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 ...

Nathann

comment:18 in reply to:  17 ; Changed 9 years ago by vdelecroix

Branch: u/ncohen/16430u/vdelecroix/16430
Commit: 162b83c0772a9c2a02eb3cea71028e8d14a6c0a781b9448a730769e28af52c3ea36faa5b8156232a
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:

03c1f45trac #16430: Small speedup for OA(None,p^c)
8e8a9f3trac #16430: Merged with 6.3.beta4
162b83ctrac #16430: Many bugfixes
3e01acbtrac #16430: micro improvements
81b9448trac #16430: put back the seealso

comment:19 Changed 9 years ago by vdelecroix

Status: needs_reviewpositive_review

comment:20 in reply to:  18 Changed 9 years ago by ncohen

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 vbraun

Branch: u/vdelecroix/1643081b9448a730769e28af52c3ea36faa5b8156232a
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.