Differences between revisions 1 and 2
Revision 1 as of 2010-01-23 22:08:30
Size: 2919
Editor: KaiJaeger
Comment:
Revision 2 as of 2010-01-23 22:11:23
Size: 3706
Editor: KaiJaeger
Comment:
Deletions are marked like this. Additions are marked like this.
Line 7: Line 7:
{{{
                                      ?
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 13:
 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 16:
 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 20:
 For example: For example:
Line 23: Line 22:
 +\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 28:
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 30:
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 36:
 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 39:
 -\?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 42:
 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 46:
 ÷\?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 49:
 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 53:
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 57:
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 60:
 {?+?}\?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 63:
 {?+?}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 66:
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 69:
 {?-?}\?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 72:
 {?-?}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 75:
 nums??('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')     nums← ↑('one' 'two' 'three')('un' 'deux' 'trois')('yan' 'tan' 'tethera')
Line 69: Line 77:
}}}     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

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)