Cheap speedup in the OA recursive constructions

[nathanncohen]

There is a lot to save by not trying to build an Orthogonal Array when ... we already know that we are going to fail.

This is the case when orthogonal_arrays(k-1,n) was called and returned "Unknown" : there is no point in trying to build an orthogonal_array(k,n) later.

This can be cheaply fixed by querying the cache before trying to build the design.

The "clean" fix would be to introduce a is_available along with the existence parameter, but this interface will probably change very soon so it is not the right time to touch all functions and deal with all combinations of existence/available/etc because of that. Besides, the current fix already does the job quite well.

This will all become an Object Oriented Hell quite soon anyway .... :-P

Nathann

Depends on #16423

CC: @videlec

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: b329351

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/16499

[nathanncohen]

comment:1

Oh. And this patch also renames some private methods in a more "object oriented" way. Maybe it will become a real object, someday. Or be rewritten in Cython.

Life.

You never know.

Nathann

[nathanncohen]

Branch: u/ncohen/16499

[sagetrac-git]

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

004833a	trac #16347: Wilson's construction with two truncated groups
f5069f0	trac #16347: Merged with 6.3.beta4
f182d36	trac #16499: Cheap speedup in the OA recursive constructions

[sagetrac-git]

Commit: f182d36

[nathanncohen]

Dependencies: #16347

[videlec]

comment:5

Needs non-trivial rebase over #16347.

[nathanncohen]

comment:6

Rebased !

Nathann

[sagetrac-git]

Changed commit from f182d36 to 934014c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. 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
0fa89d5	trac #16347: Wilson's construction with two truncated groups
828ff22	trac #16437: cut the branches in W. dec. with two trunc. blocks
8ebd21b	trac #16347: use is_sum_of_squares_pyx instead of two_squares
0175134	trac #16347: doc + simplifications
934014c	trac #16499: Cheap speedup in the OA recursive constructions

[sagetrac-git]

Changed commit from 934014c to ee77d8e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ee77d8e

trac #16499: Cheap speedup in the OA recursive constructions

[videlec]

comment:9

Hi Nathann,

I propose to

• move this over Table of MOLS from the handbook and comparison with Sage #16423
• remove the # long time for the MOLS_table test
• change 15 to 20 or 30 in the MOLS_table
  Timings are now

sage: from sage.combinat.designs.latin_squares import MOLS_table
sage: from time import time
sage: t0 = time(); MOLS_table(30); t1 = time()
...
sage: print t1 - t0
3.6996819973

Impressive!

Vincent

[nathanncohen]

comment:10

Yo !

• move this over Table of MOLS from the handbook and comparison with Sage #16423

I will do this as soon as #16423 is reviewed.

• remove the # long time for the MOLS_table test
• change 15 to 20 or 30 in the MOLS_table

No need. We will have to set it back the way it is now as soon as #16500 is reviewed, unless there is a way to save time there.

Timings are now

sage: from sage.combinat.designs.latin_squares import MOLS_table
sage: from time import time
sage: t0 = time(); MOLS_table(30); t1 = time()
...
sage: print t1 - t0
3.6996819973

Impressive!

Too bad it will not last :-/

Nathann

[nathanncohen]

Changed dependencies from #16347 to #16423

[sagetrac-git]

Changed commit from ee77d8e to b329351

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

9ff5062	trac #16423: Table of MOLS from the handbook and comparison with Sage
e64be98	trac #16423: tiny code improvement and alignment
e948cf6	trac #16423: Aligning the alignment
0a7d853	trac #16423: Broken doctests
b329351	trac #16499: Cheap speedup in the OA recursive constructions

[videlec]

comment:13

Good to me!

Vincent

[videlec]

Reviewer: Vincent Delecroix

[vbraun]

Changed branch from u/ncohen/16499 to b329351