Opened 5 years ago

Closed 5 years ago

#16499 closed enhancement (fixed)

Cheap speedup in the OA recursive constructions

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: b329351 (Commits) Commit: b3293519d314c2bd98c8074a4bd24f1535d92247
Dependencies: #16423 Stopgaps:

Description

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

Change History (14)

comment:1 Changed 5 years ago by ncohen

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

comment:2 Changed 5 years ago by ncohen

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

comment:3 Changed 5 years ago by git

  • Commit set to f182d3691892b0b1cdde8f4ab61df26845eb3e8b

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

004833atrac #16347: Wilson's construction with two truncated groups
f5069f0trac #16347: Merged with 6.3.beta4
f182d36trac #16499: Cheap speedup in the OA recursive constructions

comment:4 Changed 5 years ago by ncohen

  • Dependencies set to #16347

comment:5 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Needs non-trivial rebase over #16347.

comment:6 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

Rebased !

Nathann

comment:7 Changed 5 years ago by git

  • Commit changed from f182d3691892b0b1cdde8f4ab61df26845eb3e8b to 934014ca028dfacf625284d401cd4c82aa9a0c39

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

comment:8 Changed 5 years ago by git

  • Commit changed from 934014ca028dfacf625284d401cd4c82aa9a0c39 to ee77d8e216b43560d0f22263cd4822ec7c5d5d91

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

ee77d8etrac #16499: Cheap speedup in the OA recursive constructions

comment:9 follow-up: Changed 5 years ago by vdelecroix

Hi Nathann,

I propose to

  • move this over #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

comment:10 in reply to: ↑ 9 Changed 5 years ago by ncohen

Yo !

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

comment:11 Changed 5 years ago by ncohen

  • Dependencies changed from #16347 to #16423

comment:12 Changed 5 years ago by git

  • Commit changed from ee77d8e216b43560d0f22263cd4822ec7c5d5d91 to b3293519d314c2bd98c8074a4bd24f1535d92247

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

9ff5062trac #16423: Table of MOLS from the handbook and comparison with Sage
e64be98trac #16423: tiny code improvement and alignment
e948cf6trac #16423: Aligning the alignment
0a7d853trac #16423: Broken doctests
b329351trac #16499: Cheap speedup in the OA recursive constructions

comment:13 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Good to me!

Vincent

comment:14 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16499 to b3293519d314c2bd98c8074a4bd24f1535d92247
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.