Home First Encounter Current Status GNU License Downloads Getting Started Examples Mississippi Overview of A Structure of Data Syntax Relation to other APLs Language Reference System Fns and Vars Functions Where next Quibbles Materials Vector Home |
The “Mississippi” challenge from Vector 18.2This example is taken directly from Norman Thomson's J-ottings column in Vector 18.2. It is an interesting comparison of the speed of the 'obvious' outer-product solution and a very sneaky algorithm using upward ranking. ã The Mississippi challenge (from Vector 18.2 - Jottings) ã The object is to take a vector and return the occurrence number for each element s û 'mississippi' ã The boring way with an outer product nub v: { ((vÉv)=ÉÒv)/v } unq û nub s tbl û unq Ê.= s ã Cum across and save where we had numbers tbl û tbl « +\@1 tbl oc û ¢1++/tbl 'The answer is ',îoc ã Make it a function so we can time it ... oca s : { tbl û (nub s)Ê.=s ; tbl û tbl « +\@1 tbl; (+/tbl)-1} ã Now for the super-sneaky approach (J-forum written up in Vector) t û (sÉunq)[unqÉs] r û èèt occ û r-r[t] 'The answer is also ',îocc ã Get a little nearer the J style using index ... t û (unqÉs)#sÉunq r û èèt occ û r-t#r 'The answer is still ',îocc ã Finally as a function ocb s: { uûnub s; tû(uÉs)#sÉu; rûèèt; r-t#r } ' oca s ã tests the boring one' ' ocb s ã tests the sneaky version' ' ' 'Try some timings with various sized arrays ...' ' time qq := ocb 500000 rho s ã Arthur wrote a mean gradeup here!' The timings are interesting, when we run this in A+ and in the two major Windows APLs:
The significant line is the bottom one which supports the claim in Jonathan Barman's first impressions of A - that sorting is impressively fast. This set of timings is definitely curving downwards, so the elapsed time is less than linear with the size of the array, which is very impressive.
© British APL Association 2001 Please send any comments to Adrian Smith via adrian@causeway.co.uk - thank you. |