Sorry - it looks like a line-wrap problem - a comment line absorbed a
couple
of successors!
Here's another attempt, with forced double line spacing:
sig3 =: 3 : 0
b =. (,.~) y
'm n' =. $y
bool =. m#1
for_pad. }.i.<: m do.
'a b' =. ({.;}.) b
if. bool{~<:pad do. NB. no need if already done
if. +/ i =. (n {.a) (+/@:E.)"1 b do.
bool =. 0 (pad + I.i) } bool
end.
end.
end.
bool
)
As I said, it's not particularly attractive in space or time - that
might improve
when the nub is small with respect to the whole, but I'm looking at
something
else right now.
Thanks for pointing out the problem,
Cheers,
Mike
On 24/02/2019 10:59, R.E. Boss wrote:
sig3 does not work:
|control error
| [10]end.
| sig3_MD=:3 :0
|[-59] f:\j\user\necklaces.ijs
After deleting the last 'end'-statement, I got, with
a=:_4 _4 _1 4 1 4 _1 _1 4 1 4 4 1 _4 _4 1 1 _4 _1 _1
sig3 a
|noun result was required: sig3_MD
| bool{~<:pad
I finally found time to implement a solution I came up last week Here I first
checked some trivial cases, which otherwise would cost you a lot of time.
sig_REB=: (|.~ 3 : 0)"1
NB. check on constant array
if. 1=#~. y do. 1 return. end.
NB. check on rep array
t=.I.t0=.(=<./) y
if. -:/ y|.~"_ 0 [2 {.t do. {.t return. end.
NB. check on unique consecutive subarrray of minimals if. (#= 1+{:-{.)t do.
{.t return. end.
NB. other cases
b=.1
c=.#y
while. 1<#t do.
t=.t#~(-:"(1) 0({/:~)]) y{~ c|((+ i.)b)+"1 0 t
NB. t=.t{~ >{.(({</.[)~/:) y{~ c|((+ i.)b)+"1 0 t
b=.2*b
end.
t
)
I compared my solution with sigb_LdF and sigi_Ldf of Louis de Forcrand and
sig1_MD and sig2_MD of Mike Day.
Obviously the special cases are easy to win, but they also revealed a bug in
sigi_LdF.
1 ( #~ 10^]) 7 NB. List of 1e7 constants
100 (i.@[ $~ 10^]) 7 NB. Periodic list
1000 (?.@$~ 10^]) 7 NB. Random list
Lists of constants:
ts'sigb_LdF 1(#~10^])3' NB. sigb of Louis de Forcrand
0.0094511174 14272
ts'sigb_LdF 1(#~10^])4'
0.69180282 85952
ts'sigi_LdF 1(#~10^])3' NB. sigi of Louis de Forcrand
|length error: sigi_LdF
| sigi_LdF 1(#~10^])3
ts'sig1_MD 1(#~10^])3' NB. sig1 of Mike Day
0.0030407711 1077696
ts'sig1_MD 1(#~10^])4'
0.3157129 1.3462982e8
ts'sig2_MD 1(#~10^])4' 3' NB. sig2 of Mike Day
0.41906069 2.684537e8
ts'sig_REB 1(#~10^])7'
0.03058715 33556480
Periodic lists:
ts'sigb_LdF 100 (i.@[ $~ 10^]) 4'
0.37122401 413120
ts'sigi_LdF 100 (i.@[ $~ 10^]) 4'
|length error: sigi_LdF
| sigi_LdF 100(i.@[$~10^])4
ts'sig1_MD 100(i.@[$~10^])4'
0.010147822 8654592
ts'sig1_MD 100(i.@[$~10^])5'
1.7994755 1.07585e9
ts'sig2_MD 100(i.@[$~10^])5'
2.5281331 2.1485343e9
ts'sig_REB 1000 (i.@[ $~ 10^]) 7'
0.45120097 5.537831e8
Random lists
ts'sigb_LdF 1000 (?.@$~ 10^]) 7'
0.98856202 4.1943392e8
ts'sigi_LdF 1000 (?.@$~ 10^]) 7' NB. Overall most efficient
0.70114667 4.0265696e8
ts'sig1_MD 100 (?.@$~ 10^])4'
0.017409918 16913024
ts'sig1_MD 100 (?.@$~ 10^])5'
2.3799804 2.1485513e9
ts'sig2_MD 1000 (?.@$~ 10^])6'
0.070785475 25168768
ts'sig2_MD 1000 (?.@$~ 10^])7'
2.6975198 2.2817036e9
ts'sig_REB 1000 (?.@$~ 10^])7'
0.71293484 6.8800032e8
R.E. Boss
-----Oorspronkelijk bericht-----
Van: Programming <[email protected]>
Namens 'Mike Day' via Programming
Verzonden: donderdag 21 februari 2019 11:40
Aan: [email protected]
Onderwerp: Re: [Jprogramming] nubsieve modulo rotation
Back to this thread...
I've worked up an explicit variant, sig3, using I. and E. - fairly
simple-minded,
but might be of interest. Also revisiting sig1 for comparison. sig3 is not so
good for
space, but is reasonably fast for the example.
NB. minmd =: (({.@:/:~)`(<./)@.(0-:{.@:(0&{.)))
minmd =: {.@:/:~ NB. this works for strings as well as numeric arrays
sig1 =: {.@(/:~)@:(|."0 1~) (I.@:= minmd)
NB. rotate each occurrence of minimum pair to front
sig2 =: 13 : '{./:~ y |."0 1~ i#~ (=minmd) y {~ <: i =. I. y = minmd y'
sig3 =: 3 : 0
b =. (,.~) y
NB. following replaces values by characters - assuming nub is small enough!
NB. but it doesn't appear to save space!
NB. b =. (,.~) ((~.@:,) (a.{~i.) ]) y 'm n' =. $y bool =. m#1 for_pad.
}.i.<: m
do.
'a b' =. ({.;}.) b
if. bool{~<:pad do.
if. +/ i =. (n {.a) (+/@:E.)"1 b do.
bool =. 0 (pad + I.i) } bool
end.
end.
end.
bool
)
ts'~:sigb a'
0.000348269 6656
ts'~:sigi a'
0.000235419 6272
ts'~:sig3 a'
0.000233799 13248
ts'~:sig1"1 a'
0.000106371 7680
Also, I can confirm that Henry's canonical shift crashes this version of Jqt
JVERSION
Engine: j807/j64/windows
Release-b: commercial/2019-01-22T18:51:16
Library: 8.07.22
Qt IDE: 1.7.9/5.9.6
Platform: Win 64
Installer: J807 install
InstallPath: c:/d/j807
Contact: www.jsoftware.com
Cheers,
Mike
On 16/02/2019 17:52, [email protected] wrote:
I rewrote two explicit and perhaps clearer versions of my sig verb. Both
work on the same principle as the original, but one uses a bit vector and the
other uses a list of indices, and the indices are a bit faster (pun probably
intended). I prefer the bit vector aesthetically though.
Both basically store the set of indices where possible lexicographically
minimal rotations could start (b and i in the verbs). On iteration n, the
starting
index of rotations whose nth element is not minimal among the nth
elements of all possibly minimal rotations are removed from the
aforementioned set. The iteration continues until only one possible rotation
is left, and for a maximum of #y times, in which case all elements of y are
identical and so any rotation will do.
If I am not mistaken (I might be, have to hurry and go now), since there are
a maximum of #y iterations and each includes at most #y comparisons (= <./),
the number of comparisons is at worst quadratic in the length of y. This
happens when 1=#~.y, but most of the time this number is much smaller.
sigb=: (|.~ 3 : 0)"1
b=. 1"0 y
for. y do.
if. 1 = +/b do. break. end.
b=. (= <./)&.(b&#) y
y=. 1|.y
end.
b i. 1
)
sigi=: (|.~ 3 : 0)"1
i=. i.#y
for. y do.
if. 1 = #i do. break. end.
i=. i ((= <./)@:{ # [) y
y=. 1|.y
end.
i
)
Cheers,
Louis
----------------------------------------------------------------------
For information about J forums see
http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
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
