The A Project->Getting Started->Mississippi
Mississippi
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.2

This 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: { ((vv)=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  (sunq)[unqs]
 r  t
 occ  r-r[t]

'The answer is also ',occ

 Get a little nearer the J style using index ...
 t  (unqs)#sunq
 r  t
 occ  r-t#r

'The answer is still ',occ 

 Finally as a function
 ocb s: { unub s; t(us)#su; rt; 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:

Timings in various APLs


The outer-product solution is actually the faster of the two algorithms in both Dyalog and +Win, but it runs out of memory fairly quickly in my standard setup of 20M. In A+ it shows very comparable timings, but of course you now have 'infinite' memory as A+ will just grab swapfile on your hard-drive as it needs to allocate space for ever bigger arrays.

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.


Back to Top

© British APL Association 2001
Please send any comments to Adrian Smith via adrian@causeway.co.uk - thank you.