In ⍺ f⌸ ⍵, major cells of ⍺ specify keys for the corresponding major cells of ⍵, and f applies to each unique major cell of ⍺ and the major cells of ⍵ having that key. The monadic case f⌸⍵ is equivalent to ⍵ f⌸ ⍳≢⍵. Key is similar to the GROUP BY clause in SQL.
For example:
⎕io←0
(⍳11) ,[¯0.5] 'Mississippi'
0 1 2 3 4 5 6 7 8 9 10
M i s s i s s i p p i
{⍺}⌸'Mississippi' {⍺⍵}⌸'Mississippi'
Misp ┌─┬────────┐
│M│0 │
{⊂⍵}⌸'Mississippi' ├─┼────────┤
┌─┬────────┬───────┬───┐ │i│1 4 7 10│
│0│1 4 7 10│2 3 5 6│8 9│ ├─┼────────┤
└─┴────────┴───────┴───┘ │s│2 3 5 6 │
├─┼────────┤
{≢⍵}⌸'Mississippi' │p│8 9 │
1 4 4 2 └─┴────────┘
We illustrate key by using it to model some APL primitives and to motivate and solve a programming puzzle.
Index-Of and Friends
Since key is defined in terms of unique and indices, we expect to be able to effect members of the index-of family. And so we can.
The specifications say that f applies to each unique major cell of ⍺. Therefore, {⍺}⌸ and equivalently ⊣⌸ computes unique. Since the specifications are for unique major cells, these are what ∪⍵ would be if it were extended to non-vector arguments, analagous to the way ⍳ was extended to non-vector left arguments.
x←↑'Aspen' 'John' 'Susan' 'Roger' 'Opal' 'John' 'Aspen'
x
Aspen
John
Susan
Roger
Opal
John
Aspen
{⍺}⌸x ⊣⌸x
Aspen Aspen
John John
Susan Susan
Roger Roger
Opal Opal
A little surprisingly, key can also be used to model extended index-of and extended membership. For reasons which will become clear, we model ∍ (AKA ∊⍨) instead of ∊. Both models use the merge operator, whimsically denoted here by →.
ix ← {(≢⍺) ↓ (0⍴⍨(≢⍺)+≢⍵) ((∊i)→)⍨ (≢¨i)/(≢⍺)⌊⊃¨i←{⊂⍵}⌸⍺⍪⍵}
has ← {(≢⍺) ↓ (0⍴⍨(≢⍺)+≢⍵) ((∊i)→)⍨ (≢¨i)/(≢⍺)>⊃¨i←{⊂⍵}⌸⍺⍪⍵}
y←↑'China' 'Susan' 'John' 'John' 'Anne' 'Roger'
y
China
Susan
John
John
Anne
Roger
x ix y
7 2 1 1 7 3
x has y
0 1 1 1 0 1
To focus on essentials, ix and has do not directly handle the case where the right argument has higher rank than the left argument (the principal argument). Such higher rank arguments can be handled by pre-application of {↑,⊂⍤(¯1+⍴⍴⍺)⊢⍵} and post-application of ((1-⍴⍴⍺)↓⍴⍵)⍴.
Partition
Since key can effect non-contiguous partitions, we expect to be able to use it to effect contiguous partitions, a special case of the former. And so we can:
part ← {(+\b/⍺){⊂⍵}⌸b⌿⍵⊣b←∨\⍺}
x
Aspen
John
Susan
Roger
Opal
John
Aspen
0 1 0 1 0 0 1 part x
┌─────┬─────┬─────┐
│John │Roger│Aspen│
│Susan│Opal │ │
│ │John │ │
└─────┴─────┴─────┘
0 1 0 1 0 0 1 (⊂[0] ≡ part) x
1
(7⍴0) (⊂[0] ≡ part) x
1
Sort and Grade
sort ← {⍺⌿⍨¯1+{≢⍵}⌸⍺⍪⍵}
grade ← {(≢⍺)-⍨∊1↓¨{⊂⍵}⌸⍺⍪⍵}
If ⍵ is an array from a small “alphabet” ⍺, then ⍺ sort ⍵ sorts ⍵ and ⍺ grade ⍵ grades it. For example:
x←?1e6⍴256 a←⎕a[?1e6⍴26]
(⍋x) ≡ (⍳256) grade x (⍋a) ≡ ⎕a grade a
1 1
x[⍋x] ≡ (⍳256) sort x a[⍋a] ≡ ⎕a sort a
1 1
The Maximum of a Vector
In Dyalog ’13 session D11, I included a slide giving relative timings on the then new key operator:
x←?1e6⍴1000
a. ¯1+{≢⍵}⌸(⍳1000),x 1.00
b. ¯1+{≢⍵}⌸(⍳1+⌈/x),x 1.62
c. ...
The timings show that key with tally takes less than a factor of 2 over finding the maximum. This is fast; unbelievably fast even. The following puzzle arose from investigations into this timing: Find the maximum of a vector of unsigned 1-byte integers without using multicore, vector instructions, loop unrolling, etc. Can you do it faster in C than the following?
max=*x++;
for(i=1;i<n;++i){if(max<*x)max=*x; ++x;}
I posed the puzzle to some expert C programmers, and they failed to solve it. An “obvious” solution obtains by considering an obvious implementation of {≢⍵}⌸x in C:
M=256; memset(c,0,M*4); // initialize table of counts for(i=0;i<n;++i)c[*x++]++; // analoguous to c[x]+←1 in APL
Therefore, one way to find the maximum of x is to have an M-element (byte) Boolean table b, and:
memset(b,0,M);
for(i=0;i<n;++i)b[*x++]=1; // analoguous to b[x]←1 in APL
c=b+M; // scan from the back
for(i=0;i<M;++i)if(*--c){max=c-b; break;}
Timing show that the table method is faster than the comparison method by a factor of 1.5 for 1-byte integers and 1.3 for 2-byte integers. The table method requires more code, but the main n-loop, the time for which dominates the overall time, is simpler for the table method.
Jay Foad countered that finding the maximum (and the minimum) is much faster still with the vector instructions available in modern CPUs. Dyalog has now (version 14.1) implemented such finding, with performance benefits for key, the index-of family, grade, and sort.
Follow