I would guess the categorizing solution to be O(n), and the sorting
solution to be O(n log n), but indeed, the sorting solution seems to be
faster for all n:
timespacex '(2 + i.15) zzc"0 _ [40000000$text'
12.0779 3.0954e9
timespacex '(2 + i.15) zzc2"0 _ [40000000$text'
6.14795 2.41592e9
Is Key implemented with a sort? Could it be optimized so that it is
faster for large n? Maybe there is some other explanation? The
performance relation is 2/1 for all n which strongly indicates the
solutions use the same sort, as I see it.
Cheers,
Erling
On 2016-09-28 22:11, Henry Rich wrote:
No, I think your sort version is much cleaner. It does the job of
;@:(</.) in my code.
Combining the ideas would give
zzc2 =: (] /: #@] $ ((] , -) i.)@<:@[)
which you could make work on x=1 if you like.
Henry Rich
On 9/28/2016 9:08 AM, Erling Hellenäs wrote:
Hi all !
Thanks!
Here with two versions of Henrys algorithm which handles the 1 line
case. Performance is the same for all three.
Henrys solution is elegant and more J:ish than my sort version I
think. Old APL style algorithms like my sort version still often
perform better.
NB. Erling
ZigZagE=:([: /: ] (([: $ [) $ ]) [: (], [: |. [: }: }.) [: i. [) { ]
NB. Mike
start =: i.@(<. #)
nstep =: (0 >. (-~ #)) >.@% <:@[
diffs =: (,:~ |.)@:+:@start
tconvert =: (]{~(#@])([-.~~.@:<.) ,@|:@(+/\)@ (start, nstep $diffs))
NB. Henry Rich
zzc =: (#@] $ ((] , -) i.)@<:@[) ;@:(</.) ]
NB. Henry Rich Erling rewrite
zzcE1=:(([: # ]) $ [: ([: (], [: |. [: }: }.) i.) [) ;@:(</.) ]
zzcE2=:(#@:] $ ((], |.@:}:@:}.)@:i.)@:[) ;@:(</.) ]
NB. just an arbitrary long string
text=.'THISISJUSTSOMERANDOMSENTENCEFORTESTINGTHEZIGZAGPROBLEMSOLUTIONSTHISISJUSTSOMERANDOMSENTENCEFORTESTINGTHEZIGZAGPROBLEMSOLUTIONSTHISISJUSTSOMERANDOMSENTENCEFORTESTINGTHEZIGZAGPROBLEMSOLUTIONSTHISISJUSTSOMERANDOMSENTENCEFORTESTINGTHEZIGZAGPROBLEMSOLUTIONS'
NB. do 15 zigzags
timespacex '(2 + i.15) tconvert"0 _ text' NB. see Mike Day's solution
0.000174903 33664
timespacex '(2 + i.15) zzc"0 _ text'
0.000121448 24576
timespacex '(2 + i.15) ZigZagE"0 _ text'
6.2007e_5 17536
timespacex '(2 + i.15) zzcE1"0 _ text'
0.000114606 24576
timespacex '(2 + i.15) zzcE2"0 _ text'
0.00011204 24576
((2 + i.15) tconvert"0 _ text) -: (2 + i.15) zzc"0 _ text
1
((2 + i.15) tconvert"0 _ text) -: (2 + i.15) ZigZagE"0 _ text
1
((2 + i.15) tconvert"0 _ text) -: (2 + i.15) zzcE1"0 _ text
1
((2 + i.15) tconvert"0 _ text) -: (2 + i.15) zzcE2"0 _ text
1
1 ZigZagE 'PAYPALISHIRING'
PAYPALISHIRING
1 zzcE1 'PAYPALISHIRING'
PAYPALISHIRING
1 zzcE2 'PAYPALISHIRING'
PAYPALISHIRING
Cheers,
Erling
On 2016-09-28 14:14, 'Mike Day' via Programming wrote:
Whoosh!
It even works ok with larg = 1 !
Good stuff,
Mike
On 28/09/2016 11:58, Erling Hellenäs wrote:
ZigZagE=:([: /: ] (([: $ [) $ ]) [: (], [: |. [: }: }.) [: i. [) { ]
----------------------------------------------------------------------
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
