Opened 7 years ago
Closed 7 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 7 years ago by
comment:2 Changed 7 years ago by
- Branch set to u/ncohen/16499
- Status changed from new to needs_review
comment:3 Changed 7 years ago by
- Commit set to f182d3691892b0b1cdde8f4ab61df26845eb3e8b
comment:4 Changed 7 years ago by
- Dependencies set to #16347
comment:5 Changed 7 years ago by
- Status changed from needs_review to needs_work
Needs non-trivial rebase over #16347.
comment:7 Changed 7 years ago by
- Commit changed from f182d3691892b0b1cdde8f4ab61df26845eb3e8b to 934014ca028dfacf625284d401cd4c82aa9a0c39
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
|
comment:8 Changed 7 years ago by
- Commit changed from 934014ca028dfacf625284d401cd4c82aa9a0c39 to ee77d8e216b43560d0f22263cd4822ec7c5d5d91
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
|
comment:9 follow-up: ↓ 10 Changed 7 years ago by
Hi Nathann,
I propose to
- move this over #16423
- remove the
# long time
for theMOLS_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 7 years ago by
Yo !
- move this over #16423
I will do this as soon as #16423 is reviewed.
- remove the
# long time
for theMOLS_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.6996819973Impressive!
Too bad it will not last :-/
Nathann
comment:11 Changed 7 years ago by
- Dependencies changed from #16347 to #16423
comment:12 Changed 7 years ago by
- Commit changed from ee77d8e216b43560d0f22263cd4822ec7c5d5d91 to b3293519d314c2bd98c8074a4bd24f1535d92247
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
|
comment:13 Changed 7 years ago by
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to positive_review
Good to me!
Vincent
comment:14 Changed 7 years ago by
- Branch changed from u/ncohen/16499 to b3293519d314c2bd98c8074a4bd24f1535d92247
- Resolution set to fixed
- Status changed from positive_review to closed
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