v3 is designed for lines of a million atoms, and could be made faster.
Henry Rich
On 2/14/2019 5:57 PM, Jose Mario Quintana wrote:
Comparisons based on solutions offered.
(Beware of line-wrapping!)
v0=. ~:@:({.@(/:~)@(i.@# |."0 1 ]) "1) NB. RH
v1=. ~:@:(([: {.@/:~ {:@$ [\ (, }:))"1) NB. REB
v2=. ~:@:((|.~ >:@(# -~ {: i. 1:)@((_1 |. ] #^:_1 (= <./)@#~)^:(1 <
+/@])^:a: 1"0))"1)
NB. LdF
v3=. ~:@:((|.~ canonshift=. 3 : 0)"1) NB. HR
NB. Try each atom of y until we find one that works
for_t. /:~ ~. y do.
NB. get spacing between positions of t, including the wraparound
cyclt =. 2 -~/\ tpos =. (, (#y) + {.) t I.@:= y
NB. if there is only 1 value, use its position
if. 1 = # cyclt do. {. tpos end.
NB. If all spacings are the same, try the next value
if. (}. -: }:) cyclt do. continue. end.
NB. Canonicalize cyclt. Use its result to canonicalize y
(canonshift cyclt) { tpos return.
end.
NB. No atom worked; must be abcabc...; canonize by moving smallest to front
(i. <./) y
)
v4=. ~:@:(({.@(/:~)@:(|."0 1~) (I.@:=<./))"1) NB. MD (sig1)
v5=. ~:@:(([: {. [: /:~ ] |."0 1~ ([: I. ] = <./) #~ [: (= <./) ] {~ [: <:
[: I. ] = <./)"1)
NB. MD (sig2)
stp=. ] (([ ((<;._1 '|Sentence|Space|Time|Space * Time') , (, */&.:>@:(1
2&{))@:(] ; 7!:2@:] ; 6!:2)&>) (10{a.) -.&a:@:(<;._2@,~) ]) [ (0 0 $
13!:8^:((0 e. ])`(12"_)))@:(2 -:/\ ])@:(".&.>)@:((10{a.) -.&a:@:(<;._2@,~)
]) ::(0 0&$@(1!:2&2)@:('Mismatch!'"_))) ".@:('0( : 0)'"_)
A=: ". 12 59 $ (0 : 0) -. CRLF
1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 _1 4 1
1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 1 4 _1 _1 4
1 4 4 1 _4 _1 _4 1 1 _4 _1 _4 _4 _1 4 1 4 _1 _1 4
4 1 1 4 _1 4 1 _4 _4 1 _4 _1 _1 _4 1 _4 _1 4 4 _1
4 1 1 4 _1 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
_1 4 1 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
_1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 1 4 _1
_1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 _1 4 1 1 4
_1 4 4 _1 _4 1 _4 _1 _1 _4 1 _4 _4 1 4 _1 4 1 1 4
4 _1 _1 4 1 4 _1 _4 _4 _1 _4 1 1 _4 _1 _4 1 4 4 1
4 _1 _1 4 1 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
1 4 _1 _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
)
JQt J807 (64 nonavx windows) performance results...
(v3 was excluded; otherwise, J crases (on v3 A)! Can anyone confirm?)
stp 111
v0 A
v1 A
v2 A
v4 A
v5 A
)
┌────────┬─────┬──────────┬────────────┐
│Sentence│Space│Time │Space * Time│
├────────┼─────┼──────────┼────────────┤
│ v0 A │15680│9.79728e_5│1.53621 │
├────────┼─────┼──────────┼────────────┤
│ v1 A │15680│4.4752e_5 │0.701711 │
├────────┼─────┼──────────┼────────────┤
│ v2 A │6016 │9.1532e_5 │0.550657 │
├────────┼─────┼──────────┼────────────┤
│ v4 A │7360 │4.14325e_5│0.304943 │
├────────┼─────┼──────────┼────────────┤
│ v5 A │6016 │5.29863e_5│0.318766 │
└────────┴─────┴──────────┴────────────┘
Corresponding J806 results...
(v3 is included.)
stp 111
v0 A
v1 A
v2 A
v3 A
v4 A
v5 A
)
┌────────┬─────┬──────────────┬────────────┐
│Sentence│Space│Time │Space * Time│
├────────┼─────┼──────────────┼────────────┤
│ v0 A │14336│0.000118566885│1.69977487 │
├────────┼─────┼──────────────┼────────────┤
│ v1 A │12160│5.34553436e_5 │0.650016979 │
├────────┼─────┼──────────────┼────────────┤
│ v2 A │11264│0.000124958141│1.4075285 │
├────────┼─────┼──────────────┼────────────┤
│ v3 A │18688│0.000427807898│7.99487399 │
├────────┼─────┼──────────────┼────────────┤
│ v4 A │7296 │4.23078038e_5 │0.308677736 │
├────────┼─────┼──────────────┼────────────┤
│ v5 A │6272 │5.04595455e_5 │0.31648227 │
└────────┴─────┴──────────────┴────────────┘
On Thu, Feb 14, 2019 at 11:27 AM 'Mike Day' via Programming <
[email protected]> wrote:
FWIW, slightly better and faster versions of my rushed efforts of
yesterday
NB. rotate each occurrence of minimum to front
sig1 =: {.@(/:~)@:(|."0 1~) (I.@:=<./)
NB. rotate each occurrence of minimum with minimum left neighbour
sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=<./) y{~ <: i =. I. y = <./ y'
Still not too elegant, but quite fast for the small example, a. Don’t
know about bigger arrays.
Mike
Sent from my iPad
On 14 Feb 2019, at 03:26, Roger Hui <[email protected]> wrote:
And what would you use if you need a noun? Normal form? Again, more of
a
mouthful.
Other terms I would use for identity problems, when explaining to laymen,
is "ID number". They usually get it immediately.
On Wed, Feb 13, 2019 at 6:55 PM Raul Miller <[email protected]>
wrote:
I like “normalize” personally.
The ideas I associate with “signature” are not robust enough for a
reliable
nub (and so would require additional care elsewhere).
If that matters...
Thanks,
—
Raul
On Wednesday, February 13, 2019, Roger Hui <[email protected]>
wrote:
In this context, I prefer words like signature or representative rather
than canonical form. Shorter and less scary and puts one's mind on the
right track in multiple problems.
e.g. What's a good representative for identity problems? ~. i. ]
(index
in nub). What's a good representative for ordering problems? (Seen a
couple of weeks ago.) /:~@, i.!.0 ] (ordinals).
On Wed, Feb 13, 2019 at 5:19 PM Henry Rich <[email protected]>
wrote:
This is what I was looking for. It works on REB's testcase but has
less
than quadratic run time I think.
NB. Get # left-shifts to canonicalize y
canonshift =: 3 : 0
NB. Try each atom of y until we find one that works
for_t. /:~ ~. y do.
NB. get spacing between positions of t, including the wraparound
cyclt =. 2 -~/\ tpos =. (, (#y) + {.) t I.@:= y
NB. if there is only 1 value, use its position
if. 1 = # cyclt do. {. tpos end.
NB. If all spacings are the same, try the next value
if. (}. -: }:) cyclt do. continue. end.
NB. Canonicalize cyclt. Use its result to canonicalize y
(canonshift cyclt) { tpos return.
end.
NB. No atom worked; must be abcabc...; canonize by moving smallest to
front
(i. <./) y
)
~: (|.~ canonshift)"1 a
1 1 1 1 1 0 1 1 1 1 1 0
The canonical form used here does not always put the smallest atom at
the
front, but I think it causes vector that differ only by a rotation to
canonicalize identically.
Henry Rich
On 2/13/2019 7:29 PM, Roger Hui wrote:
Idea k: a minimum vector necessarily begins with a minimum
sub-sequence
in
x,(k-1){.x of length k , itself necessarily begins with the minimal
item.
On Wed, Feb 13, 2019 at 9:52 AM Roger Hui <[email protected]
wrote:
Yes, well, left as an exercise for the reader. :-)
Idea: the minimum rotation of a vector necessarily begins with its
minimal
item.
On Wed, Feb 13, 2019 at 9:34 AM Henry Rich <[email protected]>
wrote:
Yes; but now suppose the lines are very long. Is there a way to
find
the signature (I would call it a canonical form) that doesn't
require
enumerating rotations? (I haven't found a good way yet).
Henry Rich
On 2/13/2019 12:16 PM, Roger Hui wrote:
For each row, find a "signature", then find the nub sieve of the
signatures. The signature I use here is the minimum of all
possible
rotations.
signature=: {. @ (/:~) @ (i.@# |."0 1 ])
~: signature"1 a
1 1 1 1 1 0 1 1 1 1 1 0
On Wed, Feb 13, 2019 at 8:55 AM R.E. Boss <[email protected]>
wrote:
Let the 12 x 20 matrix be defined by
a=: 0 : 0
1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1 _1 4 1
1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 1 4 _1 _1 4
1 4 4 1 _4 _1 _4 1 1 _4 _1 _4 _4 _1 4 1 4 _1 _1 4
4 1 1 4 _1 4 1 _4 _4 1 _4 _1 _1 _4 1 _4 _1 4 4 _1
4 1 1 4 _1 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
_1 4 1 1 4 4 1 _4 _4 1 1 _4 _1 _1 _4 _4 _1 4 4 _1
_1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1 1 4 _1
_1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 _1 4 1 1 4
_1 4 4 _1 _4 1 _4 _1 _1 _4 1 _4 _4 1 4 _1 4 1 1 4
4 _1 _1 4 1 4 _1 _4 _4 _1 _4 1 1 _4 _1 _4 1 4 4 1
4 _1 _1 4 1 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
1 4 _1 _1 4 4 _1 _4 _4 _1 _1 _4 1 1 _4 _4 1 4 4 1
)
Required is the nubsieve for the items modulo rotation.
So two arrays are considered to be equal if one is a rotation of
the
other.
The answer I found is
1 1 1 1 1 0 1 1 1 1 1 0
R.E. Boss
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
------------------------------------------------------------
----------
For information about J forums see
http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by AVG.
https://www.avg.com
------------------------------------------------------------
----------
For information about J forums see http://www.jsoftware.com/
forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
