{"id":1856,"date":"2015-04-13T10:25:25","date_gmt":"2015-04-13T10:25:25","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=1856"},"modified":"2015-04-13T10:29:52","modified_gmt":"2015-04-13T10:29:52","slug":"exploring-key","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2015\/04\/exploring-key\/","title":{"rendered":"Exploring Key"},"content":{"rendered":"

In \u237a f\u2338 \u2375<\/code>, major cells of \u237a<\/code> specify keys for the corresponding major cells of \u2375<\/code>, and f<\/code> applies to each unique major cell of \u237a<\/code> and the major cells of \u2375<\/code> having that key. The monadic case f\u2338\u2375<\/code> is equivalent to \u2375 f\u2338 \u2373\u2262\u2375<\/code>. Key<\/em> is similar to the GROUP BY clause in SQL.<\/p>\n

For example:<\/p>\n

   \u2395io\u21900\r\n\r\n   (\u237311) ,[\u00af0.5] 'Mississippi'\r\n0 1 2 3 4 5 6 7 8 9 10\r\nM i s s i s s i p p  i\r\n\r\n   {\u237a}\u2338'Mississippi'                 {\u237a\u2375}\u2338'Mississippi'\r\nMisp                              \u250c\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\r\n                                  \u2502M\u25020       \u2502\r\n   {\u2282\u2375}\u2338'Mississippi'             \u251c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u250c\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2510          \u2502i\u25021 4 7 10\u2502\r\n\u25020\u25021 4 7 10\u25022 3 5 6\u25028 9\u2502          \u251c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n\u2514\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2518          \u2502s\u25022 3 5 6 \u2502\r\n                                  \u251c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2524\r\n   {\u2262\u2375}\u2338'Mississippi'             \u2502p\u25028 9     \u2502\r\n1 4 4 2                           \u2514\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\r\n<\/code><\/pre>\n
We illustrate key<\/em> by using it to model some APL primitives and to motivate and solve a programming puzzle.<\/p>\n
Index-Of and Friends<\/h2>\n
Since key<\/em> is defined in terms of unique<\/em> and indices, we expect to be able to effect members of the index-of<\/em> family. And so we can.<\/p>\n
The specifications say that f<\/code> applies to each unique major cell of \u237a<\/code>. Therefore, {\u237a}\u2338<\/code> and equivalently \u22a3\u2338<\/code> computes unique<\/em>. Since the specifications are for unique major cells<\/em>, these are what \u222a\u2375<\/code> would be if it were extended to non-vector arguments, analagous to the way \u2373<\/code> was extended to non-vector left arguments.<\/p>\n
   x\u2190\u2191'Aspen' 'John' 'Susan' 'Roger' 'Opal' 'John' 'Aspen'\r\n   x\r\nAspen\r\nJohn \r\nSusan\r\nRoger\r\nOpal \r\nJohn \r\nAspen\r\n\r\n   {\u237a}\u2338x                  \u22a3\u2338x\r\nAspen                  Aspen\r\nJohn                   John \r\nSusan                  Susan\r\nRoger                  Roger\r\nOpal                   Opal \r\n<\/code><\/pre>\n
A little surprisingly, key<\/em> can also be used to model extended index-of<\/em> and extended membership<\/em>. For reasons which will become clear, we model \u220d<\/code> (AKA \u220a\u2368<\/code>) instead of \u220a<\/code>. Both models use the merge<\/em> operator<\/a>, whimsically denoted here by \u2192<\/code>.<\/p>\n
ix  \u2190 {(\u2262\u237a) \u2193 (0\u2374\u2368(\u2262\u237a)+\u2262\u2375) ((\u220ai)\u2192)\u2368 (\u2262\u00a8i)\/(\u2262\u237a)\u230a\u2283\u00a8i\u2190{\u2282\u2375}\u2338\u237a\u236a\u2375}\r\nhas \u2190 {(\u2262\u237a) \u2193 (0\u2374\u2368(\u2262\u237a)+\u2262\u2375) ((\u220ai)\u2192)\u2368 (\u2262\u00a8i)\/(\u2262\u237a)>\u2283\u00a8i\u2190{\u2282\u2375}\u2338\u237a\u236a\u2375}\r\n\r\n   y\u2190\u2191'China' 'Susan' 'John' 'John' 'Anne' 'Roger'\r\n   y\r\nChina\r\nSusan\r\nJohn \r\nJohn \r\nAnne \r\nRoger\r\n\r\n   x ix y\r\n7 2 1 1 7 3\r\n\r\n   x has y\r\n0 1 1 1 0 1\r\n<\/code><\/pre>\n
To focus on essentials, ix<\/code> and has<\/code> 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 {\u2191,\u2282\u2364(\u00af1+\u2374\u2374\u237a)\u22a2\u2375}<\/code> and post-application of ((1-\u2374\u2374\u237a)\u2193\u2374\u2375)\u2374<\/code>.<\/p>\n
Partition<\/h2>\n
Since key<\/em> 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:<\/p>\n
   part \u2190 {(+\\b\/\u237a){\u2282\u2375}\u2338b\u233f\u2375\u22a3b\u2190\u2228\\\u237a}\r\n\r\n   x\r\nAspen\r\nJohn \r\nSusan\r\nRoger\r\nOpal \r\nJohn \r\nAspen\r\n   0 1 0 1 0 0 1 part x\r\n\u250c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2510\r\n\u2502John \u2502Roger\u2502Aspen\u2502\r\n\u2502Susan\u2502Opal \u2502     \u2502\r\n\u2502     \u2502John \u2502     \u2502\r\n\u2514\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2518\r\n   0 1 0 1 0 0 1 (\u2282[0] \u2261 part) x\r\n1\r\n   (7\u23740) (\u2282[0] \u2261 part) x\r\n1\r\n<\/code><\/pre>\n
Sort and Grade<\/h2>\n
sort  \u2190 {\u237a\u233f\u2368\u00af1+{\u2262\u2375}\u2338\u237a\u236a\u2375}\r\ngrade \u2190 {(\u2262\u237a)-\u2368\u220a1\u2193\u00a8{\u2282\u2375}\u2338\u237a\u236a\u2375}\r\n<\/code><\/pre>\n
If \u2375<\/code> is an array from a small \u201calphabet\u201d \u237a<\/code>, then \u237a sort \u2375<\/code> sorts \u2375<\/code> and \u237a grade \u2375<\/code> grades it. For example:<\/p>\n
   x\u2190?1e6\u2374256                        a\u2190\u2395a[?1e6\u237426]\r\n\r\n   (\u234bx)  \u2261 (\u2373256) grade x            (\u234ba)  \u2261 \u2395a grade a\r\n1                                 1\r\n   x[\u234bx] \u2261 (\u2373256) sort  x            a[\u234ba] \u2261 \u2395a sort  a\r\n1                                 1\r\n<\/code><\/pre>\n
The Maximum of a Vector<\/h2>\n
In Dyalog ’13 session D11<\/a>, I included a slide giving relative timings on the then new key<\/em> operator:<\/p>\n
x\u2190?1e6\u23741000\r\n\r\na. \u00af1+{\u2262\u2375}\u2338(\u23731000),x     1.00\r\nb. \u00af1+{\u2262\u2375}\u2338(\u23731+\u2308\/x),x    1.62\r\nc. ...\r\n<\/code><\/pre>\n
The timings show that key<\/em> with tally<\/em> 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?<\/p>\n
max=*x++; \r\nfor(i=1;i<n;++i){if(max<*x)max=*x; ++x;}\r\n<\/code><\/pre>\n
I posed the puzzle to some expert C programmers, and they failed to solve it. An \u201cobvious\u201d solution obtains by considering an obvious implementation of {\u2262\u2375}\u2338x<\/code> in C:<\/p>\n
M=256;\r\nmemset(c,0,M*4);              \/\/ initialize table of counts\r\nfor(i=0;i<n;++i)c[*x++]++;    \/\/ analoguous to c[x]+\u21901 <\/tt>in APL\r\n<\/pre>\n
Therefore, one way to find the maximum of x is to have an M-element (byte) Boolean table b, and:<\/p>\n
memset(b,0,M);\r\nfor(i=0;i<n;++i)b[*x++]=1;    \/\/ analoguous to b[x]\u21901 <\/tt>in APL\r\nc=b+M;                        \/\/ scan from the back\r\nfor(i=0;i<M;++i)if(*--c){max=c-b; break;}\r\n<\/pre>\n
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<\/code>-loop, the time for which dominates the overall time, is simpler for the table method.<\/p>\n
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<\/em>, the index-of family, grade, and sort.<\/p>\n","protected":false},"excerpt":{"rendered":"
In \u237a f\u2338 \u2375, major cells of \u237a specify keys for the corresponding major cells of \u2375, and f applies to each unique major cell of \u237a and the major cells of \u2375 having that key. The monadic case f\u2338\u2375 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-1856","post","type-post","status-publish","format-standard","hentry","category-apl-language"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1856","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=1856"}],"version-history":[{"count":11,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions"}],"predecessor-version":[{"id":2486,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/1856\/revisions\/2486"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=1856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=1856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=1856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}