スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Github Pagesに移行しました。

ブログをGithub Pagesに移行しました。
https://zaburo-ch.github.io/
スポンサーサイト

【C++】mainなどの関数の中では大きな配列を確保できない

これがSegmentation faultになるのに対して

これは正しく実行される。

グローバル変数はヒープに取られるのに対して、
ローカル変数はスタックに積まれていく。
スタックのサイズは制限されていることが多く、
(bashならulimit -aで確認できる。8192KBだった)
bool型は1byteなので配列のサイズは10000001/1024≒9765KBとなり
スタックのサイズ制限を超えてしまうので、
メモリリミットより小さいがローカル変数として確保できない。

[参考]
http://homepage2.nifty.com/well/Variable.html

【C++】vectorは==で比較できる

知らなかったのでメモ

C++ ベクタ
http://www.cppll.jp/cppreference/cppvector_details.html



Javaでのオブジェクトの比較みたいに
アドレスが比較されちゃうんだと勘違いしてた。

Wikipediaの記事でPageRankを計算してみた。

PageRankの記事の続きです。

【Python】PageRankアルゴリズム
http://zaburoapp.blog.fc2.com/blog-entry-38.html


PageRank実装だけして終わるのももったいないので
Wikipediaのページ内でPageRank計算してみました。

コードはこちら
zaburo-ch/wikipedia_analysis
https://github.com/zaburo-ch/wikipedia_analysis

前に作ったwikipedia.pyのコードとまとめてレポジトリにしました。

pagerank_wiki.pyを実行すると次のような動作をします。
http://dumps.wikimedia.orgより1日分のデータを取得
・国コードがjaのもののうち閲覧数上位10000ページを取り出す
・各ページの記事内のリンクをエッジとした有向グラフつくる
・有向グラフ内でPageRankを計算し大きい順に出力する

やってることはかなりwikipedia.pyに近いですが、
見返してみるとあまりにもなコードだったのでかなり書き換えました。
他にもリンク抽出にHTMLParser使ってみたりいろいろ変えてます。

前のやつと違って計算の部分にそれほど時間がかからないので
スペック次第ですが少なくとも寝てる間くらいには終わると思います。
リンク解析もこっちのほうがかなり早いです。

さて、肝心の実行結果はこんな感じです。
pagerankwikiresult.png
wikipedia_analysis/pagerank_wiki_data/result.txt

「特別:カテゴリ」がぶっちぎりで大きいですね。
確認してみたところほぼ全てのページの一番下に
「特別:カテゴリ」へのリンクがあったのでたぶんそのせいです。
「Wikipedia:出典を明記する」とかもこの類いかな。

「日本」や年がおおいのは人とか何かの作品の記事の
テンプレート化している右の枠内で登場することが多いためだと思います。

テレビ局が上位に多いのはテレビ番組からほぼ確実にリンクされているのと
閲覧数上位10000ページで限定しているため
そのなかでテレビ番組が多かったためではないかと考えています。

上位はほとんどが誰でも知っているような一般的な言葉なんですが、
101位のインターネット・ムービー・データベースってやつ、
全然何のことかわからないです。
「集英社」とか「台湾」より上なので、
かなり多くページがここにリンクしてるはずなんですが、
これどんなページからリンクされてるんでしょう?

全体的にPageRankはWikipediaのページの重要性判断としては
あまり向いていないように思いました。
WikipediaにはPageRankの基本的な考え方が合ってないですしね。
ほかのWebサイトでも試してみればもっと面白い結果が得られるかもしれません。
機会があればやってみたいと思います。

【Python】PageRankアルゴリズム

PageRankというアルゴリズム、
以前からなんとなくは知ってはいたのですが、
ランダムサーファーモデルで計算する方法を聞いて、
めちゃくちゃ賢いなこれーって思ったので実際にやってみました。

ひとまずPageRankについて調べたことを纏めます。

PageRankは基本的に次の2つの考え方でページの重要度を推定します。
・多くのページからリンクされているページの質は高い
・質の高いページからリンクされているページの質は高い

これを数学的に考えるのにランダムサーファーモデルを利用します。
ランダムサーファーモデルでは
ページのリンク関係を有向グラフとして考え、
人(サーファー)にこの有向グラフをランダムに辿らせたとき、
人が居る確率が高いページを重要とします。

まず、ページの総数をNとし、N次正方行列M
M[i][j] = ページjにいるサーファーがページiに移動する確率
と定義します。
例えばページ0にページ1とページ5へのリンクしかないとすると、
サーファーはランダムに移動するので
M[i][0]は i=1or5 のとき1/2 となりそれ以外のiでは0となります。

また、ベクトルP(t)を時刻tに各ページに人がいる確率とすると
P(0)は全ての要素が 1/N のベクトルとなり
P(t+1)はMP(t)の積を取ることで計算できます。

有向グラフが強連結のとき、この遷移を無限に繰り返すことで
Pはtに依らない一定の値に収束します。よってこのP
M P = P
の解を要素の和が1になるよう正規化してあげることにより求められます。

このPの大きさが各ページの重要度となります。

----
行列計算において Ax = λx を解く、というのは固有値問題と言って
色々な方法が考えられているらしいのですが、ここについては
行列計算における高速アルゴリズム
http://www.cms-initiative.jp/ja/events/0627yamamoto.pdf

こちらのページが詳しいです。
Pythonではscipy.sparse.linalg.eigsを使うと
Implicitly Restarted Arnoldi で計算してくれます。
ただ、M P = P を解くだけのためにこれらを使うのが速いのかは
勉強不足で僕もよくわかっていません。
----

実際のウェブページでは、ページ間の関係を有効グラフにしても
必ずしも上で述べたような強連結になるわけではありません。
そのため「一定の確率でサーファーはリンクを辿らずにランダムに移動する」
という考えを新たに導入します。その時はMにあたるものを
全ての要素が 1/N である N次正方行列Uと普通にリンクを辿る確率αを用いて
M + (1-α)U) として計算することによってPが求められます。


次の図のようなリンク関係にあるページのPageRankを
Pythonを利用して実際に計算してみます。
正しく計算できれば図の通りの値が得られるはずです。

Linkstruct2.gif

The original uploader was Gnix at English Wikipedia[GFDL or CC-BY-SA-3.0]


コードはこちら
zaburo-ch/wikipedia_analysis/master/pagerank.py

get_pagerankではScipyを用いて固有ベクトルを計算しています。
get_pagerank_simpleではもっと単純に
P(0)に何度もMをかけていき、
かける前との差が十分小さくなるまで繰り返しています。

実行結果はこんな感じです。
pagerankresult.png

図の値とかなり一致していますね!
2つの方法どちらもほぼ同じ値になっているので
get_pagerank_simpleの方法でも十分実用に足りそうです。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。