2012-04-05

Ｃ言語データ入力メモ

AOJなんかのオンラインジャッジで遊んでて、Ｃ言語のデータの入出力のことをあまり理解していないな、と長らく思っていて、最近ちゃんと調べたのでメモしてみる。わかってる人にとっては、息を吸うように自然とできていることだと思う。
今回はとりあえず、fscanfとfgetsの違いについて。
結論からいうと、fscanfは１文をそのまま読み込む、fgetsは１文読み込んだ後、改行('\n', ASCIIコード10)をつけるというだけの違い。

以下、コード例

#include <cstdio>
#include <algorithm>

const int MAX_BUFSIZE(1024);

int main(int argc, char* argv[]) {
	char buf[MAX_BUFSIZE];
	std::fill(buf, buf + MAX_BUFSIZE, 0);
	FILE* file;
	file = fopen("input", "r");

	puts("fscanf:");
	while(fscanf(file, "%s", buf) != EOF) {
		for(int i = 0; i < 20; i++) printf("%d ", (int)buf[i]);
		putchar(10);
		std::fill(buf, buf + MAX_BUFSIZE, 0);
	}
	fclose(file);
	
	file = fopen("input", "r");
	puts("fgets:");
	while(fgets(buf, MAX_BUFSIZE, file)) {
		for(int i = 0; i < 20; i++) printf("%d ", (int)buf[i]);
		putchar(10);
		std::fill(buf, buf + MAX_BUFSIZE, 0);
	}
}

以下、出力

見てのとおり、fgetsの場合は、最後に改行がつくので注意。
何故こんな細かいことを書く気になったかというと、デバッグでとても苦労してしまったから。仕様はちゃんと覚えましょう。
あと、オンラインジャッジで実際にコードを提出する時は、入力口を標準入力に変えておく。

ふつうのLinuxプログラミング Linuxの仕組みから学べるgccプログラミングの王道

作者: 青木峰郎
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2005/07/27
メディア: 単行本
購入: 35人クリック: 450回
この商品を含むブログ (145件) を見る

2012-03-05

メモメモ

研究室のメンバー＋αの人にちょっと使ってもらったユーザ類似度判定システムについて、現在の状況と問題点と、今後の方針などメモしておく。

まず、今のところ出来てるシステムの入力、出力について簡単に説明。

入力：
・N人のユーザが持っているテキストの集合
・TEXT = {text1, text2, ..., textN}　のようなイメージ
・Twitter, Facebook, Gree, mixiなどなんでもおｋ
・言語非依存

出力：
・各ユーザごとに、そのユーザに似ているユーザ上位３０人
・各ユーザごとに、そのユーザが興味をもつトピック上位３件、各トピックについてトピック語上位５０語

で、今後は
・Twitterで似ているユーザをまとめたリストを自動作成する

など考えている。
「こういう感じの人をウォッチしたい！」という要望がワンクリックで実現する。

以下、もうちょっと細かいところ。

このシステムは大きく分けて３つのモジュールで構成される。

１．入力データの前処理
２．クラスタリング
３．類似度の計算

１について

現在の状況：
・全入力データを形態素解析し、単語の頻度を調べる
・単語の頻度上位5%と、１回しか出ない単語を入力データから除去
・単語の少ないユーザを除去
・ステップ２の入力フォーマットにデータを加工

現在の問題点：
・除去するデータの選び方が雑
・類義語はまとめた方が良いのではないか？

今後の方針：
・未定

前処理は多分一番難しく、どうするのがベストなのか検討もつかない。泥臭い工夫や作業が必要そうなところである。

２について

現在の状況：
・クラスタリングにはLDAを使っている
・推定方法はCollapsed Gibbs Sampling
・トピック数は300、イテレーション回数250回。この数字を選んだ根拠は特に無い
・（加工後の）入力データの全単語数をW、イテレーション回数をIとおくと、計算量はO(WI)

現在の問題点：
・トピック数を自動で最適化できないか？
・計算にとても時間かかるしメモリも沢山消費する。並列化できないか？理屈としてはできるし、C++実装がオープンソースで公開されている

今後の方針：
・トピック数の最適化のためノンパラベイズに手を出してしまう？
・並列計算する

３について

現在の状況：
・各ユーザごとに、他ユーザとの類似度を計算している。評価にはユークリッド距離を使っている
・トピック数をK、全ユーザ数Uとすると、O(U^2*K)オーダーの計算量
・というのも、ユーザ２人１組の組み合わせが全部でU*(U-1)/2通り。各組について、ユークリッド距離計算するのにO(K)かかる。
・各ユーザのごとに、そのユーザが興味をもつトピックを出力している。ソート処理があったりで、計算量はO(U*KlogK)

現在の問題点：
・計算にとても時間かかる。多分、ボトルネックになっているのは類似度計算するところ。せめてユーザ数の線形時間にならないか？

今後の方針：
・類似度計算を並列化。多分がんばればできる。
・何も考えずにユークリッド距離使っているけど、他の評価指標も試してみたい。

2011-11-08

数論とかprojectEulerとか

数論とかprojectEulerとか
たしか10月頭くらいからprojectEulerで遊びつつ数論の勉強などしていた。「はじめての数論」が読みやすい。
その過程でチマチマ書いていたサブルーチンの使い方メモ。

ソースコードはこちら。ヘッダファイルだけど、実装まで全部書いてるのでリンク必要なし。
https://github.com/risuoku/oreore/blob/master/PE_usingNTL.h

以下の説明のうち、ZZという型はNTL(Number Theory Library)の一部である。
ZZを使うことでC++で多倍長整数を扱えるようになる。
類似のライブラリはいくつかあるようだが色々比較してこれが最も気に入ったとかいうわけではない。
ZZ→intのキャスト不可だったり初期化が面倒とか以外特に不満はないからなんとなく使っている。

typedef long long int L;

std::vector prime_vector_5000();
5000以下の素数をstd::vectorで返す。いわゆるエラストテネスのふるい。

std::vector Primes_under5000 = prime_vector_5000();
std::vector型のグローバル変数Primes_under5000の宣言。小さい数に対する素数判定に使う。

ZZ gcd(ZZ xl, ZZ xr);
xlとxrの最大公約数をZZで返す。

int gcd(int xl, int xr);
xlとxrの最大公約数をintで返す。

ZZ formula_p105(ZZ a, ZZ k, ZZ m);
「はじめての数論」p105ページにのってるアルゴリズムを実装したもの。a^k(mod m)をZZで返す。
7^327≡286(mod 853)のような計算が一瞬で終わる。計算量のオーダーはO(logk)。

L GetRandom(L max);
ランダムに選んだmax以下の整数をlong long intで返す。

bool PrimeJudge_onecount(ZZ n, ZZ a);
ラビン・ミラー判定法における1ループ。nが合成数で、1≦a≦n-1なるaがランダムに選ばれる時、75%以上の確率でfalseを返す。
言い換えると、nが合成数であることの検知に、25%以下の確率で失敗する。
内部で関数formula_p105を用いている。nが巨大でも高速な理由は、簡単に言ってしまえば指数を上手に利用している。
二分探索とかO(nlogn)ソートと似たような発想。

bool PrimeJudge_restricted(const ZZ& n, int loop_count = 20);
PrimeJudge_onecountをloop_count回だけ繰り返したもの。デフォルトでは20回。
(0.25)^20 ≒ 0 に基づいている。ただし、nが小さい時は上手くいかないあたりがrestricted。

bool PrimeJudge(const ZZ& n);
ラビン・ミラー判定法＋エラストテネスのふるい。nが素数ならtrueを返す。
nが50桁くらいなら約0.03秒で解ける。

以下、PrimeJudge_restrictedとPrimeJudgeの簡単な比較テスト。

素数が小さいと、restrictedはp=23とか成功することもあるけどわりと失敗する。一方、3桁くらいになるとかなりの確率で成功するようになる。実装では、念のため5000以下までの素数についてはリストを準備して二分探索かけている。

std::vector< std::pair > PrimeFactorization(ZZ n);
nを素因数分解したものをstd::vector< std::pair >で返す。

ZZ EulerPhaiFunction(const ZZ& n);
nを引数にとるオイラーのφ関数をZZで返す。φ関数における素因数分解の性質を利用して処理を効率化するために、内部で関数PrimeFactorizationを用いている。

std::vector periodic_vector(const int& D);
sqrt(D)を連分数展開したとき、小数点以下の桁の単位周期をstd::vectorで返す。
ただし、Dが平方数のときは空のstd::vectorを返す。

std::pair PellMinAns(const int& D);
ペル方程式x^2-D*y^2=1の最小解をstd::pairで返す。
ただし、sqrt(D)の周期１のときが多分おかしい。D=2でx=17, y=12などと出る。(正しくは、x=3, y=2)
また、Dが平方数のときはfirst,secondともに-1のstd::pairを返す。

以下、projectEulerのProblem66で、問題文の条件D≦1000をD≦10000に変えて動かしたときの出力結果。

これを総当たりで解こうとすると何年かかるんだろう。上手いこと考える人がいるんだなあと思った。

あと、75問達成でレベル３に上がった。ちょっと前までは100問解かないといけなかったけど、いいシステムになったなあ（こういう区切りがないとなかなかやめられないので・・・）。本業が難航してて、さらにそろそろ組み合わせ論とかに手出さないと解くのがきつくなってきたのでちょうどよかった。

Vim, Git
前のエントリでたしか、「一人で作業する分にはGitのブランチ必要ない」とか書いたけど全力で訂正します。もうブランチないと全く作業にならないくらい使いまくってます。あと、Vimもちょっとづつコマンド覚えていったら数ヶ月前に比べて使いやすくなってきてる。こういうコマンド系のソフトは慣れるまでが大変だけど凄く便利だなあ、と思う。

スマブラ
引退しましたm9( ^д^)

はじめての数論原著第3版―発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

作者: ジョセフ・H.シルヴァーマン,Joseph H. Silverman,鈴木治郎
出版社/メーカー: ピアソンエデュケーション
発売日: 2007/04
メディア: 単行本
購入: 9人クリック: 95回
この商品を含むブログ (17件) を見る

2011-08-31

夏休みやったことなど

vi/vim
多分夏休みで一番頑張っていない。
一応vimでコーディングやってるけど、使ってるコマンドはhjklと:q,:w,ZZ,ddくらいのもの。
今のままでも特に不便を感じないけど、使いこなしてる人から見ると色々時間の無駄をしてるはずなのでそのうちちゃんと勉強する（ほんとか？

Git
入門Gitを読みながら色々いじってたらそれなりに使えるようになった。
自分が上げるようなコードのネタは皆無なので今のところgit cloneが主力コマンド。
ブランチとか一応覚えたけど、一人で開発するぶんにはmasterだけで十分な気がする。

python
一番がんばった。
初めて触る言語なのでとりあえず本屋で入門書を・・・と思ったけど、公式ドキュメントの内容が充実し過ぎているばかりか日本語訳が存在したので必要なかった。
１週間ほど引きこもって入門自然言語読んだり実際にコーディングをやっていた。
以下、思い出せる限りで気になったところメモ。

・組み込み型が充実しまくってる
→string, list, set, dictって何もインポートせずに使えるのかー、と驚いた。C++だと色々インクルードしないといけないので。

・引数が参照渡し
→結構やっかいだった。copyモジュールをインポートすることで何とかなったけど、調べるのに時間がかかった。rubyも同じ仕様らしく最近は参照渡しが基本なのか。

・入門自然言語処理を読むだけでnltkや言語処理の基礎が身に付くわけではない
→実はpythonそのものやnltkの仕様のうちかなり限られた内容しか記載されてない。そもそも原著のタイトルには「入門」に相当する単語が無いので入門書と考えるのは不適切。
nltkの公式ドキュメントに書いてある知識が前提になっている。例えば、初めて読んだ時p19で出てくるFreqDistの使い方が全くわからずドツボにハマって大量の時間を使ってしまった。
公式ドキュメントを読めばわかるけど、実はFreqDistというのはprobabilityモジュールの中で定義されているクラスである。さらに、FreqDistは組み込み型であるdictを継承しているからkeys()メソッドを呼び出せるのだが、
こういう込み入った事情が本には全く記載されてない。他にもこういう例はあるのでこの本をnltkの入門書と思って読むべきではない。

スマブラ
フォックスを中心に練習していた。練習を積むことで、着キャンと小Jの成功率が上がってきた気がする。
フォックスの場合、とりあえず70-80%くらいまで適当に削ってからは失敗してもスキが少なく、決まれば即死の立A→上スマを積極的に狙っていく。ドリルキックから繋げても良い。

2011-08-04

夏休み？

PRML10章

PRML10章読み会でやったことまとめとか補足説明とか書いてみる。
まず、変分ベイズを3行でまとめると

　　　・(10.2)のKLをなるべく小さくしたい(q(Z) = p(Z|X)の場合が普通のEM)
　　　・q(Z)を平均場近似して、KLが最小になるようにそれぞれの因子q(Zj)を最適化(10.9)
　　　・考えるべき確率モデルについて、推定値をがんばって計算する

というノリの話（式番号はPRMLに依っている）。
この章のメインは多分、パラメータの事前分布を考慮した混合ガウス分布（テキストでは変分混合ガウス分布とか書いてるけど、不適切な気がする）で、ゴテゴテと色々な変数がついててなかなかヘビーである。事前分布つけて嬉しい点は、ベイズ的手法一般について言えることとしてサンプル数が少なくてもそれっぽい結果が出たりオンライン学習できる点か？
ビショップ先生レベルの人から見ればLDAの理論などはヌルゲーなのかもしれない。

ところで、今回は変分ベイズ使った混合ガウス分布の推定をRで実装してみました、というのが主な話題。
実装の流れと、ソースコードは以下のとおり。

実装：

ソースコード： https://github.com/risuoku/emvari

以下のコマンドを打ち込んだらとりあえず動く。2次元ガウス分布を使うためにはmvtnormパッケージが必要になる。

library(mvtnorm)
source("samplegene_2d.r") #サンプルを生成。xxオブジェクトに値が格納される。
source("emvari.r") #本体の読み込み
source("emvari_init.r") #初期化,リストParaにパラメータが格納される。
source("emvari_main.r") #メイン関数
source("emvari_graph.r") #視覚化

E_STEPのとことか自分で見直しても意味不明なので、R得意な人の指導を受けたいところ。
あと、図10.6のようにきれいに点が潰れる話は、理論的にも実験的にもいまだによくわからない。(10.69)を使って混合係数の期待値を見たけれど、1000回回しても「0と数値的に区別できない」というレベルの値は出なかった。

勉強会で話せなかったけど興味深い話題として、演習10.18がある。
これを考える前に、第10章でやった話の流れをまとめると
・隠れ変数とパラメータ（これらはモデルをわかりやすくするための区別で、確率・統計論的には同じ性質を持つ）の同時分布を(10.42)のように、分解する
・隠れ変数の最適分布が(10.49)で得られる
これがEステップに相当する部分で、ここから（超）パラメータの最適化に移る。ところで、(10.54)からの一連の流れが意味するところは、「最適なパラメータ分布（これはパラメトリック分布である点に注意する）がわかれば超パラメータがわかる」ことで、Mステップの使命であるところの「（超）パラメータの最適化」には一切ノータッチである。これは考えてみれば一見不自然で（実は、10.4で指数型分布族の場合には自明であることが示されるが省略）、パラメータを含んだ尤度関数を求めてガリガリ最適化の式を得るのが王道に思える。実際、9章でやったEMアルゴリズムはこっちの道を歩んでいる。
で、演習10.18は、(10.9)の副産物であるところのパラメータの最適分布など糞くらえで正々堂々最適化やろうという勇ましい試みで、「難問」マークがついてるのは計算が難しいからだと思う。暇で暇で暇で（＋50回繰り返し）仕方なくなった時チャレンジしてみたいと思っている。

他の話題

オレオレライブラリを地味に更新している。/と-以外の演算子は大体使えるはず。
プロジェクトオイラーで遊ぶための道具として作ったのにRSA暗号の課題で役にたった。人生どこで何が役に立つがわからない。

今後頑張ることリスト
・vi/vim
・Git
・python
・スマブラ

2011-06-25

oreore

オレオレクラスとかオレオレ関数とか

プロジェクトオイラーをC++でやってて悩まされるのが数値のデータサイズの問題。
longlongintでも18446744073709551615(十進数２０桁)が上限であるにも関わらずやつは平気で３０桁以上の計算などを出してくる。
縛りプレイに挑戦、ではないが練習がてらPE用のクラスやら関数やら自作して使ってるのでそろそろ使い方をまとめておく。（ちなみに、世の中的にはそういう機能のライブラリはもうある）

ソースコード　：　https://github.com/risuoku/oreore

/* Num_digit クラス */
メインで使ってるやつ。vectorを内部オブジェクトにもってるクラスで、N進数の各桁が配列の要素として一個ずつ格納されている。(Nはカスタマイズ可能)
数列の出力にメンバ関数out()を使う以外は、普通のintとvectorが一緒になったような感覚で使うことができる。演算子はとりあえず+, +=, *, *=, =のみオーバーロードされている。（必要性を感じたらそのうち増やすかも）
以下、サンプル。

//2^1000を考える
Num_digit a(1);
int ans(0);
	
for(int i = 0; i < 1000; i++) a *= 2;
for(int i = 0; i < a.size(); i++) ans += a[i];
	
a.out();
cout << a.size() << endl;
cout << ans << endl;

//出力
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 //オブジェクトの中身
302 //桁数
1366 //それぞれの桁の総和

/*std::vector prime_vector(long long int num_) */
num_以下の素数をvectorで返す関数。エラストテネスのふるいを普通に実装したもの。
以下サンプル。

//100以下の素数を求める
vector<long long int> v = prime_vector(100);
for(int i = 0; i < v.size(); i++) cout << v[i] << ' ';
cout << endl;

//出力
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

/* void prime_factorization(T num_, std::vector< std::pair >& vcont) */
num_を素因数分解して、結果をvector< pair >に格納する関数。pairメンバ変数のうち、firstに素因数、secondに対応する素因数の個数が格納される。
以下サンプル。

//26460 = (2^2)*(3^3)*5*(7^2) を素因数分解する。
vector< pair<int, int> > vcont;
prime_factorization(26460, vcont);
for(int i = 0; i < vcont.size(); i++) cout << vcont[i].first << ' ' << vcont[i].second << endl;

//出力
2 2
3 3
5 1
7 2

他にもあるけど、多分使い回してるのはこのへんの人たち。

思うことなど

ブログ立ち上げてから次の記事書くまでに１週間が経過してるようなノリだけど、もうちょっと続けてみようと思う。とりあえず早いとこBoost覚えないと。

2011-06-18

ブログってみた

何か勉強したり思いついたりすると更新されるブログ。見切り発車でいこう。