このテキストのこれからの部分は、6つの章からなる。すなわち、1.イントロ、2.表現、3.主張(証明)、4.追加例、5.疎線形代数、6.インプリステータスである。
1.イントロ
J言語の疎配列拡張について、"ゼロを含まない"表現を用いて説明する。$.(ドルドット、スパース)という新しい動詞を定義するが、既存の原始動詞も疎配列に対応するよう拡
張する。考え方は下記の例をみて頂きたい。
] d=: (?. 3 4$2) * ?. 3 4$100 0 55 79 0 0 39 0 57 0 0 0 0 ] s=: $. d NB.dを疎配列に変換しsに代入する NB.sを表示すると、"ゼロでない"セルのインデックスと対応する値が示される 0 1 | 55 0 2 | 79 1 1 | 39 1 3 | 57 d -: s NB.dとsは≡する 1 o. s NB.パイをd倍してみる 0 1 | 172.788 0 2 | 248.186 1 1 | 122.522 1 3 | 179.071 o. d NB.パイをd倍してみる 0 172.788 248.186 0 0 122.522 0 179.071 0 0 0 0 (o. s) -: o. d NB.関数の結果は表現に左右されない 1 0.5 + o. s 0 1 | 173.288 0 2 | 248.686 1 1 | 123.022 1 3 | 179.571 <. 0.5 + o. s 0 1 | 173 0 2 | 248 1 1 | 123 1 3 | 179 (<. 0.5 + o. s) -: <. 0.5 + o. d 1 d + s NB.関数の引数は密行列でも疎行列もOk 0 1 | 110 0 2 | 158 1 1 | 78 1 3 | 114 (d + s) -: 2*s NB.通常の代数的性質は保持される 1 (d + s) -: 2*d 1 +/ s 1 | 94 2 | 79 3 | 57 +/"1 s 0 | 134 1 | 96 |. s NB.逆 1 1 | 39 1 3 | 57 2 1 | 55 2 2 | 79 |."1 s 0 1 | 79 0 2 | 55 1 0 | 57 1 2 | 39 |: s NB.トランスポーズ 1 0 | 55 1 1 | 39 2 0 | 79 3 1 | 57 $ |: s 4 3 $.^:_1 |: s NB.$.^:_1は疎配列を密配列に変換する 0 0 0 55 39 0 79 0 0 0 57 0 (|:s) -: |:d 1 , s NB.,(カンマ、ラベル)は疎配列ベクトルに作用する 1 | 55 2 | 79 5 | 39 7 | 57 $ , s 12
2.表現
疎配列のyはブール型、整数、浮動少数、複素数、リテラル、ボックスであり得る。その(内部)性質としてsh;a;e;i;xという部分を持つ。それぞれの意味は下記の通り。
sh シェイプ$yである。シェイプの要素数は2^31以下でなければならないが、そお積は2^31以上であってもかまわない a 軸(axe)。(インデックスされた)疎の軸のベクトル e スパースの要素(“ゼロ”)。eは配列のオーバーテイクにおいてフィルとしても用いられる i インデックス。疎軸のインデックスの整数マトリックス x バリュー。通常インデックスマトリックスiに対応する非疎軸のための非ゼロのセルの(密)配列
イントロで使われた疎マトリックスsについて下記のようになる。
] d=: (?. 3 4$2) * ?. 3 4$100 0 55 79 0 0 39 0 57 0 0 0 0 ] s=: $. d 0 1 | 55 0 2 | 79 1 1 | 39 1 3 | 57
シェイプは3 4である。疎軸は0 1。疎要素は0。インデックスはsの表示において最初の1列のインデックスである。バリューは最後の列である。
スカラーは(密として)変化しない形で表現される。すべての原始動詞は引数として疎配列も密配列も受け付ける(たとえば疎配列+密配列、疎配列$疎配列など)。疎配列の
表示はインデックスマトリックス(i部分),空の列、縦棒の列、再度空の列、そして対応するバリューセル(x部分)からなる。
疎要素ををゼロに固定しない変数とするとさまざまな関数が疎配列に使えなくなる(たとえば^yや10+y)、また(たとえば<.0.5+yを四捨五入に使うなど)の慣れ親しんだフレ
ーズが使えなくなる。
3.主張(証明)
下記の主張が疎配列において成立する。疎配列を表示することにより、これらのことが確認される。
imax =: _1+2^31 NB.内部整数の最大値 rank =: #@$ NB.ランク type =: 3!:0 NB.内部タイプ 1 = rank sh NB.ベクトル sh -: <. sh NB.インテグラル imax >: #sh NB.ほとんどのimax要素において (0<:sh) *. (sh<:imax) NB.範囲0とimax 1 = rank a NB.ベクトル a e. i.#sh NB.範囲0とランクマイナス1(rank-1) a -: ~. a NB.要素はユニークである a -: /:~ a NB.ソートされた 0 = rank e NB.アトミック (type e) = type x NB.xと同じ内部タイプである 2 = rank i NB.マトリックス 4 = type i NB.インテグラル (#i) = #x NB.xの要素数と同じだけの行数 ({:$i) = #a as NB.素軸の数と同じだけの列数 (#i) <: */a{sh NB.疎軸の長さの積を範囲とする行数 imax >: */$i NB.imaxを範囲とする要素数 (0<:i) *. (i <"1 a{sh) NB.0と疎軸の長さを範囲とするi i -: ~.i NB行はユニークである i -: /:~ i NB.行はソートされている (rank x) = 1+(#sh)-#a NB.ランクは1に密軸の数を足したものに等しい imax >: */$x NB.要素数はimaxを範囲とする (}.$x)-:((i.#sh)-.a){s NB.アイテムのシェイプは密軸に対応する要素のシェイプである (type x) e. 1 2 4 8 16 32 NB.内部タイプはブール型、文字、整数、実数、複素数、またはボックスである
4.追加例
] d=: (0=?. 2 3 4$3) * ?. 2 3 4$100 46 0 0 0 0 39 0 0 0 0 46 0 0 0 0 0 0 60 0 62 0 0 60 64 ] s=: $. d NB.dを疎配列に変換しsに代入する 0 0 0 | 46 0 1 1 | 39 0 2 2 | 46 1 1 1 | 60 1 1 3 | 62 1 2 2 | 60 1 2 3 | 64 d -: s NB.表現に関係なくマッチする 1 2 $. s NB.疎軸 0 1 2 3 $. s NB.疎要素 0 4 $. s NB.インデックスマトリックス、疎軸に対応する列 0 0 0 0 1 1 0 2 2 1 1 1 1 1 3 1 2 2 1 2 3 5 $. s NB.バリューに対応 46 39 46 60 62 60 64 ] u=: (2;2)$.s NB.疎軸を2とする 0 | 46 0 0 | 0 0 0 | 1 | 0 39 0 | 0 60 0 | 2 | 0 0 46 | 0 0 60 | 3 | 0 0 0 | 0 62 64 4 $. u NB.インデックスマトリックス 0 1 2 3 5 $. u NB.対応するバリュー 46 0 0 0 0 0 0 39 0 0 60 0 0 0 46 0 0 60 0 0 0 0 62 64 ] t=: (2;0 1)$.s NB.0 1を疎軸とする 0 0 | 46 0 0 0 0 1 | 0 39 0 0 0 2 | 0 0 46 0 1 1 | 0 60 0 62 1 2 | 0 0 60 64 7 {. t NB.テイク 0 0 | 46 0 0 0 0 1 | 0 39 0 0 0 2 | 0 0 46 0 1 1 | 0 60 0 62 1 2 | 0 0 60 64 $ 7 {. t 7 3 4 7{."1 t NB.ランクによるテイク 0 0 | 46 0 0 0 0 0 0 0 1 | 0 39 0 0 0 0 0 0 2 | 0 0 46 0 0 0 0 1 1 | 0 60 0 62 0 0 0 1 2 | 0 0 60 64 0 0 0 0 = t 0 0 | 0 1 1 1 0 1 | 1 0 1 1 0 2 | 1 1 0 1 1 1 | 1 0 1 0 1 2 | 1 1 0 0 3 $. 0 = t NB.0=t疎要素は1 1 +/ , 0 = t 17 +/ , 0 = d NB.答えは表現にかかわらず一定 17 0 { t NB.フロム 0 | 46 0 0 0 1 | 0 39 0 0 2 | 0 0 46 0 _2 (<1 2 3)}t NB.アメンド 0 0 | 46 0 0 0 0 1 | 0 39 0 0 0 2 | 0 0 46 0 1 1 | 0 60 0 62 1 2 | 0 0 60 _2 s=: 1 $. 20 50 1000 75 366 $ s NB.20カ国、50地域、1000セールスパーソン 20 50 1000 75 366 NB.75製品、366日/年 */ $ s NB.シェイプの積は2^31以上でも大丈夫 2.745e10 r=: ?. 1e5 $ 1e6 NB.収入 i=: ?. 1e5 5 $ $ s NB.対応するロケーション s=: r (<"1 i)} s NB.収入を対応するロケーションいアサインする 7 {. ": s NB.sの表示における最初の7行 0 0 20 48 150 | 395543 NB.the first row says that for country 0, region 0, 0 0 39 40 67 | 316198 NB.salesperson 20, product 48, day 150, 0 0 47 37 172 | 650782 NB.the revenue was 395543 0 0 52 32 358 | 789844 0 0 54 62 82 | 923413 0 0 67 17 103 | 567367 0 0 91 13 295 | 470919 +/ , s NB.total revenue
| limit error NB.the expression failed on ,s because it would |
| +/ ,s NB.have required a vector of length 2.745e10 |
5.疎線形代数
Sparse Linear Algebra
Currently, only sparse matrix multiplication and the solutions of tri-diagonal linear system are
implemented. For example:
f=: }. @ }: @ (,/) @ (,."_1 +/&_1 0 1) @ i. f 5 NB.indices for a 5 by 5 tri-diagonal matrix 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 The phrase 1$.5 5;0 1 makes a sparse array with shape 5 5 and sparse axes 0 1 ; <"1 f 5 makes boxed indices; and x (<"1 f 5)}y amends by x the locations in y indicated by the indices (scattered amendment). s 0 0 | 46 0 1 | 55 1 0 | 79 1 1 | 52 1 2 | 54 2 1 | 39 2 2 | 60 2 3 | 57 3 2 | 60 3 3 | 94 3 4 | 46 4 3 | 78 4 4 | 13 ] d=: $.^:_1 s NB.the dense representation of s 46 55 0 0 0 79 52 54 0 0 0 39 60 57 0 0 0 60 94 46 0 0 0 78 13 ] y=: ?. 5$80 66 75 79 52 54 y %. s 0.352267 0.905377 0.00169115 0.764716 _0.434452 y %. d NB.answers are independent of representation 0.352267 0.905377 0.00169115 0.764716 _0.434452 s=: (?. (_2+3*1e5)$1000) (<"1 f 1e5)} 1 $. 1e5 1e5;0 1 $ s NB.s is a 1e5 by 1e5 matrix 100000 100000 y=: ?. 1e5$1000 ts=: 6!:2 , 7!:2@] NB.time and space for execution ts 'y %. s' 0.0550291 5.24358e6 NB.0.056 seconds; 5.2 megabytes (Pentium III 500 Mhz) 6.インプリメンテーション・ステータス As of 2005-12-17, the following facilities support sparse arrays: = =. =: < d <. <: > >. >: _ _. _: + +. +: * *. *: - -. -: % %. d %: ^ ^. $ $. $: ~ ~. ~: | |. |: .. .: : :. :: , ,. ,: ;. # ! !. !: / m /. d /: m \ m \. m \: m [ [: ] { d {. {: } d }. }: " ". ": m ` `: @ @. @: & &. &: e. d i. i: j. o. r. _9: to 9: 3!:0 3!:1 3!:2 3!:3 4!:55
| < |
| :(たてぼうコロン、パイプコロン,対角切片)の左側ボックス引数はまだインプリされていない。 |
