Opened 6 years ago

Closed 5 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) 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 6 years ago by ncohen

  • Branch set to u/ncohen/16430
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by git

  • Commit set to 03c1f4515b266f11e905136d6bda9a9de126b322

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

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

comment:3 Changed 6 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 6 years ago by ncohen

  • Milestone changed from sage-6.3 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

Right right...

Nathann

comment:5 Changed 6 years ago by ncohen

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.3
  • Status changed from positive_review to needs_work

OOops nononono ! It fixes bugs too !!

comment:6 Changed 6 years ago by ncohen

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

Nathann

comment:7 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:8 Changed 6 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 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to 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 in reply to: ↑ 9 Changed 5 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 5 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 5 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:13 Changed 5 years ago by git

  • Commit changed from 03c1f4515b266f11e905136d6bda9a9de126b322 to 162b83c0772a9c2a02eb3cea71028e8d14a6c0a7

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

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

comment:14 follow-up: Changed 5 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 ; follow-up: Changed 5 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 ; follow-up: Changed 5 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 ; follow-up: Changed 5 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 ; follow-up: Changed 5 years ago by vdelecroix

  • Branch changed from u/ncohen/16430 to u/vdelecroix/16430
  • Commit changed from 162b83c0772a9c2a02eb3cea71028e8d14a6c0a7 to 81b9448a730769e28af52c3ea36faa5b8156232a
  • Reviewers set to 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 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:20 in reply to: ↑ 18 Changed 5 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 5 years ago by vbraun

  • Branch changed from u/vdelecroix/16430 to 81b9448a730769e28af52c3ea36faa5b8156232a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.