When you use a word like 'best' you are saying a lot. For problems
known to be small, the easiest-to-understand would be my pick. I was
interested in a version that would have good worst-case performance on
big problems. Try
canonize 1e6$0 1
and see how the algorithms compare on that test.
hhr
On 2/25/2019 1:26 PM, R.E. Boss wrote:
To complete the comparison, canonize is twice as efficient as the best solution
before (sigi of de Forcrand).
ts'canonize 1000 (?.@$~ 10^])7'
0.36269515 2.6845101e8
R.E. Boss
-----Oorspronkelijk bericht-----
Van: Programming <[email protected]>
Namens Henry Rich
Verzonden: zondag 24 februari 2019 19:03
Aan: [email protected]
Onderwerp: Re: [Jprogramming] nubsieve modulo rotation
J807-c, just now released, fixes the crash that my script detected. I have a
better version now anyway, given below.
Sample run:
canonize 1e6 $ 0 1
0 1 0 1 0 1...
Henry Rich
NB. Get # left-shifts to canonicalize y
canonnub =: ~:@:canonize =: ((|.~ canonshift =: 3 : 0)"1)
NB. Try each atom of y, in ascending order, until we find one that works
lowvalues =. 0$0 NB. In case no recursion possible, remember the first value
with the lowest frequency
for_t. /:~ ~. y do.
NB. Get the positions occupied by t. If they are more than half the
positions, skip t since it won't make much progress
if. (#y) < +: # tpos =. t I.@:= y do. continue. end.
NB. If there is only 1 position, it is the shift amount - return it
if. 1 = # tpos do. {. tpos return. end.
NB. get spacing between positions of t, including the wraparound
cyclt =. 2 -~/\ (, (#y) + {.) tpos
NB. If not all spacings are the same, recur on the positions of t to find a
canonical rotation
if. (}. -.@-: }:) cyclt do. (canonshift cyclt) { tpos return. end.
NB. All the distances between t values are the same. There is nothing to
choose between them. Try the next input value,
NB. but remember a shift value for the input that had the smallest
frequency
if. (#tpos) < {.!._ lowvalues do. lowvalues =. (# , {.) tpos end.
end.
NB. No atom worked; must be aaaa... or abcabc...; canonize by moving
smallest to front
{: lowvalues NB. 0 if all values identical
)
On 2/21/2019 12:41 PM, 'Mike Day' via Programming wrote:
Have I missed an update, then?
Thanks,
Mike
Sent from my iPad
On 21 Feb 2019, at 16:58, Henry Rich <[email protected]> wrote:
The crash should be fixed in the latest released version, but I
haven't verified that.
Henry Rich
On Thu, Feb 21, 2019, 5:40 AM 'Mike Day' via Programming <
[email protected]> wrote:
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
---
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
