はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは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++の利用
bkブログ プログラミングやバッドノウハウについてのブログ 2004-2011年に書いていたブログのアーカイブです。 机の上のもののワイヤレス化 - Microsoft Arc Keyboard の導入 iPodは何を変えたのか? 人が問題にぶち当たったときには、どうするか? ソフトウエアの肥大化について、の続き ソフトウェアの肥大化について ある程度の年齢を迎えたプログラマが抱える悩み Unicode の雪だるま 設定ファイルの整理 - Emacs 編 設定ファイルの整理 - zsh 編 パターン、Wiki、XP ～時を超えた創造の原則 マッキントッシュ物語 - 僕らを変えたコンピュータ GNU diff の地味だけど便利な機能 C++ の string と vector の reserve() の挙動 暗号化 - プライバシーを救った反乱者たち Best Software Writin
マイクロソフト（株）は15日、統合開発環境“Visual Studio”シリーズの最新版となる「Visual Studio 2005」日本語正式版を“MSDN”会員向けにダウンロードでの提供を開始し、同時に、同製品の機能限定版である「Visual Studio 2005 Express Edition」日本語正式版の、一般向けの無償公開を開始した。“Express Edition”は“MSDN”会員に限らず、誰でも同社ホームページからダウンロードして利用でき、使用期限はない。なお、“Express Edition”の一般向けの無償公開は1年間の期間限定となっている。 「Visual Studio 2005」は、「.NET Framework 2.0」をサポートしたWindowsアプリケーションの統合開発環境。今回、日本語の無償版が公開されたのは、プログラミング初心者向けの機能を数多く搭載し
図1 インクリメンタル検索を実現<br>作成したサーバーCGIプログラムを使ってインクリメンタル検索する様子。計画通りに稼働しているのが分かります。 前回は，インクリメンタル検索を実現するAjaxアプリケーションのクライアント・サイドの実装を紹介しました。今回は，サーバーとして稼働するCGIプログラムを作成します。このCGIプログラムは，クライアントから送られてきたクエリーに基づいてテキストを検索し，その結果を返送します。Ajaxアプリケーションは通常のWebアプリケーションに比べて，サーバー・アクセスが増加しがちです。このためサーバーをいかに効率よく実装できるかが，サービスを快適に提供できるかどうかを左右します。サーバー負荷を下げる手法についても考えてみましょう。 テキスト検索にsaryを使用 みなさん，テキスト検索といえばどんな方法を思いつくでしょうか。単純なところではgrepコマンド
Binary 2.0カンファレンス 2005 発表資料とレポート Binary 2.0 カンファレンス 2005 は大盛況のうちに無事終了いたしました。開催にご協力いただいた皆様、スピーカーの皆様、参加していただいた皆様、大変ありがとうございました。 当日の発表資料とレポートをこのエントリでまとめています。参加報告などはこのエントリへのトラックバックで受け付けています。よろしくお願いいたします。 Binary 2.0 時代の到来 - 高林哲プログラムはなぜ Ｍona OS で動くか？fork?何それ？ - ひげぽんDynamic Programming Language C -- 私は誰？ - 浜地慎一郎g++と例外キャッチボール - 中村孝史G-Inspector -- GTK+ ランタイムインスペクション - 青笹茂実行時自己書き換え佳境 - 首藤一幸ハードコアバイナリアンへの道 -
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く