トップ «前の日記(2009-03-19) 最新 次の日記(2009-03-23)» 編集

Route 477



2009-03-22

[ruby] 「超戦略的ブロガー」をリリースしました (powered by はてな)

この記事 に感銘を受けて、任意の文章を超戦略的に変換するサービスを作りました。 (本体 / ソース)

 このサービスは任意の文章を知的かつストラテジックに変換します。
   ↓
 この戦略的なサービスは任意の戦略的文章を知的かつストラテジックに変換します。

どうぞご利用ください。 (このサービスははてなオフィス の電源(power supply)と無線LAN環境を利用してリリースされました)

[event][perl] Kansai.pm#11の参加メモ

Kansai.pm #11 の適当なメモを取ったので適当に公開します。

あんまり人に読ませることを想定していません。他のレポート を補完する感じで読むといいと思います。

 13:30〜
 いつもと違う形式
 id:naoyaのリクエスト
 若い人に
 飲み物は冷蔵庫からご自由に(!!)

Cell Challenge 2009 参戦記 : PFI 吉田(oxy)さん

 Perlではない(特別講演w)
 Cellのコンテスト
 コンピュータ全体の知識がないと勝てない
 京大情報学研究科M2->D1
 理論計算機科学
 P != NPを証明したい的な分野
 P: 計算機で解ける
 NP: 計算機で多項式時間できっとできないだろう
 エンジニア@PFI
 Anthy
 ICPC
 「関連エントリ機能」
 === Cell Challenge
 マルチコアを効率的に利用したい
 08秋: 参加しないか
 Cell=めんどくさそう
 08 12月: 問題発表(編集距離)
 PFIの同僚(chun)に誘われたので、参加
 チーム名はPFI社長のSkype名から
 (>ω <)
 09 1月:Cell the Hack
 別のコンテスト
 MT(メルセンヌ・ツイスター)を高速化
 09 2月:予選トップ通過
 09 3月:昨日本戦終了
 勝てるといいなぁ
 === なぜここでCell Challenge
 高度なプログラム: アルゴリズムとアーキテクチャに関する深い知識が必要
 Perl知らないので
 Webフレームワークは習得しないようにしている
 === 既定課題
 編集距離
 A = weight ; B = write
 weight -> weighte -> wrighte -> wrihte -> write
 A,Bの距離は4(以下)である
 総当たりすると、3以下ではできないことがわかる
 AとBの間の編集距離を、Cellを使ってできるだけ速く求めよ
 A,Bの長さは一定以下
 A,Bの長さは128で割り切れる
 1文字は1&#12316;255
 === Cell
 SPE
   SPU * 8
   SXU
   LS
   MFC
 PPE
   PPU
 SPEとPPE、全然違う2種類のCPU
 SPEは8個(Core2Duoどころではない)
 # PS3は8つ中7つしか使えない
 3.2GHz
 PPE: L1 32KB, L2 512KB
 SPE: LS 256KB, 128bitのレジスタが128個も(!!) SIMD(複数の演算を同時に行える, SSE/MMXみたいな) 重たい計算に
 === DPによる解法
 O(nm)で解けることが知られている(n = |A|, m = |B|)
     - w e i g h t
   - 0 1 2 3 4 5 6
   w 1 0 1 2 3 4 5
   r
   i
   t
   e
 左上から順に表を埋めると、右下が答え
 (上と左と左上の値から計算できる)
 サンプルプログラム:DPを7並列
 n,m=2^17 で43秒くらい (10万×10万) (並列なしならもっと)
 これを
 予選0.2秒、
 本戦0.14秒まで縮めました
 300倍くらい
 === 手法
 1. アルゴリズム的に
 2. SPE一個単位で
 3. SPE複数個単位で
 === 1. アルゴリズム的に
 SPEが7個でも7倍にしかならない
 アルゴリズムを改善すれば100倍くらいに
 128bitのレジスタを使えば、128要素を同時にもてる
 ビット並列化[H03]
 ベクトルの「横に1減っているか」「縦に1増えているか」みたいな情報(D0 HP HN VP VN)を考えると
 j列目のやつは、j-1列目のやつから計算できる
 これらを使うと編集距離が簡単に計算できる
 これらを128bitレジスタで計算しよう
 128並列
 DPの表は並列化しにくい
 が、依存関係が「足し算の繰り上がり」になってるのでハードウェアでできる
 残り7倍
 === 2. SPE一個単位で
 パイプライン
 1命令=数クロック
 複数の命令が同時に走る (-> スループット、クロック数の向上 / レイテンシの悪化)
 データハザード (ストール)
 命令の利用するデータに依存関係があると、後ろの命令が前の命令を待つ(遅い)
 ループアンローリング
 forを一部展開する -> 計算順序を調整する(コンパイラ/手) -> ハザードを減らせる
 これだけで2,3倍になったりする
 デモ
 おおー
 # なんで
 ハザード対策: 投機実行
 128bitの加算がないので、32bitの加算*4(SIMD)を使う
 繰り上がりでハザードが起こる
 じゃあ繰り上がりあり/なしを同時に実行して、後から選ぶようにするとハザードが減る (依存関係の遅延評価)
 足し算の高速化
 こうすると速くなりそう(実装できず)
   xxxx
   xxxx
   xxx
   xx
   x
 スーパースカラ
 Cellにはパイプラインが2つある (Even/Odd)
 EvenとOddを効率よく使うように等価変換
 === 3. SPE複数個単位で
 SPEは7個だけど、普通にやると7倍速も出ない
 テーブルを128c*128のブロックに分割(cは適当な数)
 ブロック間は、端っこ以外依存がない
 ブロックの計算が終わったら、次の計算を担当するSPEにその情報を渡す
 PPEをマネージャとして
 cをいくつにするか?
 cが少ないと:SPE間のやりとりが増える
 cが大きいと:レジスタ不足、コンパイル時間(ループアンローリングしすぎ)
 16くらいが良さげだった
 が、常に16ではダメ
 単語の長さによって、最後の計算がSPE1つだけになったり
 最後までSPE7つ使うようにしたい
 (x+i)/nを足していくとsumになる (5,6,6,6,6とか)
 これを使ってcを決める
 |A|が128xだとすると、nは7の倍数かつceil(x/n)が16以下になってほしい
 ページング
 プログラムから見えるのは仮想アドレス
 ページング=仮想アドレスと実際のアドレスとの対応
 SPE側でページングされてないメモリにアクセスすると、100~1000万クロックもかかってしまう
 でもPPE側なら速い
 PPEで事前にメモリ初期化→ページフォールトをわざと起こす
 デモ(1<<24バイト)
 === まとめ
 アルゴリズム的な改善が一番大事(bit並列化)
 有名問題なら、本や論文でいくらでも
 その他の最適化=*コンピュータに合わせた計算*をする
 ので、コンピュータの知識がないとだめ(パイプライン、ページング、キャッシュ、SIMD)
 その後の最適化=問題に依存したパズル
 ゴルフとかっぽい
 流行もいいけど、基礎知識の方にも面白いものがいっぱいあるよ
 === Q/A
 * C言語?
 C。アセンブラはつかわず
 * bit並列化の手法は?
 論文から。
 研究者は何百万
 * レジスタに割り付けるようなコードの確認は?
 printfで確かめる
 * アセンブラだとコード作るだけで大変だよね
 暇だったらやってたと思う(コンパイラの生成コードを参考にしたりとか)

HTMLからの本文抽出 : id:tarao(伊奈)さん

 院生
 専門はλ計算、型理論、証明支援・自動証明とか
 Javaに動的型を入れる研究
 C++, OCaml, Ruby, Perl(半年くらい), JavaScript, TeX
 JSで定理照明器を書いた
 Greasemonkeyで、問題ページを開くと自動的にsubmitするように
 === Perl
 01年:掲示板CGIの改造
 Perl嫌い病
 08年:はてなインターン
 オブジェクト指向
 CPAN
 完治→CPAN Authorになった
 === 背景
 RubyのExtractContent -> Perl移植(HTML::ExtractContent)
 バグを直したり、精度を向上したり
 サイボウズラボでも使われてるとか
 なぜ本文抽出?
 例えばブクマページ
 単純にHTMLからタグを省くだけだと、メニューとかまで入ってしまう
 例えば検索エンジン
 「この記事へのトラックバック」みたいな文字列まで引っかかると困るよね
 既存のアプローチ
 * HTML::ContentExtractor
   * HTML::TreeBuilderベースで遅い、ごみが残る
 * HTML::Content::ContentExtractor
   * トークンに分解、日本語には不向き
 * Webstemmer(Python)
   * 2つのページのdiffを取る感じで本文抽出
   * サンプルを与えて学習する
   * 一般のサイトで十分な性能が出ない
 今回の手法
 正規表現(高速)
 本文らしさをヒューリスティックに
 === 実演
 useしてnewしてextract(str)して、as_text(テキスト)とかas_html(HTML断片)を取るだけ
 HTMLは断片なのでvalidとは限らない(閉じタグだけがあったり)
 デモ
 lifehacker.jp
 youtubeとかは無理(文章が少なすぎて「ようこそ&#12316;」以下が引っかかる)
 ニュースサイトには強い
 2chまとめブログは苦手(1: 以下、名無しさんが&#12316;だけが取れたり)
   レスはブログだと「コメント欄」に構造が近い
 === アルゴリズム解説
 1. 明らかに要らないものを落とす
   - headタグ
   - display: none
   - <!-- -->
   - など
 2. HTMLを適当なブロックに分割
   - div
   - p
   - 開始タグのところで切る
 3. 各ブロックにスコアを
   - 本文っぽさ
 4. つながっているブロックをまとめる(クラスタ化)
   - クラスタのスコア=ブロックのスコアの合計
 5. スコアの一番高いクラスタが本文
 本文っぽさ
 - 句読点がいっぱいある
 - テキストノードの文字列が長い
 - リンクばかりが並んでいるとこは本文っぽくない
 クラスタ化
 高スコアのブロックが連続しているところをつなげる
 低スコアのブロックは、クラスタの切れ目っぽい
 閾値の設定は職人技w
 傾斜配点
 スコアは下にいくほど減点(コメント欄のため)
 === 発展
 駄目なサイトもある
 もっと確実にしたい
 フレームワーク化
   複数の抽出エンジンを試す
   Chain on Responsibilityパターン
   サイトに特化した抽出エンジンを用意(ニコニコ、youtube、amazon, ...)
   GoogleAdsenseのタグを使う
   RSSフィードを使う
   複数試して、一番良い結果を選択する
   取ってきた文字列が一番長いものを選ぶ
   # はてブではこれくらいやってるらしい
   日々のチューニング
 === Q/A
 * 日本語以外もいけそうだよね
 英語はOK
 文字の長さ
 * 複数の本文セクションがあったときは?(ブログのトップページとか)
 傾斜配点によって、一番最初のものが選ばれるはず
 そういう用途にチューニングされている
 * GoogleAdsenseは決めうち?
 他のものも使うようになっている。
 前のより2倍長かったら採用とか、選び方もヒューリスティック
 * HTML5対応
 まだ対応してない
 nanto_viさんパッチお願いしますw

はてな本棚

 異常にPerl力の高い本棚(見たことないPerlの洋書とか)

Perlで学ぶコルーチン : id:hakobe932さん

 M1
 ソフトウェア開発支援みたいな研究
 はてなアルバイト
 === Perl
 05年:スクリプト言語に出会う
 Python -> Ruby -> Perl
 08年:はてなインターン
 CPAN Authorに
 === コルーチン
 1/31 関西Ruby勉強会-11
 Ruby 1.9.1リリース -> Fiberについての発表が
 それPerlでも
 コルーチンとは
 サブルーチンはコルーチンのspecial caseだ! (Knuth)
 サブルーチンとは
   メイン                 サブ
   ---------------------------------
   foo
   bar()   --呼び出し->   sub bar {
                           ...
           <-リターン--   }
   baz
 コルーチン
 処理を中断したり再開したり
 coは協調のco
   A                      B
   ---------------------------------
   resume   --呼び出し-> ...
                         ...
   ...      <------中断  yield
   ...
   ...
   resume   -----再開->  ...
                         ...
                         ...
   処理の実行状態を簡単に扱うことが出来る
 === 使ってみよう
 Perl(5)では提供されてない
 が、それCPANで
 search.cpan.org -> coroutine-> 38件
 use Coro;
 XSで3000行
 Coro::State(継続オブジェクト)
 PerlのスレッドとCのスレッドを駆使
 スレッドをwaitさせとけば状態を扱えるよね、みたいな
 call/ccも実装できる、らしい
 Coroはコルーチンだけじゃない
 並行処理ライブラリ群
 scheduler, async, semaphore, channel, event driven ...
 Coro::Stateを使うと純粋なコルーチンが使える
 けどあまり使いやすくない
 CoroをベースにFiber.pmというのを作った(Ruby1.9のFiberみたいなインターフェイス)
 yieldで、中断時に値が返せるよ
 github
 例
   use Fiber;
   my $f = Fiber->new(
     sub{
       ..
       Fiber->yield;
       ..
     }
   );
   $f->resume; // subからyieldのところまでが実行される
   $f->resume; // yieldの次から最後までが実行される
 === 実用コルーチン
 実行状態を簡単に扱う
 宇宙船の例(上・右・下・左)
   do { $s->move_up; Fiber->yield } for (1..100);
 「いま何回目のループか」みたいな状態変数を用意する必要がない(Fiber内に内包されている)
 複数の宇宙船を平行動作させるのが簡単
 # 終わったFiberをresumeすると例外
 ジェネレータ
 値の列を生成する手続き(イテレータの兄弟)
 列を事前に全部生成できない・したくないときに有用
 Python, C#, JS1.7では言語の機能
 これコルーチンで
 無限factorial
   ..
   while(1){
     $val = $val * $n++;
     Fiber->yield($val);
   }
   ..
 resumeする度に次の値がもらえる
 無限ループだけど無限実行にならない!
 ステートマシン
    (1)  ->  (2)
     ^        v
    (4)  ->  (3) ->  (5)
 状態=コルーチン、状態遷移=コルーチンの切り替え
 Fiber->yield($state2)みたいに、中断するときに「次の状態」を返してやる
 # 状態どうしが相互参照しているとGCできないかも...?
 # 最後のステートで参照を切ってやればいいはず
 並行処理
 コルーチン=「明示的な切り替えが必要なスレッド」
 # これを「ノンプリエンプティブ」という(スレッドが勝手に切り替わる方はプリエンプティブ)
 勝手に切り替わらないので、同期処理がスレッドほど複雑にならない
 Coro::Semaphore, Coro::Channel, Coro::Event
 === 利点と欠点
 Pros
 - 状態管理がシンプル(ゲーム(Luaとか))
 - 並行処理がクリーンに
 Cons
 - それほど使われてない
 - 既存のクラス・クロージャ・メソッドで同じことができてしまう
 === Q/A
 * resume(1)みたいに、再開時に値を渡すことは可能?
 できる
 * RubyのFiber.yieldは、なぜFiberがレシーバ?(インスタンスでなく)
 Coroだと メイン->yield みたいに、レシーバを指定する(これはちょっとめんどい)
 呼び出し時にスタックに積み、resume時にスタックトップを再開
 * RubyのFiberもスレッドで?
 VMレベルだと思う
 # 僕もスレッドじゃないと思うけど、確信がないなぁ
 Coroには「こうするとcall/cc」みたいなサンプルが載っている
 (call/ccができるということは、コルーチンくらいできるよね)
 # C#だとプログレスバーを出すのにジェネレータを使うらしい

スペルミス修正プログラムを作ろう : id:naoyaさん

 「もしかして:○○」
 正しい答えを推定
 いろいろな手法
 - 辞書との比較 (今回紹介する)
   - 字面が似ているものしか訂正できない
 - 検索ログなどから推測
 今回の手法
 はてなキーワードを辞書として使う
 (間違った)単語を与えると、訂正候補を表示
 考え方
 辞書に正解がある
 入力と正解を比較して、「誤り度」をスコア化
 編集距離(本日2回目)を使う
 文字の挿入・削除・置換を何回使えば正しくできるかの値
 動的計画法
 # これをビット並列化すると超高速になるw
 CPANではText::Levenshtein, Text::LevenshteinXS
   * Unicode非対応
   * パッチを書くか、自前で
 20万単語との編集距離を計算するわけにはいかない
 対象をNグラムで絞る
   例:bi-gram(2文字)
     bo -> aboard, about, border, ...
 入力が"bord"なら bo + or + rd -> それぞれをbi-gramインデックスで引く
 2回以上ヒットするものを対象に編集距離を計算
 編集距離が同じだった場合どうするか
 Web上でよく使われる語を採用 (DF, Document Frequency)
 はてブのデータ(これは非公開)を使った
 編集距離を改善
 Levenshtein距離は、何文字目が間違ってても同じスコア
 Jaro-Winkler距離: 前の文字ほど重要とみなす (伊藤xxを佐藤xxと間違う人は少ないだろう)
 CPANのはUnicode非対応
   http://github.com/naoya/perl-text-jarowinkler/
   Luceneからの移植、Unicode対応
 計算方法
 「雑音のある通信路モデル」
     W                    Y
   情報源->符号化->通信->復号->出力
                    ^
                    雑音
   音声認識とか、仮名漢字変換とか
 YからWを推定したい。
 argmax_W P(W|Y) Yを観測したとき、正解がWである確率(事後確率)
 ベイズ推定
 P(Y|W): 尤度、今回は編集距離
 P(W): 今回はDF
 参考文献:IIR (Introduction to Information Retreival) など

注意

このへんから集中力がなくなったので適当になります、ごめんなさい(´・ω・`)

PerlMolの紹介 : 樋口さん

 www.perlmol.org
 化学構造情報
 フォーマット変換とかSDFのパースなど
 CPANで入る
 いろいろなフォーマット
   MOL形式
   - 原子の結合情報
   PDB形式
   - 巨大分子の各原子の立体座標
   SDF形式
   - 原子の結合情報とか
   SMILES
 例:アラニン
 MOLファイル:NとかCとかOとかHが書かれている
 use Chemistry::Mol;
 「オープンソースで始める
 ゲノム・プロテオーム・メタボローム解析」
 CPAN, BioPerl, PerlMol, DBD/DBI, Plagger(ちょw)

名札メーカー : 橋本さん

 名札PDFを作成する
 ユーザアイコンを自動取得
 Perl + PDFJ + CGI::Application

ベイズ理論と POPFile における実装例 : いいむらさん

 POPFile
 ベイズの定理
   P(Bi|E) = P(E|Bi) x P(Bi) / P(E)
   1         2         3       4
   1: メールの分類がバケツBiで合っている確率(これを知りたい)
   3: 分類Biのメールが届く確率
       = 受信メールのうち、分類Biのメールの割合
         学習するほど高くなる
   4: メールEが届く確率
       = ってそんなもの計算できない
         知りたいのは「どのP(Bi|E)が一番大きくなるか」なので、無視する
   2: 分類Biの中からメールEが取り出される確率
       = これも大変
         メールを単語ごとにちぎって、その分類から推定する
         各単語の分類があまり相関しないなら(?)わりとうまく行く

 実装
 Classifier::Bayesのclassify関数

2008年Kansai.pm活動報告&Strawberry Perlの紹介 : lapis25さん

 Kansai.pm = Kansai Perl Mongers
 技術・学術・飲み会wのバランス
 2008年
 - フレームワーク勉強会
   Perlばっかりでした
 - Kansai.pm #9
 - OSC 2008
 - Kansai.pm #10
 - KOF 2008
 2009年(予定)
 - JPAセミナやりたい
 - ミーティング、あと1回は
 - OSC, KOF出展
 - 募集中
   - どんなイベントがしたい?
 アンケート
 普段の言語
 内容はよくわかった?
 混乱している人は:
 WindowsでPerlするならStrawberry Perlおすすめ
 WindowsでPerl
 - Active Perl
 - cygwin
 - VMWareでLinux
 - XAMPP + Perlアドオン
 - Strawberry Perl [new!]
   - WindowsだけどPerlつかってない
   - Active Perlつかってる
   - Perlつかってみたい
 おすすめポイント
 - gccやmakeが入ってる
 - CPAN Shellが普通に動く
   - Active Perlだと専用ツール経由になる
 - 最初からモジュールがいくつか追加されてる(Bundle::CPAN, Bundle::LWPとか)
 - 5.10と5.8.8が選べる
 - リリースは年4回くらい(比較的緩やか)
 - 通常版のインストールはc:\strawberry固定
   - 空白問題とかを回避
   - 上級者には指定ディレクトリに入れるためのパッケージも。
 - ポータブル版(beta)
   - USBメモリとかでPerl環境を持ち歩く

XSのはなし改めSocial SKK : antipopさん

 Perler, Emacser, アイドル
 はてなエンジニア(はてなボトル、Myはてなとか)
 前回の発表以降:
 Vimmer転向を宣言したが、断念
 Lux::IO
 Term::ANSIColor::Markup
   フォントタグみたいな形式で色指定
 軽い話
 ソーシャルが流行り
 Social IMEが話題
   - MS IMEの「単語登録」みたいなのをWeb経由で自動的に共有
   - Web APIがあるので、クライアントを自由に作れる
 が、SKK使いだし...
 AquaSKK
 これをSocical化したら?
 -> id:shunirrさんがRubyでやってた(SocicalIME特化)
 せっかくなのでPerlでもやってみた
 SKKとは
 IMEの一種
 連文節変換ではなく、送りがな単位で変換(「oku R igana」とか)
 文節の区切り間違いがない(当たり前w)
 いろいろな辞書ファイル
 skkserv
 変換候補の返却サーバ、たくさん実装がある
 プロトコルさえ守れば、何を返してもいい→Social IMEで検索
 App::SocialSKK
 socialskk.plをSKKサーバとして使うと、変換時にSocialIMEを使うようになる
 プラグイン方式なので、Wikipediaとか英辞郎にも対応
 はてブにも対応(おまけ)
   - 「ほってんとり」で変換→最新のエントリを次々に表示
 実装
 POE::Component::Server::TCP
 shipit!!(この場で公開)
本日のツッコミ(全2件) [ツッコミを入れる]
いまい (2009-03-22 22:10)

戦略的プロキシエラーですよ?

yhara (2009-03-23 22:06)

なおしました。ありがとうございます。