高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
「はてな流大規模データ処理」を見てきた - もぎゃろぐ
KOF2008：関西オープンソース2008というイベントに来ています。 はてなの伊藤さんの講演があったので、講演メモを公開。 ＃ボクがメモした内容であって、100%言ったとおりに書いてあるわけじゃないので、参考としてご覧ください。 (続き) アジェンダ 大規模なデータ OSのキャッシュ MySQLの運用 大規模データアプリケーションの開発 データの例 はてなブックマークのデータ量：五千万件くらいのデータ量 このデータに対して何百万人がアクセスしてくる状況でどういう作りにするか レコード数 1073万エントリー 3134万エントリー 4143万タグ データサイズ エントリー2.5GB 何の工夫もなく普通にアクセスすると...200秒待っても結果が帰ってこない 大規模データの難しいところ 開発サーバで開発者が作っている時は快適に動いていても、多数の人間がアク
Perl スクリプトで遅い場所を特定する方法 - Devel::Profiler / Devel::NYTProf
今仕事で書いてる Sledge アプリがあるのですが、先日負荷テストを行った結果びっくりすることに現行アプリの１０倍遅いことが判明してしまいました・・・orz Sledge フレームワーク自身が重くないことは今までの経験でわかってるのですが、どうにもソースを見直しているだけでは原因が特定できない・・・そんな活躍するのがプロファイラです。プロファイラの御陰で遅いヶ所を特定することができ、無事に想定するパフォーマンスを得ることができました。この内容に関してはまた別エントリにて。 さて、プロファイラを使うとプログラム実行時の各種情報を収集し、性能解析を行うことが可能です。プロファイラについてもう少し詳しくしるには 性能解析 - Wikipedia あたりを読むと良いでしょう。 プロファイラ（英: Profiler）は性能解析ツールであり、プログラム実行時の各種情報を収集する。特に、関数呼び出しの
「科学」の勝利：オバマ氏を支えた、科学技術界からの強力な支持 | WIRED VISION
「科学」の勝利：オバマ氏を支えた、科学技術界からの強力な支持 2008年11月 7日 社会国際情勢 コメント： トラックバック (0) 「カーボン・ナノチューブで作った、たくさんのオバマ氏」という記事の中で、「ナノバマ」を作った研究者のサイトについて、「科学のために投票しよう」とだけ書かれている、という紹介があります。 これは一見すると中立的なキャッチコピーのように見えますが、今までの選挙戦を見ていると、このキャッチが「オバマに投票しよう」とほとんど同じ意味であるということがわかってきます。 「科学」は、今回の米国大統領選でひとつの焦点になったテーマでした。ワイアードの科学ブログでは、ときどき大統領選関連記事が掲載されており、大統領候補が科学的な問題にどう対応していくかが読者の関心を呼んでいたことが伺えます。(記事のまとめはこちら) 例えば、科学ブログの筆者たちも支持してきた全米規模の運動
NHKスペシャル - jkondoの日記
NHKスペシャル「デジタルネイティブ」という番組が今晩放送されますが、ここにはてなが登場します。 http://www.nhk.or.jp/digitalnative/ 物心ついた時からデジタル製品に囲まれて育った「デジタルネイティブ」な若い世代の人たちが、新しい潮流を起こしている、というような内容だと聞いています。今晩の放映が楽しみです。 NHKスペシャルは昔から好きな番組ですが、たまに「よく考えると自分はテレビのドキュメンタリー番組から非常に大きな影響を受けているな」と実感することがあります。たとえば雑誌の取材を受ける際に、「なぜ起業しようと思ったんですか？」という質問をよく聞かれます。そういう時は起業に至る経緯などを話すのですが、その中に「ベンチャーへの憧れ」という要素があります。そしてその憧れの対象はアメリカのベンチャー企業だったりするのですが、そもそもどこで「アメリカのベンチャー
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
技術者としての「日本語が亡びるとき」 - stanaka's blog
日本語が亡びるとき を読みました。普段は、あまり書評らしいものは書かないのですが、いろいろ確信が得られたので、熱が逃げない内に記します。 日本語が亡びるとき―英語の世紀の中で 作者: 水村美苗出版社/メーカー: 筑摩書房発売日: 2008/11/05メディア: 単行本購入: 169人 クリック: 12,641回この商品を含むブログ (456件) を見る この本で論じられている「日本語はこのままだと亡びる可能性がある」ということは、僕にとっては、若干背を向けたかった現実だったりします。僕は、英語が完璧にはほど遠いエンジニアの常として、なんだかんだ言って日本語をベースとした活動としています。「日本語が亡びる」ということは、それらの活動が将来的に無になってしまうことと、ほぼ同義です。 技術、特に情報科学・技術を専門としている身としては、英語が普遍語である、というのは、この本に教えられるまでもなく
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
メディア掲載実績 - 株式会社はてな