Perlで学ぼう！文系プログラマのための、知識ゼロからのデータ構造と計算量

by しんぺい a.k.a. 猫型蓄音機 Perlで学ぼう！文系プログラマのための知識ゼロからのデータ構造と計算量

あんただれ • しんぺいとか猫型とかいう名前で呼ばれています • rerakuという会社で働いてます • 仕事ではScala, Perl, Ruby

あんただれ • Github:Shinpeim • process-book • 新潟非在住 Niigata.pm 主催です •
趣味でバンド • 11/14高円寺ペンギンハウス

ペンギンハウス

今日やること • データ構造と計算量について、簡単に解説します • 基本的なことしかやりません • ハイレベルプログラマ諸氏は今すぐ別の部屋で有意義な時間を過ごすんだ！！

事前準備

Cの変数とメモリ

何がおきてる？

int のメモリを確保 JOUB

1を代入 JOUB

bも同様に JOUB JOUC

c も同様に JOUD JOUB JOUC

CPUが足し算してcに代入 JOUD JOUB JOUC

ポイント • 変数は箱ではない！！！！！！ • メモリです • たくさん用意すれば用意するほどメモリを消費する

メモリとポインタ

実はメモリには番地があります B 10000番

番地を取得 B 10000番

番地を保存する4byte確保 TIPSU C B 10000番

番地を代入 TIPSU C B 10000番

bの中身を10進数で表示 TIPSU C B 10000番

bの番地の指し示す先を見て 10000番 TIPSU C B

short* なので2バイト読む TIPSU C B

ポイント • ポインタの中には「メモリ上の位置」を表す数字が入ってる • その数字の番地から、ポインタが示す型のバイト数だけ読めばポインタの指す値を読むことができる • こうやって「値につながる値」を作るこ
とができる

練習問題へんな値が出力されるのはなぜ？

Perlの場合

SVを確保 47

AVを確保 47 "7

HVを確保 47 "7 47 )7 B

SVを確保してSVの場所を代入 47 "7 47 )7 47 B
47 47 SFG YGEEC 0x7f99d080db78

中身を表示 47 "7 47 )7 47 B
47 47 SFG YGEEC

中身の指し示すやつを取ってきて表示 47 "7 47 )7 47 B
47 47 SFG YGEEC 0x7f99d080db78

ポイント • 値はメモリに確保されてる • リファレンスにはそのメモリの場所を示すものが入っている • ねっ、CもPerlも変わらないでしょ

さまざまなデータ構造

エントリーナンバー1

配列

なにがおきてる？

short5個分を「連続して」確保 10000番

変数名でアクセスすると番地が取れる 10000番

添え字付きアクセス 10000 + short(2byte) *
2 番地を読みに行くよ 10000番

添え字付きアクセス

配列の要素を増やしたい

単方向連結リスト

単方向連結リストの要素 a next element

単方向連結リスト

要素一個つくる要素一個つくる

要素一個つくる )7 @WBMVF @OFYU@SFGVOEFG 1

要素一個つくる )7 @WBMVF @OFYU@SFGVOEFG FM@ &MFNFOU SFG 1

ふたつめの要素作る )7 @WBMVF @OFYU@SFGVOEFG FM@ &MFNFOU SFG )7
@WBMVF @OFYU@SFG&MFNFOU SFG FM@ &MFNFOU SFG 1 2

$el_ 1もう出てこないので無視 )7 @WBMVF @OFYU@SFGVOEFG )7 @WBMVF @OFYU@SFG&MFNFOU
SFG FM@ &MFNFOU SFG 1 2

同様にみっつめの要素 )7 @WBMVF @OFYU@SFGVOEFG )7 @WBMVF @OFYU@SFG&MFNFOU SFG
FM@ &MFNFOU SFG )7 @WBMVF @OFYU@SFG&MFNFOU SFG 1 2 3

Listの実装コンストラクタリストの先頭に値を追加するメソッド

空のリストを作って )7 @pSTU@FMFNFOU VOEFG MJTU -JTU SFG

要素をひとつ挿入 )7 @pSTU@FMFNFOU VOEFG MJTU -JTU SFG )7
@WBMVF @OFYU@SFGVOEFG

要素をひとつ挿入 )7 @pSTU@FMFNFOU &MFNFOUSFG MJTU -JTU SFG )7
@WBMVF @OFYU@SFGVOEFG

2を挿入 MJTU -JTU SFG )7 @WBMVF @OFYU@SFGVOEFG )7
@pSTU@FMFNFOU &MFNFOUSFG )7 @WBMVF @OFYU@SFG &MFNFOUSFG

3つめの値を取得したい MJTU -JTU SFG )7 @WBMVF @OFYU@SFG &MFNFOUSFG
)7 @pSTU@FMFNFOU &MFNFOUSFG )7 @WBMVF @OFYU@SFG &MFNFOUSFG )7 @WBMVF @OFYU@SFGVOEFG

MJTU -JTU SFG )7 @WBMVF @OFYU@SFG &MFNFOUSFG )7
@pSTU@FMFNFOU &MFNFOUSFG )7 @WBMVF @OFYU@SFG &MFNFOUSFG )7 @WBMVF @OFYU@SFGVOEFG 3つめの値を取得したい

ポイント • メモリアドレスが飛び飛び • 「空いてるところ」にメモリ確保できる • 先頭からの順々に辿らないといけないので一発でアクセスできない

一発とか順々とかちょっとふわっとしてるもうちょっとちゃんと言いたい

ここでちょっと寄り道計算量の話

オーダー法 • データの数がn個のとき、n回計算をしないといけないとき、O(n)という • 2n回計算しないといけない、とか、 2n + a回計算しないといけないときもO(n)という
• 要するに定数倍とか定数項は考えない

連結リストの計算量 • n個めの要素にアクセスしたい • 最初の要素へのアクセス + n - 1回辿る必要がある
= O(n) • リストの最初に値を挿入したい • 後ろにいくつ要素があっても、最初の要素へのアクセス + 新しい要素を作ってつなぐだけ = O(1)

配列の計算量 • n個めの要素にアクセスしたい • 計算で一発でメモリ番地が出せて、そこを読むだけでよい • O(1)

いろんな計算量をグラフでみると特徴がわかる

O(n) ԣ࣠ɿσʔλͷݸ਺ ॎ࣠ɿܭࢉͷྔ ԣ࣠ɿσʔλͷݸ਺ ॎ࣠ɿܭࢉͷྔ

O(n^2) ԣ࣠ɿσʔλͷݸ਺ ॎ࣠ɿܭࢉͷྔ

O(1) ԣ࣠ɿσʔλͷݸ਺ ॎ࣠ɿܭࢉͷྔ

O(log n)

O(log n) ԣ࣠ɿσʔλͷݸ਺ ॎ࣠ɿܭࢉͷྔ

ポイント • オーダー法は「正確な計算量」を導かない • データの量に応じて、「データが増えたときにどれくらい処理量が増えるか」をざっと知るための指標です

データ構造の話に戻ります

連結リストの特徴 • 探索の計算量がO(n)だった • 悪くないけどO(log n)だと嬉しいですよねー

2分木

2分木のnode a x<a a<x

)7 @SPPUVOEFG USFF 5SFFSFG tree 空の2分木

)7 @SPPUVOEFG USFF 5SFFSFG tree 2分木に最初の値：4を追加

2分木に最初の値：4を追加 )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @SPPU/PEF SFG
USFF 5SFFSFG tree

2分木に2を追加 )7 @WBMVF @TNBMMFS/PEFSFG @MBSHFSVOEFG )7 @SPPU/PEF
SFG USFF 5SFFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG tree

SFG USFF 5SFFSFG V )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG tree

2分木に6を追加 )7 @WBMVF @TNBMMFS/PEFSFG @MBSHFS/PEFSFG )7
@SPPU/PEF SFG USFF 5SFFSFG V V )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG tree

@SPPU/PEF SFG USFF 5SFFSFG V V )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG tree

@SPPU/PEF SFG USFF 5SFFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG V V tree

@SPPU/PEF SFG USFF 5SFFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFS/PEFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG V V V tree

2分木から1を探索 )7 @WBMVF @TNBMMFS/PEFSFG @MBSHFS/PEFSFG )7
@SPPU/PEF SFG USFF 5SFFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFS/PEFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG V V V tree

2分木の探索 • 4つ要素があるけど2回で済んだ • こういう風にちゃんと「ばらけた」木になってるとO(log n)になる

2分木から5を探索 )7 @WBMVF @TNBMMFSVOEFG @MBSHFS/PEFSFG )7 @SPPU/PEF
SFG USFF 5SFFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFS/PEFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFS/PEFSFG )7 @WBMVF @TNBMMFSVOEFG @MBSHFSVOEFG

2分木の探索 • 実質連結リスト • O(n)じゃん

B木のnode b a x<a a<x<b b<x

空のB木に7を追加

B木に3を追加

B木に9を追加満員じゃん

B木に9を追加全員並べて

B木に9を追加 nodeふたつに分けて

B木に9を追加真ん中の値の行き場がない

B木に9を追加新しいnode作る

B木に9を追加枝つなぐ

B木に9を追加見やすいように整列！

B木に5を追加

B木に6を追加全員並べて

B木に6を追加 nodeふたつに分けて

B木に6を追加真ん中は上に空きがあるのでそこに入れる

B木に6を追加

B木に6を追加枝つなぎ直す

B木に6を追加見やすいように整列！

B木に10を追加

B木に16を追加真ん中は上に

B木に16を追加

B木に16を追加 node分割して枝つなぎ直す

B木に16を追加新しいnode作って枝つなぐ

B木に16を追加

B木に16を追加 O(log n)
O(m)

B+木 • DBのインデックスとかに使われてる • B木の改良版 • 末端のnodeに全部のデータが入ってる •
node同士がlinkされてることが多い

B+木から5を探索
select * from table where id > 5

まとめ

まとめ • データ構造と計算量について簡単に見てみました • この程度の理解でも、ふだんの業務に活かせることは増えます • 今後の学習や業務に活かしていただければ幸いです

最後に • 11/14 高円寺ペンギンハウス • よろしくおねがいします

おしまい

Perlで学ぼう！文系プログラマのための、知識ゼロからのデータ構造と計算量

Perlで学ぼう！文系プログラマのための、知識ゼロからのデータ構造と計算量

More Decks by Shinpei Maruyama

Other Decks in Programming

Featured

Transcript