ドットインストール代表のライフハックブログ
![IDEA * IDEA](https://cdn-ak-scissors.b.st-hatena.com/image/square/ce98a7f98c635f33cea46e5941325dc95c2f2f54/height=288;version=1;width=512/http%3A%2F%2Fwww.ideaxidea.com%2Fwp-content%2Fuploads%2F2009%2F04%2Fusa1.gif)
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet(TC)のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木(multiway balanced treeの略であり、二分木(binary tree)とは違います)の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード(B木)の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
Google が公開しているソフトウェアの解説シリーズ(→その1 , その2)の続きです。今回は google-glog を使ってスタックトレースを表示する方法についてご紹介します。 C++ でプログラムを書いているとよく遭遇するのがセグメンテーション違反というエラーです。不正なアドレスへのアクセスなどによりセグメンテーション違反が起きると、通常、 UNIX 系の OS では SIGSEGV というシグナルによってプログラムが終了するとともに、 core というファイルが作られます。 core ファイルにはデバッガから参照できるいろいろな情報が残っていますが、多くの場合に役に立つのは、スタックトレースという情報です。スタックトレースを見れば、プログラムがどこでクラッシュしたのか、どのような関数を経由してそこにたどり着いたのかがわかります。プログラムがクラッシュした箇所を特定できれば、単純な
This domain may be for sale!
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
最近移動続きであまり研究に時間は割けないのだが、本は読めるということで本を2冊、サーベイ的な記事を3本(うち2本はチュートリアルスライドつき)を紹介する。まず Semisupervised Learning for Computational Linguistics (Chapman & Hall/CRC Computer Science & Data Analysis) 作者: Steven Abney出版社/メーカー: Chapman and Hall/CRC発売日: 2007/09/17メディア: ハードカバーこの商品を含むブログ (4件) を見る を読む。この本の著者の Steven Abney はブートストラッピングの理論的解析をした人で、 Steven Abney. Bootstrapping. 40th Annual Meeting of the Association fo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く