Differences between revisions 1 and 4 (spanning 3 versions)
Revision 1 as of 2010-01-23 22:08:30
Size: 2919
Editor: KaiJaeger
Comment:
Revision 4 as of 2010-01-23 22:11:44
Size: 3705
Editor: KaiJaeger
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
#acl AutoAdminGroup:read,write,delete,revert,admin KaiJaeger:read,write,delete,revert StephenTaylor:read,write,delete,revert All:read #acl KaiJaeger:read,write,delete,revert,admin PhilLast:read,write,delete,revert,admin All:read
Line 4: Line 4:

Example "!ScanOperator"
Line 8: Line 10:
                                      ? Variations on primitive scan:
 nvec?{axis}##.mscan nvec ? Minus scan.
 nvec?{axis}##.dscan nvec ? Divide scan.
 vect?(fn ##.ascan)vect ? Associative vector scan.
 array?{ascan}(fn ##.ascana)array ? Associative higher rank scan.
                                                ⍝ Variations on primitive scan:
 nvec ← {axis}      ##.mscan   nvec ⍝ Minus scan.
 nvec ← {axis}      ##.dscan   nvec ⍝ Divide scan.
 vect ← (fn ##.ascan)  vect ⍝ Associative vector scan.
array ← {ascan} (fn ##.ascana) array        ⍝ Associative higher rank scan.
Line 14: Line 16:
 Provided by Phil Last and Nicolas Delcros,these operators out-perform their
 primitive counterparts by scanning cumulatively from left to right.
Provided  by  Phil Last  and  Nicolas Delcros, these operators out-perform their
primitive counterparts by scanning cumulatively from left to right.
Line 17: Line 19:
 The primitive scan operator is defined as a vector of reductions:
 ¯¯¯¯¯¯¯¯¯
 ??\? ? ??/¨(1 to??)?¨??
The primitive scan operator is defined as a vector of reductions:
    ¯¯¯¯¯¯¯¯¯
    ⍺⍺\ → ⍺⍺/¨(1 to ⍴⍵)¨⊂⍵
Line 21: Line 23:
 For example: For example:
Line 23: Line 25:
 +\3 1 4 1 6
 ? +/¨(1 to 5)?¨?3 1 4 1 6
 ? +/¨(3)(3 1)(3 1 4)(3 1 4 1)(3 1 4 1 6)
 ? (+/3)(+/3 1)(+/3 1 4)(+/3 1 4 1)(+/3 1 4 1 6)
 ? 3 4 8 9 15
    +\3 1 4 1 6
+/¨(1 to 5)¨3 1 4 1 6
+/¨(3)(3 1)(3 1 4)(3 1 4 1)(3 1 4 1 6)
(+/3)(+/3 1)(+/3 1 4)(+/3 1 4 1)(+/3 1 4 1 6)
3 4 8 9 15
Line 29: Line 31:
Defn: An associative dyadic function f is one where:(A f B)f C ?? A f(B f C). Defn: An associative dyadic function f is one where: (A f B) f C ←→ A f (B f C).
Line 31: Line 33:
For associative operand functions,such as + and ×, the interpreter can "cheat" by accumulating the result in a single left-to-right pass of the vector argument, but for non-associative functions, it is obliged to do it the slow way using reductions of increasingly longer sequences as above, resulting in an O(n×n) algorithm. For  associative operand functions, such as + and ×, the interpreter can "cheat"
by  accumulating  the result in a single left-to-right pass of the vector argu-
ment, but for non-associative functions, it is obliged to do it the slow way us-
ing reductions of increasingly longer sequences as above, resulting in an O(n×n)
algorithm.
Line 33: Line 39:
 Mscan and dscan provide linear O(n)functions to simulate-\and÷\respectively. Mscan  and dscan provide linear O(n) functions to simulate -\ and ÷\ respective-
ly.
Line 35: Line 42:
 -\?1000 ? slow primitive minus-scan.
 1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...
      -\1000 slow primitive minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...
Line 38: Line 45:
 mscan?1000  ? quick minus-scan.
 1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...
      mscan ⍳1000 quick minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...
Line 42: Line 49:
 ÷\?1000 ? slow primitive divide-scan.
 1 0.5 1.5 0.375 1.875 0.3125 ...
      ÷\1000 slow primitive divide-scan.
1 0.5 1.5 0.375 1.875 0.3125 ...
Line 45: Line 52:
 dscan?1000  ? quick divide-scan.
 1 0.5 1.5 0.375 1.875 0.3125 ...
      dscan ⍳1000 quick divide-scan.
1 0.5 1.5 0.375 1.875 0.3125 ...
Line 49: Line 56:
In general, the interpreter can "cheat" only if it can determine that scan's operand function is associative. For example, even though dfn{?+?} is clearly associative, the interpreter cannot know this and so uses the slow O(n×n) method. In general, the interpreter can "cheat" only if it can determine that scan's op-
erand function is associative. For example, even though dfn {+} is clearly as-
sociative,  the interpreter cannot know this and so uses the slow O(n×n) method.
Line 51: Line 60:
In cases such as these, where it is known that the operand function is associative, ascan can be used to force a left-to-right cumulative O(n) scan. In cases such as these, where it is known that the operand function is associat-
ive, ascan can be used to force a left-to-right cumulative O(n) scan.
Line 53: Line 63:
 {?+?}\?10000 ? slow primitive scan.
 1 3 6 10 15 21 28 36 45 55 ...
      {+}\10000 slow primitive scan.
1 3 6 10 15 21 28 36 45 55 ...
Line 56: Line 66:
 {?+?}ascan?1000 ? quick associative scan.
 1 3 6 10 15 21 28 36 45 55 ...
      {+}ascan1000 quick associative scan.
1 3 6 10 15 21 28 36 45 55 ...
Line 59: Line 69:
Note that if the operand turns out to be non-associative, ascan will return a result that differs from primitive scan. Note  that  if  the operand turns out to be non-associative, ascan will return a
result that differs from primitive scan.
Line 61: Line 72:
 {?-?}\?10 ? slow primitive scan.
 1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5
      {-}\10 slow primitive scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5
Line 64: Line 75:
 {?-?}ascan?10 ? quick left to right accumulation.
 1 ¯1 ¯4 ¯8 ¯13 ¯19 ¯26 ¯34 ¯43 ¯53
      {-}ascan10 quick left to right accumulation.
1 ¯1 ¯4 ¯8 ¯13 ¯19 ¯26 ¯34 ¯43 ¯53
Line 67: Line 78:
 nums??('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')     nums← ↑('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')
Line 69: Line 80:
    disp {⍺,'-',⍵} ascan nums ⍝ left-to-right scan along rows
┌→──┬───────┬───────────────┐
↓one│one-two│ one-two-three │
├──→┼──────→┼──────────────→┤
│un │un-deux│ un-deux-trois │
├──→┼──────→┼──────────────→┤
│yan│yan-tan│yan-tan-tethera│
└──→┴──────→┴──────────────→┘

This is a read-only-page

Example "ScanOperator"

These operators where posted by John Scholes on November the 4th 2006 on Dyalog's web site:

                                                ⍝ Variations on primitive scan:
 nvec ← {axis}      ##.mscan   nvec             ⍝ Minus scan.
 nvec ← {axis}      ##.dscan   nvec             ⍝ Divide scan.
 vect ←         (fn ##.ascan)  vect             ⍝ Associative vector scan.
array ← {ascan} (fn ##.ascana) array            ⍝ Associative higher rank scan.

Provided  by  Phil Last  and  Nicolas Delcros, these operators out-perform their
primitive counterparts by scanning cumulatively from left to right.

The primitive scan operator is defined as a vector of reductions:
    ¯¯¯¯¯¯¯¯¯
    ⍺⍺\⍵  →  ⍺⍺/¨(1 to ⍴⍵)↑¨⊂⍵

For example:

    +\3 1 4 1 6
→   +/¨(1 to 5)↑¨⊂3 1 4 1 6
→   +/¨(3)(3 1)(3 1 4)(3 1 4 1)(3 1 4 1 6)
→   (+/3)(+/3 1)(+/3 1 4)(+/3 1 4 1)(+/3 1 4 1 6)
→   3 4 8 9 15

Defn: An associative dyadic function f is one where: (A f B) f C ←→ A f (B f C).
         ¯¯¯¯¯¯¯¯¯¯¯
For  associative operand functions, such as + and ×, the interpreter can "cheat"
by  accumulating  the  result in a single left-to-right pass of the vector argu-
ment, but for non-associative functions, it is obliged to do it the slow way us-
ing reductions of increasingly longer sequences as above, resulting in an O(n×n)
algorithm.

Mscan  and dscan provide linear O(n) functions to simulate -\ and ÷\ respective-
ly.

      -\⍳1000                       ⍝ slow primitive minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...

      mscan ⍳1000                   ⍝ quick minus-scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5 ...


      ÷\⍳1000                       ⍝ slow primitive divide-scan.
1 0.5 1.5 0.375 1.875 0.3125 ...

      dscan ⍳1000                   ⍝ quick divide-scan.
1 0.5 1.5 0.375 1.875 0.3125 ...


In general, the interpreter can "cheat" only if it can determine that scan's op-
erand function is associative. For example, even though dfn {⍺+⍵} is clearly as-
sociative,  the interpreter cannot know this and so uses the slow O(n×n) method.

In cases such as these, where it is known that the operand function is associat-
ive, ascan can be used to force a left-to-right cumulative O(n) scan.

      {⍺+⍵}\⍳10000                  ⍝ slow primitive scan.
1 3 6 10 15 21 28 36 45 55 ...

      {⍺+⍵}ascan⍳1000               ⍝ quick associative scan.
1 3 6 10 15 21 28 36 45 55 ...

Note  that  if  the operand turns out to be non-associative, ascan will return a
result that differs from primitive scan.

      {⍺-⍵}\⍳10                     ⍝ slow primitive scan.
1 ¯1 2 ¯2 3 ¯3 4 ¯4 5 ¯5

      {⍺-⍵}ascan⍳10                 ⍝ quick left to right accumulation.
1 ¯1 ¯4 ¯8 ¯13 ¯19 ¯26 ¯34 ¯43 ¯53

    nums← ↑('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')

    disp {⍺,'-',⍵} ascan nums       ⍝ left-to-right scan along rows
┌→──┬───────┬───────────────┐
↓one│one-two│ one-two-three │
├──→┼──────→┼──────────────→┤
│un │un-deux│ un-deux-trois │
├──→┼──────→┼──────────────→┤
│yan│yan-tan│yan-tan-tethera│
└──→┴──────→┴──────────────→┘

ScanOperator (last edited 2010-01-23 22:11:44 by KaiJaeger)