wiki:HowTo/BoostStudy14

Version 1 (modified by 村山 俊之, 11 years ago) ( diff )

--

Boost.勉強会#14

日時: 2014/3/1 10:00 ~ 18:00 場所: IIJ@神保町

cpprefjp を支える技術

  • Google Sites でリファレンスを書くのは結構大変… 統一的な書き方ができるフレームワークがほしい
  • 作業環境を GitHub に移行。
    • プレーンテキストで書きたい
    • バージョン管理しやすくしたい
    • →Markdown
  • Gogle Sites はそのままに… GitHub で書いた Markdown を自動的に HTML に変換して Google Sites に同期する。
  • cpprefjp → HTML → GitHub (MarkDown)
  • GitHub (MarkDown) → (Python) → HTML → cpprefjp
  • cpprefjp → HTML
    • Google Apps Script を使用
    • 何回かに分けた (API 制限)
  • HTML → Markdown
    • Ruby 1.9 の正規表現でがんがった
    • 手動で手直しもしました。→ツールは使い捨て (;_;)
  • GitHub → Google Sites
    • めるぽんさんが作成、運営も…
  • 変換サーバー (andare)
    • GitHub から Markdown 取得し、 HTML に変換
    • Python+Dhango製
    • Markdown という Python ライブラリを使用
  • アップロードスクリプト
    • Google Apps Script を使用
  • シンタックスハイライト
    • Markdown ライブラリにもともとあった。
    • 執筆者指定で特定の文字列をハイライトできるようにしたい。
      • 指定した文字列を検索し、一旦ランダムな文字列を前後に入れてから、その文字列を HTML に置換し直すというやり方をゴリゴリコーディングしましたよ
  • GitHub の差分管理
    • site ブランチ
      • A - B
    • master ブランチ
      • A - B - C - D
    • master ブランチと site ブランチの違いを見て更新ファイルを判断
    • Google Sites 更新後、 master ブランチを site ブランチへ merge (上図の C と D)
  • アップロード
    • スクリプトの制限
      • 実行時間は 5分まで
      • 1ファイル更新に 5秒ぐらいかかる
      • 制限1: 1回あたり 60ファイルぐらいしか更新できない
        • どこまで更新したかをストレージに保存
        • 4分過ぎたら次のタイマーを仕掛けて終了
        • 次の実行では中断したところから再開
      • …では甘かった orz
      • 制限2: ストレージの 1つのキーは 9KB まで…
      • 実行時の情報 (JSON) を格納したら漏れた
        • JSON 文字列を自動的にぶった切って複数のキーに格納
        • 取り出すときは自動的に結合して取得
    • エラー通知
      • GitHub の Issue に自動登録するようにしたよ
      • 次の実行で変換エラーがなくなれば自動で Issue を閉じるようにしてあるよ
      • 一時的なエラーの可能性もあるので失敗しても何度かはリトライ
      • エラーのあったファイルを変換サーバに POST
      • あとは変換サーバ側でいい感じに Issue に登録してくれる

Boost.Graphの設計と、最短経路アルゴリズムの使い方いろいろ

  • Boost Graph Library の設計がメインのお話。
  • グラフのデータ構造とアルゴリズムのライブラリ。STL の概念に基づく。後発のグラフライブラリに大きな影響を与える。
  • グラフとは…
    • 頂点 vertex と辺 edge からなるデータ構造
      • 棒グラフや折れ線グラフとは関係ない。
    • 辺が方向を持つかどうかで有向グラフ(directed)、無向グラフ(undirected) の2つの分類があるよ。
    • ex)
      • 電車の路線
      • 道路
      • network
      • ファイルの依存関係
      • クラス図
      • 行列
        • チェス盤
      • etc...
  • グラフの用途
    • 最短経路を求める
    • 一筆書き
    • ネットワーク分析
      • コミュニティ、情報を広げる中心にいるのは誰か
      • コミュニティ同士を繋ぐ架け橋、またはボトルネックは誰か
    • ページランクの算出 (Google検索)
    • 迷路を解く
  • 文献
  • グラフ型
    • adjacency_list ...隣接リスト
    • adjacency_matrix ...
  • 操作
    • グラフ型への統一的な操作を提供
    • グラフ型が直接持つインタフェース(メンバ)を使うのではなく、オーバーロード可能なフリー関数を介してグラフを操作。
    • Boost.Graph のコンセプトを満たす、あらゆるグラフ型を適用可能。
      • std::vector もグラフ型として使えるよ 
        std::vector<Hoge> g;
proc_graph(g);
    • vertices() や edges() といったグラフコンセプトのフリー関数を、 グラフ構造とアルゴリズムの中間インタフェースとしている。
      • STL の反復子コンセプトと対を成すもの、と考えればいい。
  • プロパティマップ
    • グラフには様々な種類のデータが付加される。
    • ex) 電車の路線図
      • 頂点 ... 駅名
      • 辺 ... 駅間の距離
      • 全体 ... 路線名
    • adjacency_list のテンプレートパラメータ
      • OutEdgeListS ... グラフの隣接構造を表すためのコンテナ
        • vecS: std::vector
        • listS: std::list
        • setS: std::set
      • VertexListS ... 頂点コンテナ
      • DirectedS ... 有向か無向か
      • VertexProperties ... 頂点
      • EdgeProperties ... 辺
      • GraphProperties ... グラフ全体
    • 取得と設定は boost::get(), boost::set() を使用。
  • 使い方いろいろ…
    • dijkstra_shortest_paths() に絞ってみていくよ
    • 最短経路を求める
    • 先行マップ
      • ある頂点の前に通る頂点を集めた辞書
      • 目的地 Z を与えると、 Z の前を通る頂点 F が取得できる。
      • 逆順の最短経路を頂点のリストとして取得できる。 
        std::deque<Vertex> route;
for(Vertex v  to; v != from; v = parents[v]){
        route.push_front(v);
}
route.push_front(from);
      • 先行マップは、 dijkstra_shortest_paths() に boost::predecessor_map() という関数を通して渡していた。
        • boost::predecessor_map() : 名前付き引数を使う関数。(使わないバージョンもあるけど引数やたら多くて大変)
    • 最短経路全体でどれくらいの距離があるか知りたい場合は、 distance_map を指定する。 
      boost::dijkstra_shortest_paths(g, from,
        boost::predecessor_map(&parents[0]).
        distance_map(&distance[0]));

int d = distance[to];
    • イベントビジター ... アルゴリズムの各ポイントで、任意の関数を呼び出せる。 
      struct MyVisitor : dijkstra_visitor<> {
        template <class Vertex, class Graph>
        void discover_vertex(Vertex v, const Graph&)
        { ...event... }
};

boost::dijkstra_shortest_paths(...
      • 特定の頂点が見つかったら例外を投げて、アルゴリズムのループを脱出する。
      • 既存のアルゴリズムを使って、新たなアルゴリズムを作る。
        • dijkstra_shortest_paths() は、幅優先探索をイベントビジターでラップして作られている。
      • コルーチンでアルゴリズムを中断
      • アルゴリズム計算状況の可視化。
  • アルゴリズムの設計
    • ユーザビリティとは、その分野に精通していないユーザーにとっての公開されているアルゴリズムインタフェースのわかりやすさ。 同時に、精通しているユーザーにとってのアルゴリズムを構成できる幅のこと。
Note: See TracWiki for help on using the wiki.