稀疏

$. _ _ _

稀疏

$.y 轉換緊緻陣列為稀疏，相反地， $.^:_1 y 轉換稀疏陣列到緊緻。

大部分函數 f 下 f -: f&.$. 與f -: f&.($.^:_1)為等式，除了使用稀疏原子為填充者 (如 overtake {.)。 0$.y applies $. or $.^:_1 as appropriate; 亦即，converts a dense 陣列to 稀疏與a 稀疏陣列to dense.

1$.sh;a;e produces a 稀疏陣列. sh specifies shape. a specifies 稀疏 axes; negative 索引ing may be used. e specifies "zero" 分子,與its type determines type of 陣列. 引數may also be sh;a (e is assumed to be a floating point 0) or just sh (a is assumed to be i.#sh -- all axes are 稀疏 -- and e a floating point 0).

2$.y gives 稀疏 axes ( a part);
(2;a)$.y (re-)specifies 稀疏 axes; (2 1;a)$.ygives number of bytes required for (2;a)$.y; (2 2;a)$.ygives number of items in i part or x part for specified 稀疏 axes a (that is, #4$.(2;a)$.y).

3$.y gives 稀疏分子 ( e part); (3;e)$.yrespecifies 稀疏分子.

4$.y gives 索引矩陣( i part).

5$.y gives value 陣列( x part).

6$.y gives flag ( flag part).

7$.y gives number of non-稀疏 entries in 陣列 y;亦即， #4$.y or #5$.y.

8$.y removes any completely "zero" value框格與corresponding rows 在索引矩陣.

inverse of n&$. is (-n)&$. .

remainder of this text is divided into following sections: Introduction, Representation, Assertions, Furr Examples, Sparse Linear Algebra, and Implementation Status.

介紹

We describe a 稀疏陣列extension to J using a representation that "does not store zeros". One new 動詞 $. is defined to create與manipulate 稀疏陣列,與existing 基本單字 are extended to operate on such陣列. se ideas are illustrated in following examples:

   ] d=: (?. 3 4$2) * ?. 3 4$100
 0 75  0 53
 0  0 67 67
93  0 51 83

   ] s=: $. d                  轉換 d 到稀疏並指定給 s
0 1 | 75
0 3 | 53                       展示 s 得到「非零」框格的索引與其對應值
1 2 | 67                       
1 3 | 67
2 0 | 93
2 2 | 51
2 3 | 83

   d -: s                      d and s match
1

   o. s                        p times s
0 1 | 235.619
0 3 | 166.504
1 2 | 210.487
1 3 | 210.487
2 0 | 292.168
2 2 | 160.221
2 3 | 260.752

   o. d                        p times d
      0 235.619       0 166.504
      0       0 210.487 210.487
292.168       0 160.221 260.752

   (o. s) -: o. d              得到的函數與表達式獨立
1

   0.5 + o. s
0 1 | 236.119
0 3 | 167.004
1 2 | 210.987
1 3 | 210.987
2 0 | 292.668
2 2 | 160.721
2 3 | 261.252

   <. 0.5 + o. s
0 1 | 236
0 3 | 167
1 2 | 210
1 3 | 210
2 0 | 292
2 2 | 160
2 3 | 261

   (<. 0.5 + o. s) -: <. 0.5 + o. d
1

   d + s                       函數引數可為緊緻或者稀疏
0 1 | 150
0 3 | 106
1 2 | 134
1 3 | 134
2 0 | 186
2 2 | 102
2 3 | 166

   (d + s) -: 2*s              familiar algebraic properties are preserved
1

   (d + s) -: 2*d
1

   +/ s
0 |  93
1 |  75
2 | 118
3 | 203
   
   +/"1 s
0 | 128
1 | 134
2 | 227

   |. s                        reverse
0 0 | 93
0 2 | 51
0 3 | 83
1 2 | 67
1 3 | 67
2 1 | 75
2 3 | 53

   |."1 s
0 0 | 53
0 2 | 75
1 0 | 67
1 1 | 67
2 0 | 83
2 1 | 51
2 3 | 93

   |: s                        轉置
0 2 | 93
1 0 | 75
2 1 | 67
2 2 | 51
3 0 | 53
3 1 | 67
3 2 | 83

   $ |: s
4 3

   $.^:_1 |: s                 $.^:_1 轉換稀疏陣列成緊緻
 0  0 93
75  0  0
 0 67 51
53 67 83

   (|:s) -: |:d
1

   , s                         ravel; a 稀疏 向量
 1 | 75
 3 | 53
 6 | 67
 7 | 67
 8 | 93
10 | 51
11 | 83

   $ , s
12

Representation

A 稀疏陣列 y may be布林, 整數, floating point, complex, literal, or boxed,與has (internal) parts sh;a;e;i;x;flag where:

`sh`	Shape, `$y` . 分子 of shape must be less than `2^31` ,but product over shape may be大於 `2^31` .
`a`	Axe(s), a 向量 of排序ed 稀疏 (索引ed) axes.
`e`	Sparse 分子 ("zero"). `e` is also used as fill in any overtake of 陣列.
`i`	Indices, an 整數矩陣of indices for 稀疏 axes.
`x`	Values, a (dense) 陣列of usually non-zero框格 for non-稀疏 axes corresponding to 索引矩陣 `i` .
`flag`	各類bit flags.

For 稀疏矩陣 s used 在introduction,

   ] d=: (?. 3 4$2) * ?. 3 4$100
 0 75  0 53
 0  0 67 67
93  0 51 83
    
   ] s=: $. d
0 1 | 75
0 3 | 53
1 2 | 67
1 3 | 67
2 0 | 93
2 2 | 51
2 3 | 83

shape is 3 4 ; 稀疏 axes are 0 1 ; 稀疏分子 is 0; indices are first two columns of numbers 在display of s ;and values are last column.

純量仍然如之前的表達方式 (緊緻地)。所有的基本單字接受稀疏或緊緻陣列作為引數 (即， 稀疏+緊緻 或 稀疏$稀疏)。稀疏陣列的展示為索引矩陣的展示 ( i part), a blank column, a column of vertical lines, anor blank column,與 corresponding value框格 ( x part).

Letting 稀疏分子 be variable rather than fixed at zero makes 許多more 函數 closed on 稀疏陣列 (e.g. ^y or 10+y), and familiar results can be produced by familiar片語 (e.g. <.0.5+y for rounding to nearest 整數).

Assertions

以下 assertions成立於稀疏陣列，而展示一稀疏陣列invokes these consistency checks on it.

`imax =: _1+2^31`	最大內部整數
`rank =: #@$`	秩
`type =: 3!:0`	內部型態

`1 = rank sh`	向量
`sh -: <. sh`	積分
`imax >: #sh`	最多 `imax` 分子
`(0<:sh) *. (sh<:imax)`	介於 `0` 與 `imax`

`1 = rank a`	向量
`a e. i.#sh`	介於 `0` 與秩-1
`a -: ~. a`	分子為唯一
`a -: /:~ a`	排序

`0 = rank e`	原子ic
`(type e) = type x`	內部型態與 `x`的相同

`2 = rank i`	矩陣
`4 = type i`	積分
`(#i) = #x`	列數與 `x`的子項同
`({:$i) = #a`	行數與稀疏軸同
`(#i) <: */a{sh`	# rows 的界限為稀疏軸長度之積
`imax >: */$i`	# 分子的界限為 `imax`
`(0<:i) *. (i <"1 a{sh)`	`i` 介於 0與稀疏軸的長度
`i -: ~.i`	各列為唯一
`i -: /:~ i`	各列排序

`(rank x) = 1+(#sh)-#a`	秩等於 1 加上緊緻軸的個數
`imax >: */$x`	# 分子的界限為 `imax`
`(}.$x)-:((i.#sh)-.a){s`	子項形狀為緊緻軸的維度
`(type x) e. 1 2 4 8 16 32`	內部型態為布林、字元、整數、實數、複數或封裝

更多的範例

   ] d=: (0=?. 2 3 4$3) * ?. 2 3 4$100
13 0 0 0
21 4 0 0
 0 0 0 0

 3 5 0 0
 0 0 6 0
 0 0 0 0

   ] s=: $. d                  轉換 d 成稀疏並指定 s
0 0 0 | 13
0 1 0 | 21
0 1 1 |  4
1 0 0 |  3
1 0 1 |  5
1 1 2 |  6

   d -: s                      相配與表達方式獨立
1

   2 $. s                      稀疏軸
0 1 2

   3 $. s                      稀疏 分子
0

   4 $. s                      索引矩陣; 各行對應稀疏軸
0 1 0
0 1 1
1 0 0
1 0 1
1 1 2

   5 $. s                      對應值
13 21 4 3 5 6

   ] u=: (2;2)$.s              令 2 為稀疏軸
0 | 13 21 0
  |  3  0 0
  |        
1 |  0  4 0
  |  5  0 0
  |        
2 |  0  0 0
  |  0  6 0

   4 $. u                      索引矩陣
0
1
2

   5 $. u                      對應值
13 21 0
 3  0 0

 0  4 0
 5  0 0

 0  0 0
 0  6 0

   ] t=: (2;0 1)$.s            令 0 1 為稀疏軸
0 0 | 13 0 0 0
0 1 | 21 4 0 0
1 0 |  3 5 0 0
1 1 |  0 0 6 0

   7 {. t                      take
0 0 | 13 0 0 0
0 1 | 21 4 0 0
1 0 |  3 5 0 0
1 1 |  0 0 6 0

   $ 7 {. t
7 3 4

   7{."1 t                     take with rank
0 0 | 13 0 0 0 0 0 0
0 1 | 21 4 0 0 0 0 0
1 0 |  3 5 0 0 0 0 0
1 1 |  0 0 6 0 0 0 0

   0 = t
0 0 | 0 1 1 1
0 1 | 0 0 1 1
1 0 | 0 0 1 1
1 1 | 1 1 0 1

   3 $. 0 = t                  0=t的稀疏分子為 1
1

   +/ , 0 = t
18

   +/ , 0 = d                  答案與表達式獨立
18

   0 { t                       取自
0 | 13 0 0 0
1 | 21 4 0 0

   _2 (<1 2 3)}t               amend
0 0 | 13 0 0  0
0 1 | 21 4 0  0
1 0 |  3 5 0  0
1 1 |  0 0 6  0
1 2 |  0 0 0 _2

   s=: 1 $. 20 50 1000 75 366
   $ s                         20 個國家， 50 個地區， 1000 個業務員，
20 50 1000 75 366              75 種產品， 一年的366 個日子

   */ $ s                      形狀之積可以超過 2^31
2.745e10

   r=: ?. 1e5 $ 1e6            收益
   i=: ?. 1e5 5 $ $ s          對應區位
   s=: r (<"1 i)} s            指定收入到對應區位

   7 {. ": s                   展示 s 中的前7列
 0  0   5 30 267 | 128133      第一列描述國別 0，地區 0，
 0  0  26 20 162 | 319804      業務員 5，產品 30，日期 267，
 0  0  31 37 211 | 349445      收益為 128133
 0  0  37 10 351 | 765935
 0  0  56  6  67 | 457449
 0  0  66 54 120 |  38186
 0  0  71 74 246 | 515473

   +/ , s                      總收益
|limit error                   錯誤發生於 ,s 因為需要長度為2.745e10的向量
| +/    ,s                     

   +/@, s                      總收益
5.00289e10                     由特殊碼支援 f/@, 

   +/+/+/+/+/ s                總收益
5.00289e10

   +/^:5 s
5.00289e10

   +/^:_ s
5.00289e10

   +/ r
5.00289e10

   +/"1^:4 s                   各國之總收益
 0 | 2.48411e9
 1 | 2.55592e9
 2 | 2.55103e9
 3 | 2.52089e9
 4 | 2.49225e9
 5 | 2.45682e9
 6 | 2.52786e9
 7 | 2.45425e9
 8 | 2.48729e9
 9 | 2.50094e9
10 | 2.51109e9
11 | 2.59601e9
12 | 2.49003e9
13 | 2.58199e9
14 | 2.44772e9
15 | 2.47863e9
16 | 2.46455e9
17 |  2.5568e9
18 | 2.43492e9
19 | 2.43582e9

   t=: +/^:2 +/"1^:2 s         total revenue by salesperson

   $t
1000

   7{.t
0 | 4.58962e7
1 | 4.81548e7
2 | 3.97248e7
3 | 4.89981e7
4 | 4.85948e7
5 | 4.69227e7
6 | 4.22094e7

稀疏線性代數

目前，僅有稀疏矩陣乘法與tri-diagonal 線型方程組的解 are implemented。例如:

   f=: }. @ }: @ (,/) @ (,."_1 +/&_1 0 1) @ i.

   f 5                         indices for a 5 by 5 tri-diagonal矩陣
0 0
0 1
1 0
1 1
1 2
2 1
2 2
2 3
3 2
3 3
3 4
4 3
4 4

   s=: (?. 13$100) (<"1 f 5)} 1 $. 5 5;0 1
   $s
5 5

片語 1$.5 5;0 1 產生一個形狀為 5 5 與稀疏軸為 0 1 (在每一維度都稀疏)的稀疏陣列； <"1 f 5 產生封裝索引；而 x (<"1 f 5)}y amends by x locations in y indicated by indices (scattered amendment).

   s
0 0 | 13
0 1 | 75
1 0 | 45
1 1 | 53
1 2 | 21
2 1 |  4
2 2 | 67
2 3 | 67
3 2 | 93
3 3 | 38
3 4 | 51
4 3 | 83
4 4 |  3

   ] d=: $.^:_1 s              dense representation of s
13 75  0  0  0
45 53 21  0  0
 0  4 67 67  0
 0  0 93 38 51
 0  0  0 83  3

   ] y=: ?. 5$80
10 60 36 42 17

   y %. s
1.27885 _0.0883347 0.339681 0.202906 0.0529263

   y %. d                      answers are independent of representation
1.27885 _0.0883347 0.339681 0.202906 0.0529263

   s=: (?. (_2+3*1e5)$1000) (<"1 f 1e5)} 1 $. 1e5 1e5;0 1

   $ s                         s is a 1e5 by 1e5矩陣
100000 100000

   y=: ?. 1e5$1000

   ts=: 6!:2 , 7!:2@]          time與space for 執行

   ts 'y %. s'
0.28 5.2439e6                  0.28 seconds; 5.2 megabytes (Pentium 266 Mhz)

Implementation Status

As of 2000-12-01, following facilities support 稀疏陣列:

= d     =.      =: 
<       <.      <: 
>       >.      >: 
_       _.      _:

+       +.      +:
*       *.      *:
-       -. m    -:
%       %. d    %:

^       ^.
$ m     $.      $:
~               ~: d
|       |.      |:

        ..      .:
:       :.      ::
,       ,.      ,:

#
!       !.      !:
/ m
\ m     \. m 

[       [.      [:
]       ].
{ d     {.      {:
} d     }.      }:

"       ".       ": m
`                `:
@       @.       @:
&       &.       &:

j. m
o.
r. m
_9: to 9:

3!:0 
3!:1
3!:2
3!:3
4!:55

Notes:

Sparse literal與boxed 陣列not yet implemented.
雙邊 %. only implements case of triadiagonal 矩陣s.
Boxed左引數for |: (diagonal slices) not yet implemented.
單邊 f/ and f/"r are only implemented for + * >. <. +. *. = ~: , (and only 布林引數for = and ~:); on an axis of length 2, 單邊 f/ and f/"r are implemented for any 函數.
單邊 f/@, (and f/@:, and f/&, andf/&:,)are supported by 特殊碼.
{ and } only accept following 索引引數: 整數陣列, <"1 on 整數陣列,與scalar boxed indices (respectively, item 索引ing, scattered 索引ing,與索引 lists a0;a1;a2;...).

下個 • 前個 • 字彙 • 索引 • 主選單