憂鬱な午後のひととき
涼しくて眠れたので少し回復.
とある確率でカオスでタイムマシンな勉強会に参加.
こちらもまた懇親会に参加したかったけど眠すぎたので諦める. 来週使う予定の会場はもう少し広くできることを知った(今更!).
明日確認してみる.
寝不足と夏ばてで完全ダウン. まいった.
数論暗号勉強会. ようやくグレブナー基底へ. 懇親会は参加したかったけど眠かったので諦める.
・PRML10章の山場, 混合ガウス分布の変分下界Lの導出を書いた(
prml10.pdf).
そのあとの予測分布がスチューデントのt分布になるところも書いといた. 小指が腱鞘炎になりそうだ.
・初めてatndを立てた.
x86/x64最適化勉強会1
参加メンバーがいい感じでちょっとどきどき.
・PRML9章の
計算の説明を書いた.
10章ではこのあたりの計算のオンパレードになる. ただいま作成中.
間違いを指摘してくださっても何も出だせませんが, 少し計算力があがるかもしれません.
・8/6にx86/x64最適化勉強会をサイボウズ(飯田橋)でしようと思います. 十数人規模で中級者向け. ただいま発表者募集中.
第1回 データ構造と情報検索と言語処理勉強会 #DSIRNLP参加
会場提供のmixiの方, ありがとうございました. 勉強会の内容はおいといて(えっ), 今日の一番の衝撃は
n_shuyoさんの記事のあんちょこって何?という人が複数いると知ったこと.
そんなに年齢が違わないはずの
y_shindohさんまでもが….
そういう若い人たちは自分で計算しなさいということですね.
#PS. リンクは
https://github.com/herumi/prml/raw/master/prml4.pdfなどの方がダイレクトでいいかな.
PRMLの「計算がちょー大変」という10章を一通り読んだので計算導出部分を書き始める.
だれかノートに書いた数式を自動的にTeXにしてくれるシステムしらんかな.
『雨にも負けず粗茶一服』(松村栄子)
東京の茶道の家元の息子が大学受験をすっぽかして車の免許取りにいってたのが見つかって半ば勘当状態で家出する.
なぜか京都の友達の友達の家に転がり込む. 凄いやなやつなのにそんな見ず知らずの人を留めてくれるかいなと思ったり.
でも全体を流れる京都弁とこれでもかという茶道の話が何故か心地よくてついつい読んでしまう.
この文体はただ者ではない!と思ったら純文学の人なんや. へんちくりんな人もたくさん登場して非常におもろい. 他の作品も読んでみよう.
# 私も親に仏壇に向かって「まんまんちゃんあんしいや」って言われてたな.
9/16(金)に開催される日本応用数理学会2011年度年会 「数論アルゴリズムとその応用」(JANT)の
研究集会プログラムを公開しました.
Project Euler 161
上から横に1ラインずつ埋めていくことを考える. トリオミノの縦の最大長は3なので, ある1ラインが埋まったときの下2ラインのパターンの種類を考える.
横9とすると2ライン分では2
19通り(実際にはそれよりは少ない). その値に関するDPをする.
状態数が少ないのでHaskellのSTモナドやUArrayを使わずData.MapのinsertWithでDPをしても数秒で答えが出る.
いつも勉強させてもらってる(そしてよー, こんなにうまく解けるなーと感心してる)
jeneshiccさんや
inamoriさんのコードよりも速いって初めてじゃなかろうか.
多分, もうそんなことは無いだろう(相当前に解かれたやつだし).
初クーラー. 暑すぎる.
Project Euler 237
時計回りに90度回転する. 横一列の4個を一組として考える. 全体で一つにつながっていけないことを考えるとその可能なパターンは意外と多くない(15個).
しかも上から下に一ラインずつ追加していくとき, その可能性は一つ上のラインだけで決まってしまうことがわかる.
"||||"だけは例外で, 一つ上の状態がそのまま降りてくるので状態が変わらないとして扱う.
でその各パターンがいくつあるかに関するDPができる.
最後は"└┘└┘"か, "└──┘"のどちらかにくっつけるやつを拾う.
ただそれだと縦に10
12つなげるのは気が遠くなる. そのパターンの漸化式をよく見ると必要な計算は5x5の行列の巾乗(実はもっと減らせるらしいが)をすればよいことが分かり,
log(10
12)でできる. 面白い. それならHaskellでナイーブに実装しても一瞬. とわかるまで何時間もかかった. 自分は頭悪いなあと思う.
11日のところでreadv相当のシステムコールはWindowsには無いと書いたら,
egtraさんから
WSASendはできるよ, boost::asioも使ってるよというご指摘があった.
すいません知りませんでした. ありがとうございます. 単なるsendの非同期版だと思ってました. それからboostのソース見たときはどこ見てたんだ. 恥ずかしい.
C++0xでUTF-8/UTF-16の読み書き
下で「多分C++には拡張されて無い」なんて偉そうなこと書きましたがC++0xで追加された機能がVC10には実装されてました. すいません.
codecvtというヘッダを使います. gcc 4.6.0にはまだこのヘッダは無いみたい.
Windowsだしwchar_t = UTF-16でよいよね.
#include <fstream>
#include <codecvt>
#include <memory>
int main()
{
{ // ワイド文字列をUTF-8で書き込む
typedef std::codecvt_utf8_utf16<wchar_t> Cvt;
std::unique_ptr<Cvt> cvt(new Cvt());
std::locale loc(std::locale(""), cvt.get());
std::wofstream ofs("utf8.txt", std::ios::binary);
ofs.imbue(loc);
ofs << L"utf8で書き込む" << std::endl;
}
{ // ワイド文字列をUTF-16で書き込む
// UTF-16(LE)
typedef std::codecvt_utf16<wchar_t, 0x10ffff, std::little_endian> Cvt;
// UTF-16(LE) + BOM
// typedef std::codecvt_utf16<wchar_t, 0x10ffff, static_cast<std::codecvt_mode>(std::generate_header|std::little_endian)> Cvt;
// UTF-16(BE) ; default
// typedef std::codecvt_utf16<wchar_t> Cvt;
std::unique_ptr<Cvt> cvt(new Cvt());
std::locale loc(std::locale(""), cvt.get());
std::wofstream ofs("utf16.txt", std::ios::binary);
ofs.imbue(loc);
ofs << L"utf16で書き込む" << std::endl;
}
}
std::codecvt_utf8をlocaleに設定するとワイド文字列をUTF-16にしてファイルに書き込みます.
std::codecvt_utf16はデフォルトのテンプレートパラメータはUTF-16(BE)のbig endianなのでUTF-16(LE)を使いたいならstd::little_endianを指定する必要があります.
BOMも欲しければstd::generate_headerとの論理和とします.
ただし, それは第3パラメータなので第2パラメータMaxcodeも指定する必要があります. これは使う文字のコード番号の最大数でUCS-2なら21ビットなので0x10ffffです. 微妙に面倒ですね.
std::getline 知らんかった・・・
VCでwifstreamを使ってUTF-16のファイルをうまく読めないとあるけど, それは逆.
wifstreamはマルチバイトファイル(つまりは通常cp932で書かれたファイル)を読んでプログラム中のwchar_tなものに入れるための関数.
#include <string>
#include <fstream>
#include <iostream>
#include <locale>
int main()
{
std::locale loc("japanese");
std::wcout.imbue(loc);
{
std::wofstream ofs("a.txt");
ofs.imbue(loc);
ofs << L"こんにちは hello" << std::endl;
}
{
std::wifstream ifs("a.txt");
ifs.imbue(loc);
std::wstring str;
ifs >> str;
std::wcout << str << std::endl;
}
}
localeをjapaneseにしてifsにそれを設定してワイド文字を書き込むとcp932の文字コードに変換されてストリームに書き込まれる.
wifstreamでそのファイルを読み込むとマルチバイト文字列がワイド文字列に変換されてwstringに格納される.
上記プログラムを実行してできたa.txtをテキストエディタで開いて確認すればよい.
ちなみにfopenでVCで拡張された
ccs属性を指定すればUTF-16やUTF-8のファイルを読み書きすることはできる(多分C++には拡張されて無い : ←嘘
C++0xでUTF-8/UTF-16の読み書き参照).
ccsにはUTF-16なら"UNICODE", UTF-8なら"UTF-8"と指定する. 下記プログラムはUTF-8で書かれたファイルを生成する.
#include <stdio.h>
int main()
{
FILE *fp;
if (fopen_s(&fp, "b.txt", "w,ccs=UTF-8")) {
puts("err");
return 1;
}
const wchar_t str[] = L"こんにちはfopen with UTF-8\n";
puts("write");
fwrite(str, sizeof(*str), sizeof(str) / sizeof(*str) - 1, fp);
fclose(fp);
}
readv, writevというシステムコールは以前, boost::asioのまとめてバッファを書き込む関数の実装を追っかけていて, 知った.
残念ながら今のところWindowsには同様のシステムコールはなさそう(←間違い. あります
15日).
ためしてガッテン 数字トリック見破り術
なかなかよくできていた. 定番の勘違いしやすい確率問題を, 条件付き確率という言葉を出さずに絵で説明していた.
相当どうやって解説するかに時間を割いたんじゃないやろか.
『ベイズ統計と統計物理』(伊庭幸人)
PRMLを読んでたらイジングモデルが出てきた. 統計物理(統計熱力学)は大学のときに一通り勉強したけど殆ど覚えてないし, 教科書は実家.
どうしたもんかと思ったら, この本がたまたま手元にあって, 実は7年ほど前に読んでたのだけど今回再読した. で, 大正解.
PRMLで, もやっとしてた部分があちこちクリアになった. 似たような人*, ぜひ読むべし. 薄いし.
(*)「1.5 人生は辛い」はPRMLのグラフィカルモデルにおける推論の肝. 3章はMCMC.
4章は事前分布って何?とか, モデルエビデンスの話など.
2章「統計物理アナロジー」を少しだけまとめてみよう.
たとえば結晶構造で分子のつながりぐあいを考える. 各分子が線で繋がっていて, それぞれの繋がりかたにある種の制約を入れたり, 状態があると考える.
各分子の状態xに対してその局所的なエネルギーをEloc(x)で表し, 全ての和を全体のエネルギーとする.
E(x) = Σ E_loc(x)
このとき平衡状態における状態xの出現確率P(x)を次の式で与える. kはボルツマン定数, Tは温度.
P(x) = exp(-E(x)/kT) / Σ_x exp(-E(x)/kT)
エネルギーが高いものはあまり起こりにくく, エネルギーが低いものが起きやすい.
出現確率の高いものが現れやすい状態である(というモデルを考える). これをカノニカル分布(ギブス分布, ボルツマン分布とも)という.
局所的な状態が+/-やS/Nの2値なものを考えるのがイジングモデル. エントロピーや誘電率, 磁性体の熱によって性質が変わる相転移などの現象を説明できて成功を収めた.
さて, 条件付き確率分布の式を眺めてみる.
P(x|y) = P(x, y) / Σ_x P(x, y)
yやTに相当するものは互いに無いけどそれはとりあえずおいとくと, これってなんとなく形が似てるよね, という話.
局所的な状態から全体の形が決まる部分とか, 解がただ一つではなくて複数の答えの重み付きの重なりぐあいだとかも.
なら, 歴史ある統計物理の様々な手法を確率的推論に使ってみよう. PRMLではイジングモデルを使った2値画像のノイズ除去の例が載ってるね.
そういう手法の中で大成功したものの一つがMCMC(マルコフ連鎖モンテカルロ)ということなんだそうな.
おもろい.
Shibuya.pm 夏の正規表現祭り
サイボウズ・ラボユースで
sinya8282さんが高速なgrep(or 正規表現エンジン)を作るというのをやっていて, それの最適化まわりの指導担当なので見に行った.
今回はみな正規表現ネタなのでperlを殆ど知らない私でも大丈夫.
彼の発表は正規表現の否定の話でみなの反応も上々. 次は作ってるやつの話をしたいね.
#というか自分がやりたい.
懇親会では, 今DeNAにいる@kazuhoさんや
樋口さんとdeepな話でもりあがる.
あっと言う間に終わってしまった.
mixiの会場は
広くて綺麗. どうもありがとうございました.
6月末からの急激な暑さでへたってる. 動く気になれない.
昔
御意見は光成滋生<herumi@nifty.com>までお願いします