How Facebook Ships Code Posted: January 17, 2011 | Author: yeeguy | Filed under: business management, product management, social networks, startups |322 Comments I’m fascinated by the way Facebook operates. It’s a very unique environment, not easily replicated (nor would their system work for all companies, even if they tried). These are notes gathered from talking with many friends at Facebook
概要 rank/select は簡潔データ構造(Succinct Data Structures)の核になる関数です.ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank,k 番目の 0, 1 の位置(Index)を求めるのが select であり,ビット列の密度(1 の割合)によって,いろいろな実装があります. marisa-trie では,0, 1 の割合が極端に偏らないビット列を想定するとともに,32-bit 環境における性能の劣化を防ぐために,64-bit 整数を使わないようにしました.そのため,ほとんどの部分は以前に開発したライブラリからの流用ですが,新しく書き直した部分もあります.ちなみに,索引のサイズはビット列の長さ n bits に対して (1/4)n bits です. 基本 ビット列の実装 ビット列の格納には 32-bit 整数の配列を使っています
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く