Upgrade to Pro — share decks privately, control downloads, hide ads and more …

2018早稲田大学アルゴリズムとデータ構造特別講義 / 2018-Algorithm-And-...

2018早稲田大学アルゴリズムとデータ構造特別講義 / 2018-Algorithm-And-Data-Structure-Course-At-Waseda

Yoshiyuki Asaba

December 21, 2018
Tweet

More Decks by Yoshiyuki Asaba

Other Decks in Technology

Transcript

  1. 4 創業からIPOまで、中小企業活性化のためのサービスを一気通貫で提供 freee会社概要 ❂ 納税する ↗ 育てる ↻ 運営する ✩

    はじめる 会社設立 freee 開業 freee クラウド会計ソフト freee 人事労務 freee (マイナンバー管理 freee 含む) クラウド申告 freee 161億603万円 (資本準備金等含む) 従業員数 事業内容 クラウド型バックオフィスサービスの開発・販売 資本金 設立年月日 2012年7月 465名(2018年6月末時点) 2017年「働きがいのある会社」 ランキング3位
  2. 7 Webサービス(1) インターネット上で何かしらの価値を提供するシステム • クラウドや*aaSなどと表現することもある ◦ SaaS, PaaS, IaaSなど •

    freeeはビジネス向けのサービスを提供 ◦ B2B (Business To Business) ◦ ブラウザだけでなくiOSやAndroidのアプリからサービスを使うケースも含める
  3. 10 サービスが常時稼働しているとは? 前提:マシンは壊れるもの • CPU, メモリ, ストレージ, その他パーツなど • ソフトウェアのバグによって機能しなくなることもある

    ◦ 物理的に壊れなくても、OS, ミドルウェア, アプリケーションが壊れることによって事実上 の壊れた状態になることも 壊れても大丈夫なように複数のマシンでサービスを動かす • 「冗長化」と呼んだりします ハードウェア(PC, tablet, smartphone等) OS(iOS, MacOS, Windows, Linux等) ミドルウェア アプリケーション
  4. 11 レスポンスを速く返すとは? 計算を速く終わらせる • ハードウェアのスペックをあげる • ソフトウェアを効率よく動かす ◦ アルゴリズムとデータ構造が特に重要 •

    不要な計算を後回しにする サーバーの忙しさを下げる • 少ない計算量でも、同じ処理が一台でたくさん動いている と待たされる ◦ リクエストを複数のサーバーに振り分ける ◦ 負荷分散と呼ぶ 待ち行列 • リクエストを即座に処理し始める(待たせない)
  5. 13 データを保存する Webサービスは大抵は何かのデータを保存します • 会計データ • 画像 • SNSの投稿 •

    チャットメッセージ 保存するためのシステムがあります • RDBMS, KVS, ... • あとで説明予定 これ
  6. 16 すべてを紹介するのは難しいので RDBMS (Relational DataBase Management System) • データの検索 •

    データの並び替え • データの結合 KVS (Key Value Store) キューシステム
  7. 18 RDBMS Relational DataBase Management System • 簡単に言うと ◦ 安全にかつ高速に、大量のデータを保存・検索できるシステム

    ◦ WebサービスだとMySQLやPostgreSQLがよく使われている ◦ RDBMSは大抵のサービスで使われていると思って良い データベースの授業は3年で開講されるそうですが、 その場合は絶対に受けておいたほうが良いです!!
  8. 19 RDBMSのイメージ スプレッドシートみたいなもの • テーブル • 行 • 列 特徴

    • 検索ができる • 大量データを扱える • 同時操作が可能 • その他にもいろいろありますが、来年の講義でぜひ学んでください
  9. 20 SQL Structured Query Language • RDBMSに命令をするための言語 • 宣言的に欲しいデータの検索条件を記述 •

    データの挿入、更新、削除も可能 • どのように検索するかはRDBMSが裏で決める SELECT 学籍番号, 名前 FROM 学生 WHERE 都道府県 = ‘東京都’ 命令:学生というテーブルの中から東京都の学生だけを学籍番号と名前を抽出したい
  10. 23 データの検索 線形探索 • データをすべて検索する ◦ 配列を最初から最後までスキャンするイメージ • ストレージの速度が速くなったとはいえ遅い •

    フルスキャンと呼んだりします インデックス探索 • 次のページから説明します • 二分木探索をイメージしてもらえると
  11. 24 例:教科書から特定の内容が書かれているページに飛びた い 「クイックソート」というキーワードを探す • その本が1,000ページあるとする 探し方 • 巻末にある「索引」から「クイックソート」という単語があるか調べて、あればそのページに 移動する

    ◦ インデックススキャン • 本を1ページ目から探していく ◦ 1,000ページを読み込まないといけないので時間がかかる ◦ 「変数」という一般的な用語だといろいろなページに出てくるので、先頭から全部確認し たほうが速い ▪ ↑は選択率が高い状態 ▪ 意味があるかどうかは置いておいて
  12. 25 B+Tree 木構造の一つ • インデックス(索引)を表現するデータ構造の一つ • ソート済みのデータを保持する • メモリ上で収まりきらないようなデータを効率よく扱えるように工夫されている ◦

    前提:ストレージのオペレーションは遅い インデックス探索 • 次のページから説明します • 二分木探索をイメージしてもらえると By Grundprinzip - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=10758840
  13. 26 B+Treeの特徴 実際のデータは葉にしか持たない • B-Treeは節にも持つ • ブロックデバイスに適している ◦ ブロックデバイスとは簡単に言うと外部ストレージ(HDD, SSD等)

    ◦ 一回のストレージのオペレーションをブロックという塊で操作する • 節を1ブロックに大量に詰め込むことができるので、木の高さが低くなる
  14. 28 B+Treeの挙動を知りたい場合 小さいCのコードがあります • http://www.amittai.com/prose/bplustree.html $ gcc -g -O0 btp.c

    $ ./a.out ... Enter any of the following commands after the prompt > : i <k> -- Insert <k> (an integer) as both key and value). f <k> -- Find the value under key <k>. p <k> -- Print the path from the root to key k and its associated value. r <k1> <k2> -- Print the keys and values found in the range [<k1>, <k2> d <k> -- Delete key <k> and its associated value. x -- Destroy the whole tree. Start again with an empty tree of the same order. t -- Print the B+ tree. l -- Print the keys of the leaves (bottom row of the tree). v -- Toggle output of pointer addresses ("verbose") in tree and leaves. q -- Quit. (Or use Ctl-D.) ? -- Print this help message. > i 3 3 |
  15. 32 Top-N sort (Top-k selection) 並び替えた結果から上位10件を取りたい • SELECT * FROM

    students ORDER BY score DESC LIMIT 10 • 該当する行をすべてとってきてソートするのではなく、上位N件だけを保持してソートする
  16. 35 テーブル結合とは 2つのテーブルを指定した条件で別のテーブルを作る(結合, JOIN) • 例:数字が一致する行を結合したい 学籍番号 都道府県 コード 4

    101 2 102 1 102 7 104 都道府県 コード 都道府県名 101 東京都 102 神奈川県 103 長野県 104 愛媛県 駆動表 内部表 結合 学籍 番号 都道府県 コード 都道府県 コード 都道府県名 4 101 101 東京都 2 102 102 神奈川県 1 102 102 神奈川県 7 104 104 愛媛県
  17. 36 結合例1 特定の学生がどこ出身か? • 都道府県コードをキーにテーブルを結合 • →学籍番号と都道府県名を取得可能になる 学籍番号 都道府県 コード

    4 101 2 102 1 102 7 104 都道府県 コード 都道府県名 101 東京都 102 神奈川県 103 長野県 104 愛媛県 学生テーブル (駆動表) 都道府県テーブル (内部表) 都道府県コードの一 致を条件に結合 学籍 番号 都道府県 コード 都道府県 コード 都道府県名 4 101 101 東京都 2 102 102 神奈川県 1 102 102 神奈川県 7 104 104 愛媛県
  18. 37 結合例2 特定の学生がどの講義を履修したか? • 学籍番号をキーにテーブルを結合 • →学籍番号と講義IDを取得可能になる • →さらに講義名を取得したい場合は講義テーブルを結合 学生テーブル

    学籍番号 名前 4 山田 2 田中 1 鈴木 7 木村 学籍番号 講義番号 1 1001 1 2001 4 3001 2 1022 7 4000 2 1001 講義番号 講義名 1001 英語 1022 会計学 3001 ネットワーク 2001 論理学 4000 線形代数 履修テーブル 講義テーブル
  19. 38 テーブル結合(JOIN)をどう実現するか 代表的なものは3つのアルゴリズム • Nested Loop Join • Merge Join

    • Hash Join すでに習ったアルゴリズムを組み合わせています のちほど3つのアルゴリズムを実装していただきます
  20. 39 サンプルデータ 1次元の整数の配列を2つ用意 • 整数は学籍番号や講義番号だと思ってください • 結合結果の順番は不定 4 山田 9

    高橋 2 田中 1 鈴木 7 木村 2 1022 10 2001 5 1001 7 1003 2 5000 2 田中 2 1022 2 田中 2 5000 7 木村 7 1003 結合 学生テーブル 履修テーブル
  21. 40 Nested Loop Join 単純な2重ループのアルゴリズム • 全組み合わせを比較し、条件にあったものを返す • もう少し丁寧に書くと ◦

    駆動表の条件にマッチするのを内部表から持ってくる、というのを繰り返す ◦ B+Treeでは条件次第では内部表から早くデータを取ってこれる 4 9 2 1 7 2 10 5 7 2
  22. 42 擬似コード (PostgreSQLソースコードのコメントより引用) Join { get initial outer and inner

    tuples INITIALIZE do forever { while (outer != inner) { SKIP_TEST if (outer < inner) advance outer SKIPOUTER_ADVANCE else advance inner SKIPINNER_ADVANCE } mark inner position SKIP_TEST do forever { while (outer == inner) { join tuples JOINTUPLES advance inner position NEXTINNER } advance outer position NEXTOUTER if (outer == mark) TESTOUTER restore inner position to mark TESTOUTER else break // return to top of outer loop } } }
  23. 55 擬似コード (再掲) Join { get initial outer and inner

    tuples INITIALIZE do forever { while (outer != inner) { SKIP_TEST if (outer < inner) advance outer SKIPOUTER_ADVANCE else advance inner SKIPINNER_ADVANCE } mark inner position SKIP_TEST do forever { while (outer == inner) { join tuples JOINTUPLES advance inner position NEXTINNER } advance outer position NEXTOUTER if (outer == mark) TESTOUTER restore inner position to mark TESTOUTER else break // return to top of outer loop } } }
  24. 57 練習問題 以下のJOINアルゴリズムを実装してください • Nested Loop Join • Merge Join

    ◦ ソートは何で実装しても良いです • Hash Join ◦ ハッシュテーブルは何を実装しても良いです それぞれのJOINアルゴリズムについてどういう特性があるか考えてみてくだ さい
  25. 59 練習問題 出力 • マッチした値と件数 ◦ 重複分も含める ◦ マッチした値の順番は問いません ◦

    件数がそれぞれのJOINで同じことを確認する 1 1 2 2 3 3 3 3 join count = 4
  26. 62 KVS KVSは色々なミドルウェアがある • Keyとそれに対するValueを保持する ◦ Keyでデータを検索 • 代表的なものは連想配列をハッシュテーブルを使って実装 key-valueをオンメモリで持っておく実装が多いシステム

    • データを永続化できるものもある • キャッシュ用途に使われることが多い • memoryが溢れそうな場合はLRU(Least Recently Used)等のポリシーで消すこともある
  27. 64 KVSの使用例 sessionデータを一時的に保存し、リクエストごとに参照 • sessionとはサービスにログインされると作られるデータ • ハッシュテーブルはO(1) • B+TreeはO(log_b N)

    ◦ bはどれくらい説に詰め込めるか(2分木の場合は2) ◦ 外部ストレージへのI/Oも発生する可能性がある web server web server session key value Athoh4Phu0aeng9wureJ Aさんの識別子 fohphaChahmoo1saizuu Bさんの識別子 Aeng6ei1phei0LohQu8i Cさんの識別子 GET (sessionの有効性の確認) SET (login時) ハッシュテーブル (session keyは実際はもっと長い)