Wavelet Tree - naoyaのはてなダイアリー
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
naoyaのはてなダイアリー - MySQL の負荷分散に LVS + keepalived を使う
あとで書く、と言った手前なので書くとします。 DSASの中の人がすごい勢いで LVS の話を書いてくれてます。この辺。LVS を使うと Linux と箱でロードバランサが作れちゃいます。普通に買ったら数百万とかしちゃうやつ。 DSAS の中のひとに感謝しつつ、いい機会なのでやってみよう! と思っていろいろ試して昨日あたりからはてなの中でも LVS + keepalived で動かしはじめてます。いまのところ問題なし。 そのロードバランサをどこに使ってるかですが、普通ロードバランサというとインターネットからの入り口のところに置いてウェブサーバーの負荷分散に使うイメージがあります。が、今回ははてなでは MySQL のスレーブの手前に置くという役割でとりあえず使いはじめました。 +-----------+ +-----------+ | mod_perl | | mod_perl | +----
naoyaのはてなダイアリー - Inside Hatena Bookmark's Backend の資料
以下に置いておきました。遅くなってすいません。 http://bloghackers.net/~naoya/pdf/050404inside_hatena_bookmark.pdf 会場で前置きしたように、はてなブックマークは、はてなで一番大きなシステムであるはてなダイアリーあるいは同じ YAPC で発表のあった mixi に比べると、まだそこまで大きな規模ではありません。月間の PV はだいたい 4,000 万 PV 〜 というところです。 ただ、日本でのトラフィックが上から 5 番目みたいな怪物サイトよりも、月間の PV が 1,000 万クラスのサービスの情報の方が、より現実的で役に立つのではないかと思い、はてなブックマークの裏側に絞って話しをしてみました。 ...という前提で見ていただけると嬉しいです。 はてなブックマークのデータのサイズもかなり大きくなってきたので、ぼちぼちパーテ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
