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
