狠狠撸

多次元配列の効率的
利用法の検討
uyuutosa
1

Agenda
1. 注意事項
2. Pythonについて
3. Pythonで大量データを利用する上手の課題
4. 効率的な演算規則及びプログラムの開発
2

1. 注意事項
この資料の中では著者の勝手な理解に基づいた内
容が多く含まれており、かつそれらに関しての真
偽に関しては詳細に調査を行っておりません。こ
の資料を参考にして生じた損害に関しては著者は
一切責任を負わないことをここに明記いたしま
す。
従いまして、本資料の内容は話半分に聞いていた
だけると幸いです。
3

? Pythonとは、オランダ人のグイド?ヴァンロッ
サムによって開発された、プログラミング言語
? 可読性が高い
? モジュールが豊富
? Zen of Python
wikipediaより引用
5

Pythonは禅
The Zen of Python, by Tim Peters
Beautiful is better than ugly.
醜いより美しいほうがいい。
Explicit is better than implicit.
暗示するより明示するほうがいい。
Simple is better than complex.
難解であるよりは平易であるほうがいい。
Complex is better than complicated.
複雑であるよりは難解であるほうがいい。
Flat is better than nested.
ネストは浅いほうがいい。
Sparse is better than dense.
密集しているよりは間があるほうがいい。
Readability counts.
読みやすいことは善である。
6

Special cases aren't special enough to break the rules.
特殊であることはルールを破る理由にならない。
Although practicality beats purity.
しかし、実用性を求めると自然さが失われることがある。
Errors should never pass silently.
エラーは隠すな、無視するな。
Unless explicitly silenced.
ただし、わざと隠されているのなら見逃せ。
In the face of ambiguity, refuse the temptation to guess.
曖昧なものに出ったら、その意味を適当に推測してはいけない。
There should be one-- and preferably only one --obvious way to do it.
たったひとつの冴えたやりかたがあるはずだ。
Although that way may not be obvious at ?rst unless you're Dutch.
そのやり方は一目見ただけではわかりにくいかもしれない。オランダ人にだ
けわかりやすいなんてこともあるかもしれない。
Now is better than never.
ずっとやらないでいるよりは、今やれ。
7

Although never is often better than right now.
でも、今"すぐ"にやるよりはやらないほうがマシなことが多い。
If the implementation is hard to explain, it's a bad idea.
コードの内容を説明するのが難しいのなら、それは悪い実装で
ある。
If the implementation is easy to explain, it may be a good idea.
コードの内容を容易に説明できるのなら、おそらくそれはよい
実装である。
Namespaces are one honking great idea -- let's do more of
those!
名前空間は優れたアイデアであるため、積極的に利用すべきで
ある。
http://qiita.com/IshitaTakeshi/items/e4145921c8dbf7ba57ef
8

Numpyについて
? NumPyは、プログラミング言語Pythonにおいて数値計算を効率的に
行うための拡張モジュール
? 効率的な数値計算を行うための型付きの多次元配列（例えばベクトル
や行列などを表現できる）のサポートをPythonに加えるとともに、そ
れらを操作するための大規模な高水準の数学関数ライブラリを提供
? NumPyの祖先であるNumericはJum Huguninらによって開発され
た。その後2005年にTravis Oliphantが、Numarrayの機能をNumeric
に組み込み、そこへ大幅な修正を加えることで、NumPyを開発した。
wikipediaより引用。
Pythonで数値計算をするために(多分)必須。
9

Numpyのndarray
使用例
のときは?
from numpy import *
x = arange(30)
1 + x
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29])
定数を配列に対し加減乗除できる。
10

使用例
In[]: sin(x)
Out[]:
array([ 0. , 0.84147098, 0.90929743, 0.14112001, -0.7568025 ,
-0.95892427, -0.2794155 , 0.6569866 , 0.98935825, 0.41211849,
-0.54402111, -0.99999021, -0.53657292, 0.42016704, 0.99060736,
0.65028784, -0.28790332, -0.96139749, -0.75098725, 0.14987721,
0.91294525, 0.83665564, -0.00885131, -0.8462204 , -0.90557836,
-0.13235175, 0.76255845, 0.95637593, 0.27090579, -0.66363388])
全配列に同様の処理をするUniversal functionが提
供されている。
11

使用例
In []: where(x > 10, 2, 0)
Out[]:
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2])
条件で分岐する関数にも対応
→?以上、数式通りに記述できる
12

(自分が考える)数式通りに書けることのメリット
1. 数式をプログラムに翻訳する労力が減る
2. 減った労力を別の事に使える(当然)
13

数式通りに記述できない例 - パーセプ
トロン
~ # 省略
~
w0 = array([0,0,0])
while 1:
~ # 省略
~
# 予測が不正解なら，パラメータを更新する
if predict != t_n:
w += t_n * phi(x_n, y_n)
misses += 1
# 予測が外れる点が無くなったら学習終了(ループを抜ける)
if misses == 0:
break
∵計算を更新する際に、一つ前の計算結果を利用している。
→ 一度に計算出来ない → Python上でイテレーションしなくてはならない。
→ Pythonはインタプリタなので、大量のループを回すと重い。
※sklearn.linear_model.Perceptron既存の提供されているライブラリを使えば速い。
14

3. Pythonで大量データを
利用する上での課題
15

? Pythonでループを使用すると重い。
? 特にndarrayはiterable属性を持っているため、for文にコンテナとして渡すことができる
が、list型と比べ重い(らしい)。
{なぜなら???} ← 未検討
{どれくらい???} ← 未検討
→ 従って、大量のデータをPythonでイテレーションするのははばかられる。
? 考えられる解決策
1. cython やBoostPython等の、pythonをC言語化したりC++/Cの関数やクラスをPythonでラ
ッピングする。← それらの習得が必要でかつコーディング作業が増大。
2. Scipy、Sympy等の外部モジュールを使う。←提供されていないアルゴリズムに対応できな
い。
? 外部モジュールや他言語に依存せず、ハンドリングに優れたndarrayで提供している演算規
則のみで複雑で大量の演算を行うにはどうすれば良いか?
→ ndarrayのハンドリング性をフル活用する。
16

要件
? Python上で処理をする事を避け、ndarrayのハ
ンドリング性をフル活用する。
そこで駆使すべき機能は
1. Broadcasting
2. Indexing
Broadcasting?, Indexing??
17

Broadcasting
? Broadcastingとは、ある2つのN次元配列の演
算の際、それらが異なるランクで、かつランク
が小さい方の配列の次元数が大きい方のの下位
ランクの次元数と一致する時に発生する。
? ランクが小さい方の配列が大きい方の配列の残
りのランクだけコピーされる。
ランクって何? → テンソルで言う添字の数
18

例 - ランク2とランク3
#b.shape[-a.ndim:] == a.shape の時は
a = arange(12).reshape((3,4))
b = ones((2,3,4))
# 全て計算可能
print "a + b = "
print a + b
print "a - b = "
print a - b
print "a * b = "
print a * b
print "a / b = "
print a / b
print "a ** b = "
print a ** b
19

a + b =
[[[ 1. 2. 3. 4.]
[ 5. 6. 7. 8.]
[ 9. 10. 11. 12.]]
[[ 1. 2. 3. 4.]
[ 5. 6. 7. 8.]
[ 9. 10. 11. 12.]]]
a - b =
[[[ -1. 0. 1. 2.]
[ 3. 4. 5. 6.]
[ 7. 8. 9. 10.]]
[[ -1. 0. 1. 2.]
[ 3. 4. 5. 6.]
[ 7. 8. 9. 10.]]]
a * b =
[[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]
[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]]
20

a / b =
[[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]
[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]]
a ** b =
[[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]
[[ 0. 1. 2. 3.]
[ 4. 5. 6. 7.]
[ 8. 9. 10. 11.]]]
21

# b.shape[-a.ndim:] != a.shape の時は、
a = arange(12).reshape((3,4))
b = ones((2,3,6))
#全て計算不可能
a + b; a - b; a * b; a / b; a ** b
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-15-852b2a6c2213> in <module>()
20 b = ones((2,3,6))
21 #全て計算不可能
---> 22 a + b; a - b; a * b; a / b;a ** b
23
24
ValueError: operands could not be broadcast together with shapes (3,4) (2,3,6)
22

Indexing
配列の参照をよりインテリジェントに
したもの
[]で指定する
a = array([0,1,2,3,4])
In []: a[2]
Out[]:
2
23

範囲指定(slice)が可能
a = array([0,1,2,3,4])
In []: a[0:3]
Out[]:
array([0, 1, 2])
24

インデックス指定に配列を指定可能
a = array([0,1,2,3,4])
b = array([3,2,4,1,0])
In []: a[b]
Out[]:
array([3, 2, 4, 1, 0])
25

True, Falseのbool型を指定可能
a = array([0,1,2,3,4])
b = array([True, False, True, False, True])
In []: a[b]
Out[]:
array([0, 2, 4])
26

配列のアサインメントに条件式を指定可能
a = array([0,1,2,3,4])
b = array([3,2,4,1,0])
In []: a[a > b]
Out[]:
array([3, 4])
27

多次元の配列のインデクシングに(部分的に)対応
内部でブロードキャストを行っている。
a = array([0,1,2,3,4])
In []: a = arange(6).reshape((2,3)); a
Out[]:
array([[0, 1, 2],
[3, 4, 5]])
In []: a[array([0,1,0])[:, None], array([2,1,0])]
Out[]:
array([[2, 1, 0],
[5, 4, 3],
[2, 1, 0]])
28

IndexingとBroadcastingの適用例
例 - アップサンプリング
def halp_flip(v):
width = v[0].size; height = len(v)
xidx = array(roll(arange(width) * ones(height)[:None], width/2), dtype=int)
yidx = array(roll(arange(width)[:,None]*ones(height), height/2), axis=0), dtype0int)
return v[xidx.reshape(xidx.size), yidx.reshape(yidx.size)].reshape((height, width))
def upsample(v, up):
width = v[0].size; height = len(v)
f_res = zeros((height+up, width+up), dtype=complex128)
f = fft.fft2(v)
xidx = array(roll(arange(len(f_res[0].size)[:,None], -len(f_res)/2,dtype=int)
yidx = array(roll(arange(len(f_res[0].size)[:,None], -len(f_res)/2,dtype=int)
f_rolled = half_flip(f)
f_res[up/2:-up/2, up/2:-up/2] = f_rolled
f_res_rolled = f_res[xidx.reshape(xidx.size), yidx.reshape(yidx.size)].reshape((len(f_res), len(f_res))
return array(nom(fft.ifft2(f_res_rolled).real, 255), dtype=uint8)
29

考察
IndexingとBroadcastingを使っ
て、多次元配列を計算する
? 処理がイタレーションより高速(書き方で例外あり)
? 複数の処理を同時に行うため、可読性に劣る。慣れていないと
ミスをする。
? 一度に処理でき効率的な半面、それを実現するための関数?
概念(where, reshape, Broadcasting, Indexing etc...等)、が多
い。
? 結局、数式をプログラムに(人力)コンパイル(翻訳)している。
30

4. 効率的な演算規則及び
プログラムの開発
31

より効率的な配列演算の検討
? 数式の演算規則の考案
1. ndarrayの配列演算に親和性の高い演算規則
2. 添字の位置によって提供様々な演算が可能
? 演算規則を反映した配列演算プログラムの開発
→ 別紙(配布資料)
? 自己定義の演算規則及び集合論的な記述により、紙面での記
述とコーディングが一対一対応する。
→ 紙面に記述された数式をそのままプログラムとして入力で
きる。
32

本提案のメリット
1. 分業
? 理論検討の際のコーディングに対する技術的な敷居を
下げる。
→ 理論検討を行う側がコーディングを覚える労力を
低減できる。
? 本演算規則によって記述された数式を最低限の理解で
実装できる。
→ 理論を利用する側が理論を理解する労力を低減で
きる。
33

本提案のメリット
2. 分業
? 演算規則にそって記述した数式が即実行できる
ので、より直感的なアルゴリズム検討が可能と
なり、新たなアルゴリズムを発想できる可能性
がある。
34

現状の実装状況
? Pythonのndarrayでは大量のデータ(具体的な値は未検討)を与えて
やると処理が重くなる。
? よりハード寄り(メモリアクセス等の管理)のアルゴリズムの検
討、つまりndarray自体の検討が必要。
→ しかし、現状の知識では敷居が高い。
自己定義の多次元配列の開発
? 検討用として、C++でndarrayライクな演算規則を持ったクラス
の開発。
35

自作c++クラスndarrの開発
//setting dimension.
ndarr<double> a{2};
ndarr<double> b{3,2};
ndarr<double> c{4,3,2};
ndarr<double> d{5,4,3,2};
ndarr<double> e{6,5,4,3,2};
ndarr<double> f{7,6,5,4,3,2};
ndarr<double> g{8,7,6,5,4,3,2};
36

For example, input the number from 0 to
{array size -1}.
a.range();
b.range();
c.range();
d.range();
e.range();
f.range();
g.range();
37

1. array is able to be viewed
with following format
a =
[0.00e+00 1.00e+00 ]
b =
[[0.00e+00 1.00e+00 ]
[2.00e+00 3.00e+00 ]
[4.00e+00 5.00e+00 ]]
38

2. Binary operation is supported.
a + 2 - a * a / 4 =
[2.00e+00 2.75e+00 ]
39

3. So-called 'broadcast' tecnhnic
is supported.
a + b = [0 1] + [[0 1], [2 3], [4 5]] =
[[0.00e+00 2.00e+00 ]
[2.00e+00 4.00e+00 ]
[4.00e+00 6.00e+00 ]]
a + b + c + d + e + f + g
= {is also able to be calculeted but too big to output.}
40

4. Product of dot, cross and dyad
is suported.
The dot product of a and b is
[[1.00e+00 3.00e+00 5.00e+00 ]
[1.00e+00 3.00e+00 5.00e+00 ]
[1.00e+00 3.00e+00 5.00e+00 ]]
The cross product of a and b is
[[0.00e+00 -2.00e+00 -4.00e+00 ]
[0.00e+00 -2.00e+00 -4.00e+00 ]
[0.00e+00 -2.00e+00 -4.00e+00 ]]
The dyadic product of a and b is
[[[[0.00e+00 0.00e+00 ]
[0.00e+00 0.00e+00 ]
[0.00e+00 0.00e+00 ]]
[[0.00e+00 1.00e+00 ]
[0.00e+00 1.00e+00 ]
[0.00e+00 1.00e+00 ]]]
[[[0.00e+00 2.00e+00 ]
[0.00e+00 2.00e+00 ]
[0.00e+00 2.00e+00 ]]
[[0.00e+00 3.00e+00 ]
[0.00e+00 3.00e+00 ]
[0.00e+00 3.00e+00 ]]]
[[[0.00e+00 4.00e+00 ]
[0.00e+00 4.00e+00 ]
[0.00e+00 4.00e+00 ]]
[[0.00e+00 5.00e+00 ]
[0.00e+00 5.00e+00 ]
[0.00e+00 5.00e+00 ]]]]
41

sin(b) =
[[0.00e+00 8.41e-01 ]
[9.09e-01 1.41e-01 ]
[-7.57e-01 -9.59e-01 ]]
fabs(b) =
[[0.00e+00 1.00e+00 ]
[2.00e+00 3.00e+00 ]
[4.00e+00 5.00e+00 ]]
42

b's dimension transpose [0,1] to [1,0] as fllows.
[[0.00e+00 2.00e+00 4.00e+00 ]
[1.00e+00 3.00e+00 5.00e+00 ]]
c's dimension transpose [0,1,2] to [0,2,1] as fllows.
[[[0.00e+00 2.00e+00 4.00e+00 ]
[1.00e+00 3.00e+00 5.00e+00 ]]
[[6.00e+00 8.00e+00 1.00e+01 ]
[7.00e+00 9.00e+00 1.10e+01 ]]
[[1.20e+01 1.40e+01 1.60e+01 ]
[1.30e+01 1.50e+01 1.70e+01 ]]
[[1.80e+01 2.00e+01 2.20e+01 ]
[1.90e+01 2.10e+01 2.30e+01 ]]]
c's dimension transpose [0,1,2] to [2,1,0] as fllows.
[[[0.00e+00 6.00e+00 1.20e+01 1.80e+01 ]
[2.00e+00 8.00e+00 1.40e+01 2.00e+01 ]
[4.00e+00 1.00e+01 1.60e+01 2.20e+01 ]]
[[1.00e+00 7.00e+00 1.30e+01 1.90e+01 ]
[3.00e+00 9.00e+00 1.50e+01 2.10e+01 ]
[5.00e+00 1.10e+01 1.70e+01 2.30e+01 ]]]
43

7. Other utility menber function
is provided a little.
min(b) = 0.00e+00
sum(b) = 5.00e+00
sum(b) = 1.50e+01
mean(b) = 2.50e+00
44

まとめ
? Pythonのndarrayで効率的に計算を行うために、自
己定義の演算規則及びテンソルライクなクラスを開
発した。
今後
? 高速化
? ndarrayのソースの検討
? 数式を容易に記述できるソフトウェアに対するプラ
グインの開発
45

狠狠撸

多次元配列の効率的利用法の検讨

More Related Content

多次元配列の効率的利用法の検讨