The A Project->Getting Started->Mississippi
Mississippi
Home
First Encounter
Current Status
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: { ((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

ã 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]

ã Get a little nearer the J style using index ...
t û (unqÉs)#sÉunq
r û èèt
occ û r-t#r

ã 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 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.