Opened 6 years ago

Closed 6 years ago

#16295 closed enhancement (fixed)

Faster is_orthogonal_array

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: vdelecroix, knsam, dimpase Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix, Brett Stevens
Report Upstream: N/A Work issues:
Branch: 02f1247 (Commits) Commit: 02f12476967dd287ffb47e711098a5518efbddd2
Dependencies: #16236 Stopgaps:

Description

As the ticket claims this ticket implements a Cython version of is_orthogonal_array, which is then called by is_transversal_design and are_mutually_orthogonal_latin_squares.

Also sets a check=False in the code which slowed things down. As a resultthe tests are checked faster in the designs/ folder !

Nathann

Change History (73)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Branch set to u/ncohen/16295
  • Commit set to 0d5c222cc78546cada8ae505197f429781b9595c

Last 10 new commits:

31a53f2trac #16235: update the MOLS table
1a13ff8trac #16241: New MOLS shared by Ian Wanless
2af2acftrac #16241: missing links and tests
7e77f90trac #16241: Broken doctests
83b0d2ctrac #16241: Merged with updated #16235
c212bf9trac #16241: Broken doctests
e655b36trac #16236: Five mutually orthogonal latin squares of order 12
b516266trac #16236: Merged with updated #16241
f5339fatrac #16236: Broken doctests
0d5c222trac #16295 : Faster is_orthogonal_array

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 follow-up: Changed 6 years ago by brett

Nathann,

The code looks good and I have tested on an example different from your doc test.

The following run fine:

make, doc-test, docbuild html, code coverage is 100%

I had trouble making the pdf documentation and then went back to devel branch to check it worked Ok there. It did and then when I moved back to u/ncohen/16295 it worked. I am not sure what happened

I think this needs two things:

  • it needs to be as consistent as possible with the purely python version inside orthogonal_arrays.py. That is, it will react the same way on the same input. This change should be done and then a doc-test written to verify it.
  • it needs to have a doctest that demonstrates the speed improvement that cycthon gives over the purely python version inside orthogonal_arrays.py.

comment:5 in reply to: ↑ 4 Changed 6 years ago by ncohen

Hellllooooo !!

I had trouble making the pdf documentation and then went back to devel branch to check it worked Ok there. It did and then when I moved back to u/ncohen/16295 it worked. I am not sure what happened

Yeah, we had the same problems just one hour ago when Volker tried to merge #16277 or #16235... And it does not happen again because Sphinx is totall unreliable. I expect it to ocome from the dependencies, not from this ticket

I think this needs two things:

  • it needs to be as consistent as possible with the purely python version inside orthogonal_arrays.py. That is, it will react the same way on the same input. This change should be done and then a doc-test written to verify it.

Once this patch is applied there is no python version inside of orthogonal_arrays.py, as this patch removes it. We can add any doctest you want, but what could it be ? Remember that this function is already tested a LOT by all constructions of OA/TD/MOLS as it is run on those instances every time one is built.

  • it needs to have a doctest that demonstrates the speed improvement that cycthon gives over the purely python version inside orthogonal_arrays.py.

Once more, this function removes the purely python one.

Nathann

comment:6 follow-up: Changed 6 years ago by vdelecroix

Hi Nathann,

You should avoid using any in Cython. This is not properly cythonized. The following is better by 15%:

for i in range(len(OA)):
    if len(OA[i]) != k:
        if verbose:
            print {"OA"   : "Some row does not have length "+str(k),
                   "MOLS" : "The number of matrices is not "+str(k)}[terminology]

If you do so, you need to move up the cdef int i,j,l.

Vincent

comment:7 in reply to: ↑ 6 Changed 6 years ago by ncohen

Yoooooooo !!

You should avoid using any in Cython. This is not properly cythonized. The following is better by 15%:

It is good to know, but I really do not think that this is the critical part here :-D

Nathann

comment:8 follow-up: Changed 6 years ago by brett

Sorry, I had changed branches and then opened orthogonal_array.py in an editor and so thought is_orthogonal_array was still there.

Here is my timing data

with Cython:

sage: time is_orthogonal_array(OA,8,9)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 27.2 µs
False
sage: time is_orthogonal_array(OA,12,11)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 239 µs
True

with Python:

sage: time is_orthogonal_array(OA,8,9,2)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 29.1 µs
False
sage: time is_orthogonal_array(OA,12,11,2)
CPU times: user 12 ms, sys: 4 ms, total: 16 ms
Wall time: 13.1 ms
True

this shows a significant improvement in speed.

However I think this needs to be fixed:

sage: is_orthogonal_array(OA,12,11,3)
True

If it is passed t=3 it should at least alert the user that it is going to override this with t=2

Here is what I think should be done:

  • fix t>2 bug
  • remove "any" as Vincent suggested
  • implement a doc test for
    • all your bad input/format tests
    • memory test
    • t>2 test
Last edited 6 years ago by brett (previous) (diff)

comment:9 Changed 6 years ago by brett

p.s. where is sage_free documented?

comment:10 in reply to: ↑ 8 Changed 6 years ago by ncohen

Hello !

  • fix t>2 bug

Done.

  • remove "any" as Vincent suggested

Guys, it is very important that you understand that this is what is called "taste", and that it makes absolutely no difference in the runtimes. If you want to make changes like that, it would be cool to implement it yourself instead of asking me to do it for you.

I just did it, because I need the patch to get in quick.

  • implement a doc test for
    • all your bad input/format tests

Done.

  • memory test

I cannot test that.

  • t>2 test

Done.

Nathann

comment:11 Changed 6 years ago by git

  • Commit changed from 0d5c222cc78546cada8ae505197f429781b9595c to 839acc5a498c2fea319f92b477b1995f31d3bb9d

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

411a759trac #16286: Merged with updated #16277
11eff2ctrac #16235: Merged with 6.2
5a0e3fetrac #16235: Merged with #16231
c0b13c4trac #16235: Merged with updated #16286
9fb0f62trac #16241: useless if condition in MOLS constructor
67ab2d2trac #16241: Merged with updated #16235
2d7da8atrac #16236: Merged with updated #16241
973b926trac #16236: Merged with #16272
37681e2trac #16295 : Faster is_orthogonal_array
839acc5trac: Doctests and review

comment:12 Changed 6 years ago by git

  • Commit changed from 839acc5a498c2fea319f92b477b1995f31d3bb9d to 994324e77dbe8f3126aeba9059dc847feaebe8bc

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

994324etrac #16295: Doctests and review

comment:13 Changed 6 years ago by ncohen

Brett : the performance improvements are particularly nice for LARGE designs ! I implemented this because I wanted to check that we could indeed produce all the OA promised in our MOLS table, but some (in particularly prime powers, for k gets very large) took VERY long. With this, it is really faster and checking that the OA is an OA is not the bottleneck anymore when playing with designs.

Nathann

comment:14 Changed 6 years ago by ncohen

A bugfix. u=1 was disregarded by mistake in wilson_construction. Julian R. Abel spotted this from only looking at the MOLS table. That's scary O_O;;;;

Nathann

comment:15 Changed 6 years ago by git

  • Commit changed from 994324e77dbe8f3126aeba9059dc847feaebe8bc to b9f8b0388a8cd333bfaf4160896b09be5550896a

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

fc6de73trac #16295: Merged with 6.3.beta1
b9f8b03trac #16295: bugfix in wilson's construction

comment:16 Changed 6 years ago by brett

Vincent,

What does it mean that "any" is not properly cythonized. Does this just mean it is not efficient or does it mean there could be problems with future versions of cython?

brett

comment:17 follow-up: Changed 6 years ago by brett

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

and recieved

From trac.sagemath.org:sage
 * branch            u/ncohen/16295 -> FETCH_HEAD
fatal: Not possible to fast-forward, aborting.

how do I update this branch?

thanks brett

comment:18 follow-up: Changed 6 years ago by brett

As suggestedin the developers guide, I just ran

$git checkout master
Switched to branch 'master'
Your branch is ahead of 'origin/master' by 1992 commits.
$ git reset --hard trac/master
fatal: ambiguous argument 'trac/master': unknown revision or path not in the working tree.
Use '--' to separate paths from revisions

I am not sure what to do, the developers guide does not help here.

brett

Last edited 6 years ago by brett (previous) (diff)

comment:19 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by dimpase

Replying to brett:

As suggestedin the developers guide, I just ran

$git checkout master

Why do you need this? This brings you to the stable Sage release (6.2). Of course you are miles ahead of it, being around 6.3.beta1 or even later.

comment:20 in reply to: ↑ 17 ; follow-up: Changed 6 years ago by dimpase

Replying to brett:

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

how about doing this without --ff-only ?

comment:21 in reply to: ↑ 19 ; follow-up: Changed 6 years ago by brett

Replying to dimpase:

Replying to brett:

As suggestedin the developers guide, I just ran

$git checkout master

Why do you need this? This brings you to the stable Sage release (6.2). Of course you are miles ahead of it, being around 6.3.beta1 or even later.

I keep a current stable release branch for reference and stability if I need it. I think I have done something to it.

Last edited 6 years ago by brett (previous) (diff)

comment:22 in reply to: ↑ 20 ; follow-up: Changed 6 years ago by brett

Replying to dimpase:

Replying to brett:

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

how about doing this without --ff-only ?

Ok I tried

$ git checkout u/ncohen/16295 
Switched to branch 'u/ncohen/16295'
$ git pull trac u/ncohen/16295
From trac.sagemath.org:sage
 * branch            u/ncohen/16295 -> FETCH_HEAD
Auto-merging src/sage/schemes/hyperelliptic_curves/monsky_washnitzer.py
Auto-merging src/sage/combinat/designs/orthogonal_arrays.py
CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py
Auto-merging src/sage/combinat/designs/latin_squares.py
Auto-merging src/sage/combinat/designs/designs_pyx.pyx
CONFLICT (add/add): Merge conflict in src/sage/combinat/designs/designs_pyx.pyx
Auto-merging src/sage/combinat/designs/block_design.py
Auto-merging src/module_list.py
Automatic merge failed; fix conflicts and then commit the result.

Have I somehow changed the files? I certainly did not intend to.

brett

comment:23 in reply to: ↑ 21 Changed 6 years ago by dimpase

Replying to brett:

as you see switching to the branch master rather than already on branch master, and you're ahead of master by a zillion commits, you are most probably on develop, or on some other branch you got onto while reviewing a ticket.

comment:24 in reply to: ↑ 22 Changed 6 years ago by dimpase

Replying to brett:

Replying to dimpase:

Replying to brett:

To look at the new code for this patch, I updated master and develop. Then I tried

git checkout u/ncohen/16295
git pull --ff-only trac u/ncohen/16295

how about doing this without --ff-only ?

Ok I tried

$ git checkout u/ncohen/16295 
Switched to branch 'u/ncohen/16295'
$ git pull trac u/ncohen/16295
From trac.sagemath.org:sage
 * branch            u/ncohen/16295 -> FETCH_HEAD
Auto-merging src/sage/schemes/hyperelliptic_curves/monsky_washnitzer.py
Auto-merging src/sage/combinat/designs/orthogonal_arrays.py
CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py
Auto-merging src/sage/combinat/designs/latin_squares.py
Auto-merging src/sage/combinat/designs/designs_pyx.pyx
CONFLICT (add/add): Merge conflict in src/sage/combinat/designs/designs_pyx.pyx
Auto-merging src/sage/combinat/designs/block_design.py
Auto-merging src/module_list.py
Automatic merge failed; fix conflicts and then commit the result.

Have I somehow changed the files? I certainly did not intend to.

are you updating from develop? Or master? On the other hand I just tried git trac pull 12345 (I am using git-trac-command, which I would recommend!) it is worked.

Perhaps you should try checking out develop and then trying again...

comment:25 Changed 6 years ago by ncohen

Guys guys, all this is happening because I rewrote history here. The only thing to do brett is to checkout my branch, or to checkout "develop" and then to pull my branch.

The copy of my branch that you have on your computer has been abandonned. If you do a checkout on it THEN pull my branch then you are trying to apply the same modifications twice, and it fails.

If you can delete the copy of my branch that you have on my computer, do it.

It is a bit hard to debug without having both hands on your keyboard, though :-/

Nathann

comment:26 Changed 6 years ago by brett

Everything is good except I am still having trouble building the documentation

$sage -docbuild reference html
.
.
.
c_functions                                    writing output... [ 99%] tableaux
                                               writing output... [100%] words
[combinat ] None:38: WARNING: citation not found: Schiffmann
Error building the documentation.
Traceback (most recent call last):
  File "/home/brett/Projects/SAGE/sage/src/doc/common/builder.py", line 1477, in <module>
    getattr(get_builder(name), type)()
  File "/home/brett/Projects/SAGE/sage/src/doc/common/builder.py", line 487, in _wrapper
    x.get(99999)
  File "/home/brett/Projects/SAGE/sage/local/lib/python/multiprocessing/pool.py", line 554, in get
    raise self._value
OSError: [combinat ] None:38: WARNING: citation not found: Schiffmann

Do you get this error too Nathann?

comment:27 follow-up: Changed 6 years ago by ncohen

Helloooooo Brett !!

No I don' get this error and apparently it does not come from the designs code but somewhere else.. I think you should run "make doc-clean && make" which will re-build the doc. Takes some time, but not tooo long either. Sorry, I think you hit a lot of walls on this tickets ^^;

Nathann

comment:28 in reply to: ↑ 27 Changed 6 years ago by brett

Replying to ncohen:

Helloooooo Brett !!

No I don' get this error and apparently it does not come from the designs code but somewhere else.. I think you should run "make doc-clean && make" which will re-build the doc. Takes some time, but not tooo long either. Sorry, I think you hit a lot of walls on this tickets ^^;

Nathann

It is not a problem. The coding part of this patch is clear and easy so this is a good ticket to hit the other kinds of problems that might show up when reviewing.

comment:29 Changed 6 years ago by brett

make doc-clean && make worked fine. Does this build both html and pdf documentation?

comment:30 Changed 6 years ago by ncohen

I think it only build the html one. "make doc-pdf" builds the pdf version :-)

Nathann

comment:31 follow-up: Changed 6 years ago by leif

    # Filling times_n
    for i in range(n+1):
        times_n[i] = i*n

Ahem, you care for speed? ;-)

(And there's no times_n2[] either.)

comment:32 in reply to: ↑ 31 ; follow-up: Changed 6 years ago by ncohen

Ahem, you care for speed? ;-)

Yeah. And it turns out that I am totally incompetent.

When caching the multiplication

sage: OA=designs.orthogonal_array(None,2**7,check=False)
sage: %timeit is_orthogonal_array(OA,2**7+1,2**7,2)                    
1 loops, best of 3: 618 ms per loop

When you don't

sage: OA=designs.orthogonal_array(None,2**7,check=False)
sage: %timeit is_orthogonal_array(OA,2**7+1,2**7,2)                    
1 loops, best of 3: 375 ms per loop

.......................................................

(And there's no times_n2[] either.)

times_n2 ? What for ?

Anyway, this caching was the only thing keeping me from implementing this for all t, so now I will be able to implement it generally now. Cool -_-

Nathann

comment:33 follow-up: Changed 6 years ago by brett

Does this data show that it is faster to simply do the multiplications?

comment:34 in reply to: ↑ 33 Changed 6 years ago by leif

Replying to brett:

Does this data show that it is faster to simply do the multiplications?

In general depends on your CPU and your (C) compiler. (And in conjunction with Cython, the kind of code the latter generates, i.e., whether the C compiler can "guess" what's meant or whether the code is to obfuscated.)

comment:35 in reply to: ↑ 32 ; follow-up: Changed 6 years ago by leif

Replying to ncohen:

times_n2 ? What for ?

It's used twice, in the outer loop and the first inner loop:

    for i in range(k): # For any column C1
        C1 = OAc+i*n2
        for j in range(i+1,k): # For any column C2 > C1
            C2 = OAc+j*n2
            ...

One would usually not look up multiples of n^2 (or n in the earlier case), but do

    C1 = OAc
    i = 0
    while i < k:

        ... # similar for C2, j

        C1 += n2
        i++

In C, you'd presumably drop j (and perhaps also i) altogether, and just compare the pointers to the address of the (current sub-)array end.

(And inlining the bitset operations would of course make it even faster. Afterwards special-case for n=2m ... :-) )

comment:36 in reply to: ↑ 35 Changed 6 years ago by ncohen

It's used twice, in the outer loop and the first inner loop:

Come on... This is not the bottleneck :-P

(And inlining the bitset operations would of course make it even faster. Afterwards special-case for n=2m ... :-) )

They may be inlined already ! I didn't check though.

Anyway. Let's remove this useless caching, and then I will go sleep a bit. I couldn't do this earlier because my laptop is totally breaking and my screen refused to turn on T_T

Nathann

comment:37 Changed 6 years ago by git

  • Commit changed from b9f8b0388a8cd333bfaf4160896b09be5550896a to 2414b81b0ace07a1c0febb54dc86712b2cbafc73

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

2414b81trac #16295: Undoing useless """optimizations"""

comment:38 Changed 6 years ago by ncohen

  • Component changed from combinatorics to combinatorial designs

comment:39 Changed 6 years ago by ncohen

Would anybody have some time for this ticket ? :-P

Nathann

comment:40 follow-ups: Changed 6 years ago by brett

Nathann

I am in Finland visiting a colleague. My plan is to produce a patch on top of this that implements Vincent's code for "any" and does some small work on English and once I commit it and if you are OK with my changes we can finish with this patch. I am sorry I am working in spurts on these sage patches, but I am trying to make the most of my time with my colleague here. It will be soon.

regards brett

comment:41 in reply to: ↑ 40 Changed 6 years ago by ncohen

Hello !

I am in Finland visiting a colleague.

Okayyyyyyyyy.... !

My plan is to produce a patch on top of this that implements Vincent's code for "any"

This is already done, I updated the code last time and there is no "any" anymore.

and does some small work on English

Okay.

and once I commit it and if you are OK with my changes we can finish with this patch. I am sorry I am working in spurts on these sage patches, but I am trying to make the most of my time with my colleague here. It will be soon.

Got it ! Have fun there.

Nathann

comment:42 in reply to: ↑ 40 Changed 6 years ago by leif

Replying to brett:

My plan is to produce a patch on top of this that [...] does some small work on English and once I commit it and if you are OK with my changes we can finish with this patch.

Yes, there are some typos, and the first sentence of the docstring refers to M while the parameter's name is OA.

comment:43 Changed 6 years ago by git

  • Commit changed from 2414b81b0ace07a1c0febb54dc86712b2cbafc73 to f1c7fa1da662e2ca6863ba5bc600fd15e1e3af26

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

f1c7fa1trac #16295: Typo

comment:44 Changed 6 years ago by git

  • Commit changed from f1c7fa1da662e2ca6863ba5bc600fd15e1e3af26 to 31e84b82913815b2005b5e2e45650c1568a45761

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

451d359trac #16295: Merged with 6.3.beta2
31e84b8trac #16295: todo note

comment:45 Changed 6 years ago by ncohen

Okay guys... Well it has been two weeks, so if the only problem of this patch is a typo perhaps it can be dealt with ?... There are several branches depending on this one...

Nathann

comment:46 Changed 6 years ago by brett

I am just back from Scandinavia. I will do this today.

brett

comment:47 follow-up: Changed 6 years ago by brett

I have made almost all the changes. In the code line

if verbose:
    print {"OA"   : "Columns {} and {} are not orthogonal".format(i,j),
           "MOLS" : "Matrices {} and {} are not orthogonal".format(i,j)}[terminology]
    return False

Is there a compact way of switching depending on the values of i and j in the case that terminology=MOLS? if i = 0 and j>1 then "square j-2" is not row latin. if i=1 and J> 1 then square j-2 is not column latin" if both i,j >2 then "square i-2 is not orthogonal to square j-2"

if i=0 and j=1 I have not found the right way to word the error message yet. Perhaps something like "the row and column indices are not orthogonal"

brett

Last edited 6 years ago by brett (previous) (diff)

comment:48 in reply to: ↑ 47 Changed 6 years ago by ncohen

Hello !

Replying to brett:

I have made almost all the changes. In the code line

if verbose:
    print {"OA"   : "Columns {} and {} are not orthogonal".format(i,j),
           "MOLS" : "Matrices {} and {} are not orthogonal".format(i,j)}[terminology]
    return False

Is there a compact way of switching depending on the values of i and j in the case that terminology=MOLS? if i = 0 and j>1 then "square j-2" is not row latin. if i=1 and J> 1 then square j-2 is not column latin" if both i,j >2 then "square i-2 is not orthogonal to square j-2"

This block of code is not about each matrix being a latin square. Actually, this is not checked anywhere so I will add a commit.

This block of code is about the orthogonality of two matrices, i.e. do you find all possible pairs of integers when you read them simultaneously cell by cell.

Nathann

comment:49 follow-ups: Changed 6 years ago by brett

Nathann,

I understand what the code is doing. When I say "square" I mean "latin square" and in the language of MOLS column 0 of an OA is the row index of the Squares, column 1 is the column index and column i is latin square i-2. I am just making the error reporting consistent with the way that a MOLS person would interpret it. Please do not change the branch yet as I am in the middle of editing the code. I was just curious if there was a compact way to use a more complex case/switch in cython. But I think there is not so I will just make the changes with nested if statements.

brett

comment:50 in reply to: ↑ 49 Changed 6 years ago by ncohen

Still, it must be checked that each matrix is a latin square, because right now we have this :

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])                                               
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])                                               
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True)                         
True

I added a commit on u/ncohen/16295_v2 to fix that. Do not worry about possible conflicts with what you are doing : when you will be done, push your commit wherever you want on a branch of yours, give me its name and I will deal with the merge.

Nathann

comment:51 in reply to: ↑ 49 ; follow-up: Changed 6 years ago by ncohen

Hello,

I understand what the code is doing. When I say "square" I mean "latin square" and in the language of MOLS column 0 of an OA is the row index of the Squares, column 1 is the column index and column i is latin square i-2.

Right now when are_mutually_latin_squares calls is_orthogonal_array it does not check that the resulting OA is a OA(k+2,n) but only that it is a OA(k,n). This, because the OA that is produced has only k columns and not k+2. This, because the columns corresponding to the row indices and the columns indices are not added to the OA.

This way, when the sequence of matrices is not a MOLS, the error message is that "matrix i is not orthogonal with matrix j" or that "matrix i is not a latin squares".

Which is, I believe, clearer to the user and easier to implement than by messing with the error messages of is_orthogonal_design.

Nathann

comment:52 in reply to: ↑ 51 ; follow-up: Changed 6 years ago by brett

I just tried

$git trac push
git: 'trac' is not a git command. See 'git --help'.

but this did not work to push my revision up. What command do I use?

comment:53 in reply to: ↑ 52 Changed 6 years ago by ncohen

Hello !

but this did not work to push my revision up. What command do I use?

You seem to want to use "git trac" but it is not installed. This being said if you downloaded the branch without using "git trac" I don't think that just pushing is going to work.

What is the output of

git push trac HEAD:public/16295

It should push your current branch to public/16295.

Nathann

comment:54 follow-ups: Changed 6 years ago by brett

The Sage developers guide says "git trac puch" not "git push trac"

here is what I get when I do it the right way around:

$ git push trac
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
remote: FATAL: W refs/heads/u/ncohen/16295 sage brett DENIED by fallthru
remote: error: hook declined to update refs/heads/u/ncohen/16295
To git@trac.sagemath.org:sage.git
 ! [remote rejected] u/ncohen/16295 -> u/ncohen/16295 (hook declined)
error: failed to push some refs to 'git@trac.sagemath.org:sage.git'
Last edited 6 years ago by brett (previous) (diff)

comment:55 in reply to: ↑ 54 Changed 6 years ago by ncohen

The Sage developers guide says "git trac puch" not "git push trac"

here is what I get when I do it the right way around:

Okay. So you noticed that the "right way" did not work. Can you try the "wrong way", i.e. the line I gave you above ? From the error message you got I think it will work.

The reason is simple : you cannot simply "push" to my branch because you have no write access to it. All branches whose name is u/my_login/whatever can only be written by guys whose login is my_login.

public/whatever branches can be written by anybody, though.

Nathann

comment:56 follow-ups: Changed 6 years ago by brett

your command worked but it creates a new branch and that is inoptimal

$ git push trac HEAD:public/16295
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
To git@trac.sagemath.org:sage.git
 * [new branch]      HEAD -> public/16295

Does this get attached to the right ticket?

Last edited 6 years ago by brett (previous) (diff)

comment:57 in reply to: ↑ 56 Changed 6 years ago by ncohen

your command worked but it creates a new branch and that is inoptimal

Don't worry about branches, nobody has to pay for them. Anyway you cannot write on my branch (which is not my doing) so there is no other way.

Does this get attached to the right ticket?

It does not get attached to any ticket. You just added a branch on the trac server. Now I can look at it, we can discuss it, and if we agree with what is inside I will push it on the branch which is on this ticket. Or I will change this ticket's branch to public/16295 if it is easier.

Nathann

comment:58 in reply to: ↑ 56 ; follow-up: Changed 6 years ago by dimpase

Replying to brett:

your command worked but it creates a new branch and that is inoptimal

$ git push trac HEAD:public/16295
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
To git@trac.sagemath.org:sage.git
 * [new branch]      HEAD -> public/16295

Does this get attached to the right ticket?

Why do you think this is not optimal? This is a normal way to go. Surely if there already was public/16295 branch you'd rather pushed there. But there was none. You can't push into someone else's branch. only into public/ ones.

comment:59 in reply to: ↑ 58 Changed 6 years ago by brett

Replying to dimpase:

Why do you think this is not optimal? This is a normal way to go. Surely if there already was public/16295 branch you'd rather pushed there. But there was none. You can't push into someone else's branch. only into public/ ones.

I thought that that if there was a way for me to write to the patch's branch then having to create another is inoptimal, but if this is how it works then that is no problem.

Last edited 6 years ago by brett (previous) (diff)

comment:60 in reply to: ↑ 54 Changed 6 years ago by dimpase

Replying to brett:

The Sage developers guide says "git trac puch" not "git push trac"

git trac means invoke git-trac git extension. (see http://github.com/sagemath/git-trac-command)

git push trac means do git's push to the remote named trac`.

(you can use git remote -v to see which remotes are set up for you)

here is what I get when I do it the right way around:

$ git push trac
Counting objects: 13, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 937 bytes, done.
Total 7 (delta 6), reused 0 (delta 0)
remote: FATAL: W refs/heads/u/ncohen/16295 sage brett DENIED by fallthru
remote: error: hook declined to update refs/heads/u/ncohen/16295
To git@trac.sagemath.org:sage.git
 ! [remote rejected] u/ncohen/16295 -> u/ncohen/16295 (hook declined)
error: failed to push some refs to 'git@trac.sagemath.org:sage.git'

surely, you can't push in an u/TRAC-USERNAME branch, that's why

comment:61 follow-up: Changed 6 years ago by brett

Nathann,

I think if MOLS people are going to be using this code then we should add the additional 2 columns in when a MOLS gets transformed to a OA. In that case all the error messages I have changed are correct and this is what MOLS people will expect

comment:62 in reply to: ↑ 61 ; follow-up: Changed 6 years ago by ncohen

Brett,

Here is the behaviour of your branch

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: m1 = matrix([[0,1,0],[2,0,1],[1,2,0]]) # not a latin square
sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]]) # not a latin square                                     
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True)                         
The row and column indices are not orthogonal
False
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])  # not a latin square
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])  # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2],verbose=True)
True
sage: a,b,c,d = designs.mutually_orthogonal_latin_squares(11,4)      
sage: are_mutually_orthogonal_latin_squares([a,b,c,d,d],verbose=True)
Squares 1 and 2 are not orthogonal
False

The index issues come from problem I mentionned in comment 51.

I think if MOLS people are going to be using this code then we should add the additional 2 columns in when a MOLS gets transformed to a OA. In that case all the error messages I have changed are correct and this is what MOLS people will expect

Here is what my branch u/ncohen/16295_v2 (mentionned in comment 50) does :

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: m1 = matrix([[0,1,0],[2,0,1],[1,2,0]]) # not a latin square
sage: m2 = matrix([[0,1,2],[1,2,0],[2,0,1]]) # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2], verbose=True) 
Matrix 0 is not row latin
False
sage: m1 = matrix([[0,0,0],[1,1,1],[2,2,2]])  # not a latin square
sage: m2 = matrix([[0,1,2],[0,1,2],[0,1,2]])  # not a latin square
sage: are_mutually_orthogonal_latin_squares([m1,m2],verbose=True)
Matrix 0 is not row latin
False
sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: a,b,c,d = designs.mutually_orthogonal_latin_squares(11,4)
sage: are_mutually_orthogonal_latin_squares([a,b,c,d,d],verbose=True)
Matrices 3 and 4 are not orthogonal
False

Our terminology is almost the same (we can replace "matrix" with "square" if you prefer). The interest of mine is that you do not have to add MOLS-specific code to the is_orthogonal_array function. Thus do you mind if we keep my version of the code to make are_mutually_orthogonal_squares correct and include your typo fix ?

Nathann

comment:63 in reply to: ↑ 62 ; follow-up: Changed 6 years ago by brett

Nathann,

I strongly feel that it would be much more consistent with

1) what people in design theory will expect the code to do

2) the equivalence between OAs and MOLS

to have are_mutually_orthogonal_squares add the two extra columns and then simply call is_orthogonal_array. This will have the effect of checking that all the squares are, in fact latin and you will not have to have are_mutually_orthogonal_squares do this extra checking.

in my opinion as a design theorist, the behaviour you cite in comment 62 of my code is all correct. In the second example the squares ARE orthogonal, they are just NOT latin. if you add the additional two columns the behaviour will be reported.

brett

comment:64 in reply to: ↑ 63 Changed 6 years ago by ncohen

Hello !

I strongly feel that it would be much more consistent with

1) what people in design theory will expect the code to do

You claim again that my code does something that somebody (a user ?) "in design theory" might not expect. Can you tell me what it is ? Or is the function okay for the user's point of view, while you think that the way it is coded is "something that people in design theory" would not expect ?

2) the equivalence between OAs and MOLS

to have are_mutually_orthogonal_squares add the two extra columns and then simply call is_orthogonal_array. This will have the effect of checking that all the squares are, in fact latin and you will not have to have are_mutually_orthogonal_squares do this extra checking.

I would have agreed if the function only returned True/False answer. What you are telling me to do is that I should consider all latins squares as k rows of a TD to which I add the two row/column ones, only to differentiate them later in a function that has no reason to contain MOLS-specific code.

This is why it does not make sense to me to build a homogeneous input only to dissassemble it immediately afterwards.

Besides, I expect that my commented code is sufficient for anybody "who does design theory" to understand what exactly happens.

in my opinion as a design theorist, the behaviour you cite in comment 62 of my code is all correct.

It is not. The function is named "are_mutually_orthogonal_latin_squares". It should return True if the input consists of mutually orthogonal latin squares.

In the second example the squares ARE orthogonal, they are just NOT latin. if you add the additional two columns the behaviour will be reported.

I agree with that, I am just showing that your branch returns wrong results. If this is fixed the results will be correct. This being said, if this is fixed then what you said just above, i.e. that the function should return True even when the input does not consist of latin squares, will not hold anymore. And so according to you the function will return wrong results.

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:65 Changed 6 years ago by ncohen

Two details that may help you decide :

1) The current behaviour of the are_mutually_orthogonal_latin_squares is to check that the latin squares are latin squares, and so changing that would mean changing the behaviour of the function

sage: from sage.combinat.designs.latin_squares import are_mutually_orthogonal_latin_squares
sage: are_mutually_orthogonal_latin_squares([Matrix([[1,1],[1,0]])])                       
False

2) All results returned by the constructors of mutually_orthogonal_latin_squares are checked using this function.. If it does not check whether the latin squares are orthogonal then we need to make sure that the output of our constructors are actually latin squares

Nathann

comment:66 Changed 6 years ago by ncohen

I updated my branch starting from u/ncohen/16295_v2 by adding your commit to it. I removed the "if" in is_orthogonal_array that only deal with MOLS input as this was already dealt with in are_mutually_orthogonal_latin_squares. This mixed version of our codes seems good to me...

Nathann

comment:67 Changed 6 years ago by git

  • Commit changed from 31e84b82913815b2005b5e2e45650c1568a45761 to b66a187a35ff81525f42ddf4d93611ec2bd9fb6b

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

6fb1f14trac #16295: Bugfix
1653790trac #16295: Merged with 6.3.beta3
b66a187fixed some small language typos and changed MOLS error messages into context that MOLS researchers will expect.

comment:68 Changed 6 years ago by ncohen

Brett ?

comment:69 Changed 6 years ago by vdelecroix

Hi Nathann,

We waited too long for that ticket and many tickets are depending on this one. For me the review is basically done as the function does what is specified.

I added one nice doctest at u/vdelecroix/16295... If you like it, set my branch to positive review otherwise set yours to positive review.

Vincent

comment:70 Changed 6 years ago by ncohen

  • Branch changed from u/ncohen/16295 to u/vdelecroix/16295
  • Commit changed from b66a187a35ff81525f42ddf4d93611ec2bd9fb6b to 02f12476967dd287ffb47e711098a5518efbddd2
  • Status changed from needs_review to positive_review

AHahahah. Funny doctest. I was actually thinking that "indeed, this function is used a LOT in the code, but that it is only tested on True instances. With your doctest, it makes it a bit more interesting than

def is_orthogonal_array(*args):
    return True

Thanks !

Nathann


New commits:

02f1247trac #16295: one more doctest

comment:71 Changed 6 years ago by ncohen

  • Reviewers set to Vincent Delecroix, Brett Stevens

comment:72 Changed 6 years ago by brett

OK,

I am (mostly) happy. What do I do to approve this patch?

brett

Last edited 6 years ago by brett (previous) (diff)

comment:73 Changed 6 years ago by vbraun

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