YAPC::Asia 2日目 「はてなブックマークのシステムについて」 - naoyaのはてなダイアリー2日目の発表も終えました。資料を公開します。 はてなブックマークのシステムについてView more presentations from Naoya Ito. 今日も少し駆け足気味でした。YACP::Asia 2009、今年も楽しかったです。Hackathon 出ずに京都に戻らなければならなかったのが悔やまれます。 発表の様子 撮影: id:hirose31
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
OGC2009 での発表資料 - naoyaのはてなダイアリー
昨日開催されました OGC2009 にて、はてなブックマークのコミュニティについて発表させていただきました。 INTERNET Watch さんなどでも取り上げていただいてます。 http://internet.watch.impress.co.jp/cda/event/2009/02/05/22342.html http://game.watch.impress.co.jp/docs/20090206/ogc_net.htm 以下に発表資料を公開します。(ウェブでの公開用に少々編集を行いました) OGC2009 はてなブックマークについてView more presentations from Naoya Ito. (tags: hatena) 後半時間が足りずに飛ばしてしまったので、記事では触れられていませんが、まだまだ課題が山積みです。今後も継続的に改善していきたいと思っています。
KOF 2008 の発表資料 - naoyaのはてなダイアリー
KOF 2008 での発表資料「はてな流大規模データ処理」を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/081108huge_data.ppt 一部参考文献からの引用 (Introduction to Information Retrieval から Vector space model の図、たつをの ChangeLog から転置インデックスの図) があります。この場を借りて感謝。 環境によってはおそらくフォントの表示がいまいちだと思いますが、ご了承ください。 追記 SlideShare にアップロードしました。 081108huge_data.pptView SlideShare presentation or Upload your own. (tags: linux mysql) 追記: メモリはディスクの 150 倍について
サーバ/インフラ Tech Meeting の資料など - naoyaのはてなダイアリー
金曜日は サーバー/インフラを支える技術出版記念イベント サーバ/インフラ Tech Meeting の日でした。自分は「Linuxカーネルの読み方」と題して、自分なりにまとめたカーネルのソースコードを読むコツについてお話させていただきました。 発表資料を以下にアップロードしました。 http://bloghackers.net/~naoya/ppt/08080924svr_techmeeting.ppt (ppt) http://www.slideshare.net/naoya1977/how-to-read-linux-kernel/ (Slide Share) 同じく著者のひろせさんからはなぜこの本を書いたか、どういう本なのかという概論 (One more thing もありました)。Klab の安井さんは DSAS について、特に「ダイナミック」をキーワードにした幾つかのインフラ構
Hadoop Streaming - naoyaのはてなダイアリー
id:naoya:20080511:1210506301 のエントリのコメント欄で kzk さんに教えていただいた Hadoop Streaming を試しています。 Hadoop はオープンソースの MapReduce + 分散ファイルシステムです。Java で作られています。Yahoo! Inc のバックエンドや、Facebook、Amazon.com などでも利用されているとのことです。詳しくは http://codezine.jp/a/article/aid/2448.aspx (kzk さんによる連載記事)を参照してください。 Hadoop Streaming 記事にもあります通り、Hadoop 拡張の Hadoop Streaming を使うと標準入出力を介するプログラムを記述するだけで、Hadoop による MapReduce を利用することができます。つまり、Java 以外
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
LWP::UserAgent + POE::Filter::Line で行ベース処理 - naoyaのはてなダイアリー
#!/usr/bin/env perl use strict; use warnings; use LWP::UserAgent; use POE::Filter::Line; my $filter = POE::Filter::Line->new; my $ua = LWP::UserAgent->new; ## POE::Filter::Line で $chunk を行入力に変換 $ua->get( 'http://d.hatena.ne.jp/naoya/', ':content_cb' => sub { my $chunk = shift; my $lines = $filter->get([ $chunk ]); for (@$lines) { print "got: $_\n"; } } ); POE::Filter は単独で使うことができます。LWP のコールバックと組み合わ
Linux のプロセスが Copy on Write で共有しているメモリのサイズを調べる
Linux は fork で子プロセスを作成した場合、親の仮想メモリ空間の内容を子へコピーする必要があります。しかしまともに全空間をコピーしていたのでは fork のコストが高くなってしまいますし、子が親と同じようなプロセスとして動作し続ける場合は、内容の重複したページが多数できてしまい、効率がよくありません。 そこで、Linux の仮想メモリは、メモリ空間を舐めてコピーするのではなく、はじめは親子でメモリ領域を共有しておいて、書き込みがあった時点で、その書き込みのあったページだけを親子で個別に持つという仕組みでこの問題を回避します。Copy-On-Write (CoW) と呼ばれる戦略です。共有メモリページは、親子それぞれの仮想メモリ空間を同一の物理メモリにマッピングすることで実現されます。より詳しくは コピーオンライト - Wikipedia などを参照してください。 この CoW に
Perl の autobox で遊ぶ - 2008-01-19 - naoyaのはてなダイアリー
autobox を使ったコードをここ最近よく見た ので、ややいまさらですが自分もすこし遊んでみました。autobox は Perl の組み込みのデータ (bless されていないスカラー、リスト、ハッシュほか) をファーストクラスオブジェクトとして扱うための機構を提供するモジュール(レキシカルプラグマ)です。 #!/usr/local/bin/perl use strict; use warnings; use FindBin::libs; use autobox; use autobox::Core; use autobox::Encode; use autobox::Hatena::Feed; use autobox::Accessor; shift->b(qw/perl autobox/)->items->foreach(sub { $_[0]->title->encode('utf
Perl で 8ビット CPU を作る - naoyaのはてなダイアリー
CPU を作る、と言ってもハードではなくソフト、仮想機械です。 2001 年から UNIX USER で連載されていた西田亙さんの「gccプログラミング工房」。いまさらながら、バックナンバーを取り寄せて初回から順番に読んでいます。とてもためになる連載です。 この連載中で第10回から数回に分けて開発されていた octopus という 8 ビット CPU の仮想機械があります。オリジナルは C 言語で書かれていたのですが、その設計を見て、これは他の言語でも作れるのではないか、と思い Perl に移植してみたところなんとか動作させることができました。以下の URL にコードを公開します。(西田さんに確認を取ったところ、オリジナルのソースは Public Domain とのことでした。オリジナルは http://www.skyfree.org/jpn/unixuser/ からダウンロード可能です。
x86 Linux のメモリモデル、プロセス空間切り替え、カーネルスタック - naoyaのはてなダイアリー
ひとつ前のエントリ id:naoya:20070924:1190653790 では Linux のコンテキストスイッチにおける、主にハードウェアコンテキストの退避/復帰の処理を追ってみました。その中で カーネルスタック (switch_to() 内で pushl %ebp とかして値が積まれるスタック)とはそのときの実行コンテキストに紐づくカーネルプロセススタックという理解でよいか。 という疑問がもやもや湧いて出てきました。ここ数日 はじめて読む486―32ビットコンピュータをやさしく語る を読んでいたのですが、その中にこの疑問への答えへの入り口が載っていまして、そこを糸口に調べてみました。で、結果としては 答え: 良い でした。 x86 は特権レベルの移行と連動してスタックポインタを切り替える仕組みを持っています。Linux の場合モードはカーネルモード(特権レベル0) とユーザーモード
inetd の仕組みを見てみる - naoyaのはてなダイアリー
inetd や xinetd (以下 inetd) はインターネットサービスをデーモン化するのに共通している処理を担い、ほとんどの時間をアイドル状態で過ごすその手のサービスに必要なリソースを節約する役割を果たします。 inetd のひとつ面白いところは、inetd でサービス化したいプログラムの標準入力/標準出力がクライアントソケットの入出力に接続されるところです。例えば daytime 相当のサービスを自分で作ろうと思った場合 #!/usr/local/bin/perl # daytime.pl use strict; use warnings; use DateTime; use IO::Handle; STDOUT->autoflush(1); STDOUT->printf( "%s\n", DateTime->now(time_zone => 'Asia/Tokyo') ); と標
naoyaのはてなダイアリー - Linuxのページキャッシュ
世間では PHP が、Perl が、と盛り上がっているようですが空気を読まずまたカーネルの話です。今回はページキャッシュについて。 /dev/shm に参照系ＤＢを持っていくと I/O 負荷が激減した件（当たり前だけど） - drk7jp で、ディスク上にあったファイルを /dev/shm (tmpfs) に移したら I/O 待ちがなくなって負荷がさがった、ということなんですがおそらくこれは tmpfs に置く必要はないかなと思います。Linux (に限らず他の OS もそうですが) にはディスクの内容を一度読んだらそれはカーネルがキャッシュして、二度目以降はメモリから読む機構 = ページキャッシュがあります。tmpfs にデータを載せることができた、ということは物理メモリの容量に収まるだけのデータサイズかと思うので、放っておけば該当のファイルの内容すべてがメモリ上にキャッシュされて io
Web::Scraper - naoyaのはてなダイアリー
Today I've been thinking about what to talk in YAPC::EU (and OSCON if they're short of Perl talks, I'm not sure), and came up with a few hours of hacking with web-content scraping module using Domain Specific Languages. 使ってみたよ! #!/usr/local/bin/perl use strict; use warnings; use FindBin::libs; use URI; use Web::Scraper; use Encode; use List::MoreUtils qw/uniq/; my $links = scraper { process 'a.key
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Introduction to DBIx::MoCo - naoyaのはてなダイアリー