| | 1 | = Boost.勉強会#14 = |
| | 2 | |
| | 3 | 日時: 2014/3/1 10:00 ~ 18:00 |
| | 4 | 場所: IIJ@神保町 |
| | 5 | |
| | 6 | == cpprefjp を支える技術 == |
| | 7 | |
| | 8 | * Google Sites でリファレンスを書くのは結構大変… 統一的な書き方ができるフレームワークがほしい |
| | 9 | * 作業環境を GitHub に移行。 |
| | 10 | * プレーンテキストで書きたい |
| | 11 | * バージョン管理しやすくしたい |
| | 12 | * →Markdown |
| | 13 | * Gogle Sites はそのままに… GitHub で書いた Markdown を自動的に HTML に変換して Google Sites に同期する。 |
| | 14 | * cpprefjp → HTML → GitHub (MarkDown) |
| | 15 | * GitHub (MarkDown) → (Python) → HTML → cpprefjp |
| | 16 | * cpprefjp → HTML |
| | 17 | * Google Apps Script を使用 |
| | 18 | * 何回かに分けた (API 制限) |
| | 19 | * HTML → Markdown |
| | 20 | * Ruby 1.9 の正規表現でがんがった |
| | 21 | * 手動で手直しもしました。→ツールは使い捨て (;_;) |
| | 22 | * GitHub → Google Sites |
| | 23 | * めるぽんさんが作成、運営も… |
| | 24 | * 変換サーバー (andare) |
| | 25 | * GitHub から Markdown 取得し、 HTML に変換 |
| | 26 | * Python+Dhango製 |
| | 27 | * Markdown という Python ライブラリを使用 |
| | 28 | * アップロードスクリプト |
| | 29 | * Google Apps Script を使用 |
| | 30 | * シンタックスハイライト |
| | 31 | * Markdown ライブラリにもともとあった。 |
| | 32 | * 執筆者指定で特定の文字列をハイライトできるようにしたい。 |
| | 33 | * 指定した文字列を検索し、一旦ランダムな文字列を前後に入れてから、その文字列を HTML に置換し直すというやり方をゴリゴリコーディングしましたよ |
| | 34 | * GitHub の差分管理 |
| | 35 | * site ブランチ |
| | 36 | * A - B |
| | 37 | * master ブランチ |
| | 38 | * A - B - C - D |
| | 39 | * master ブランチと site ブランチの違いを見て更新ファイルを判断 |
| | 40 | * Google Sites 更新後、 master ブランチを site ブランチへ merge (上図の C と D) |
| | 41 | * アップロード |
| | 42 | * スクリプトの制限 |
| | 43 | * 実行時間は 5分まで |
| | 44 | * 1ファイル更新に 5秒ぐらいかかる |
| | 45 | * 制限1: 1回あたり 60ファイルぐらいしか更新できない |
| | 46 | * どこまで更新したかをストレージに保存 |
| | 47 | * 4分過ぎたら次のタイマーを仕掛けて終了 |
| | 48 | * 次の実行では中断したところから再開 |
| | 49 | * …では甘かった orz |
| | 50 | * 制限2: ストレージの 1つのキーは 9KB まで… |
| | 51 | * 実行時の情報 (JSON) を格納したら漏れた |
| | 52 | * JSON 文字列を自動的にぶった切って複数のキーに格納 |
| | 53 | * 取り出すときは自動的に結合して取得 |
| | 54 | * エラー通知 |
| | 55 | * GitHub の Issue に自動登録するようにしたよ |
| | 56 | * 次の実行で変換エラーがなくなれば自動で Issue を閉じるようにしてあるよ |
| | 57 | * 一時的なエラーの可能性もあるので失敗しても何度かはリトライ |
| | 58 | * エラーのあったファイルを変換サーバに POST |
| | 59 | * あとは変換サーバ側でいい感じに Issue に登録してくれる |
| | 60 | |
| | 61 | == Boost.Graphの設計と、最短経路アルゴリズムの使い方いろいろ == |
| | 62 | |
| | 63 | * Boost Graph Library の設計がメインのお話。 |
| | 64 | * グラフのデータ構造とアルゴリズムのライブラリ。STL の概念に基づく。後発のグラフライブラリに大きな影響を与える。 |
| | 65 | * グラフとは… |
| | 66 | * 頂点 vertex と辺 edge からなるデータ構造 |
| | 67 | * 棒グラフや折れ線グラフとは関係ない。 |
| | 68 | * 辺が方向を持つかどうかで有向グラフ(directed)、無向グラフ(undirected) の2つの分類があるよ。 |
| | 69 | * ex) |
| | 70 | * 電車の路線 |
| | 71 | * 道路 |
| | 72 | * network |
| | 73 | * ファイルの依存関係 |
| | 74 | * クラス図 |
| | 75 | * 行列 |
| | 76 | * チェス盤 |
| | 77 | * etc... |
| | 78 | * グラフの用途 |
| | 79 | * 最短経路を求める |
| | 80 | * 一筆書き |
| | 81 | * ネットワーク分析 |
| | 82 | * コミュニティ、情報を広げる中心にいるのは誰か |
| | 83 | * コミュニティ同士を繋ぐ架け橋、またはボトルネックは誰か |
| | 84 | * ページランクの算出 (Google検索) |
| | 85 | * 迷路を解く |
| | 86 | * 文献 |
| | 87 | * [http://www.amazon.co.jp/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E3%81%AE%E6%9C%AC-%E3%83%AC%E3%83%8A%E3%81%AE%E3%81%B5%E3%81%97%E3%81%8E%E3%81%AA%E6%95%B0%E5%AD%A6%E3%81%AE%E6%97%85-P-%E3%82%B0%E3%83%AA%E3%83%83%E3%83%84%E3%83%9E%E3%83%B3/dp/4621061364/ref=sr_1_1?ie=UTF8&qid=1393639481&sr=8-1&keywords=%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E3%81%AE%E6%9C%AC 最短経路の本] |
| | 88 | * [http://www.oreilly.co.jp/books/9784873115504/ オープンソースで学ぶ社会ネットワーク分析] |
| | 89 | * グラフ型 |
| | 90 | * adjacency_list ...隣接リスト |
| | 91 | * adjacency_matrix ... |
| | 92 | * 操作 |
| | 93 | * グラフ型への統一的な操作を提供 |
| | 94 | * グラフ型が直接持つインタフェース(メンバ)を使うのではなく、オーバーロード可能なフリー関数を介してグラフを操作。 |
| | 95 | * Boost.Graph のコンセプトを満たす、あらゆるグラフ型を適用可能。 |
| | 96 | * std::vector もグラフ型として使えるよ |
| | 97 | {{{#!c++ |
| | 98 | std::vector<Hoge> g; |
| | 99 | proc_graph(g); |
| | 100 | }}} |
| | 101 | * vertices() や edges() といった'''グラフコンセプトのフリー関数'''を、 |
| | 102 | グラフ構造とアルゴリズムの中間インタフェースとしている。 |
| | 103 | * STL の反復子コンセプトと対を成すもの、と考えればいい。 |
| | 104 | * プロパティマップ |
| | 105 | * グラフには様々な種類のデータが付加される。 |
| | 106 | * ex) 電車の路線図 |
| | 107 | * 頂点 ... 駅名 |
| | 108 | * 辺 ... 駅間の距離 |
| | 109 | * 全体 ... 路線名 |
| | 110 | * adjacency_list のテンプレートパラメータ |
| | 111 | * OutEdgeListS ... グラフの隣接構造を表すためのコンテナ |
| | 112 | * vecS: std::vector |
| | 113 | * listS: std::list |
| | 114 | * setS: std::set |
| | 115 | * VertexListS ... 頂点コンテナ |
| | 116 | * DirectedS ... 有向か無向か |
| | 117 | * VertexProperties ... 頂点 |
| | 118 | * EdgeProperties ... 辺 |
| | 119 | * GraphProperties ... グラフ全体 |
| | 120 | * 取得と設定は boost::get(), boost::set() を使用。 |
| | 121 | * 使い方いろいろ… |
| | 122 | * dijkstra_shortest_paths() に絞ってみていくよ |
| | 123 | * 最短経路を求める |
| | 124 | * 先行マップ |
| | 125 | * ある頂点の前に通る頂点を集めた辞書 |
| | 126 | * 目的地 Z を与えると、 Z の前を通る頂点 F が取得できる。 |
| | 127 | * 逆順の最短経路を頂点のリストとして取得できる。 |
| | 128 | {{{#!c++ |
| | 129 | std::deque<Vertex> route; |
| | 130 | for(Vertex v to; v != from; v = parents[v]){ |
| | 131 | route.push_front(v); |
| | 132 | } |
| | 133 | route.push_front(from); |
| | 134 | }}} |
| | 135 | * 先行マップは、 dijkstra_shortest_paths() に boost::predecessor_map() という関数を通して渡していた。 |
| | 136 | * boost::predecessor_map() : 名前付き引数を使う関数。(使わないバージョンもあるけど引数やたら多くて大変) |
| | 137 | * 最短経路全体でどれくらいの距離があるか知りたい場合は、 distance_map を指定する。 |
| | 138 | {{{#!c++ |
| | 139 | boost::dijkstra_shortest_paths(g, from, |
| | 140 | boost::predecessor_map(&parents[0]). |
| | 141 | distance_map(&distance[0])); |
| | 142 | |
| | 143 | int d = distance[to]; |
| | 144 | }}} |
| | 145 | * イベントビジター ... アルゴリズムの各ポイントで、任意の関数を呼び出せる。 |
| | 146 | {{{#!c++ |
| | 147 | struct MyVisitor : dijkstra_visitor<> { |
| | 148 | template <class Vertex, class Graph> |
| | 149 | void discover_vertex(Vertex v, const Graph&) |
| | 150 | { ...event... } |
| | 151 | }; |
| | 152 | |
| | 153 | boost::dijkstra_shortest_paths(... |
| | 154 | }}} |
| | 155 | * 特定の頂点が見つかったら例外を投げて、アルゴリズムのループを脱出する。 |
| | 156 | * 既存のアルゴリズムを使って、新たなアルゴリズムを作る。 |
| | 157 | * dijkstra_shortest_paths() は、幅優先探索をイベントビジターでラップして作られている。 |
| | 158 | * コルーチンでアルゴリズムを中断 |
| | 159 | * アルゴリズム計算状況の可視化。 |
| | 160 | * アルゴリズムの設計 |
| | 161 | * ユーザビリティとは、その分野に精通していないユーザーにとっての公開されているアルゴリズムインタフェースのわかりやすさ。 |
| | 162 | 同時に、精通しているユーザーにとってのアルゴリズムを構成できる幅のこと。 |
![(please configure the [header_logo] section in trac.ini)](/trac/original/ideanote/chrome/site/your_project_logo.png){kind=logo}
