オンライン学習でキャッシュを実装してみた - ny23の日記
手持ちのオンライン学習器で訓練データをメモリに載せず処理するモードがオンメモリで処理するモードに比べて5倍ぐらい遅いのが気になったので，Vowpal Wabbit みたく訓練データをキャッシュしてみることにした．まず準備として，Simple-9 と Variable byte code (vByte)，さらに binary でそのまま保存する場合 (Raw) に，訓練データの符号化（入出力込み）／復号化 (入力のみ込み) の性能を比較してみた．普段使っている訓練データをx100倍したもの (約3000万訓練例, 819,841,000 integers) を入力．Disk Cache の扱いがいい加減だったので，再実験した．さらに，Group Varint Encoding の結果も追加した． 素性番号を適当につけた場合 (5952MiB) | Simple-9 | vByte |Grou
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
プログラミングは人生だ――まつもとゆきひろ ― ＠IT
私がプログラミングを始めたのは中学校３年生のときでした。父が買ってきたシャープのポケットコンピュータ（PC-1210）でBASICを使うようになったのです。わずか400ステップしか入力できない小さなコンピュータでしたが、それでも自分の命令したとおりに動作するポケコンを見ていると、自分にはなんでもできるようなそんな「万能感」を感じさせてくれました。 それから四半世紀以上たちましたが、私がプログラミングから感じる「わくわく」は少しも減ることはありません。むしろ、どんどん増えているように感じます。長いプログラム経験を踏まえて、いま、感じるのは、 プログラミングは人生だ ということです。プログラムには人生のあらゆる側面が詰め込まれています。文字どおり、人生そのものといってもいい過ぎではないでしょう。……うーん、やっぱり、いい過ぎかな。 プログラミングはスポーツだ 皆さんの多くは若いときにスポーツに
各種マップ実装の性能比較 - mixi engineer blog
今回は小ネタのmikioです。key/valueのレコードを高速に格納・参照・削除する仕組みが連想配列とかマップとか呼ばれて親しまれていますが、Tokyo Cabinetのオンメモリマップの性能をC++の各種実装と比較してみました。 以下の実装を対象として、100万レコードの格納と検索にかかる時間を計測します。キーと値は各8バイトの文字列とします。 Tokyo Cabientのオンメモリマップ（TCMAP） STL（C++の標準テンプレートライブラリ）のmapとmulti mapとset GNU拡張テンプレートのハッシュマップ Googleのdense hashおよびsparse hash テストコードはこちらに挙げておきます。具体的な操作としては、マップオブジェクトを生成し、バケット配列の要素数をレコード数と同じにチューニングし、ループを回してレコード群を格納します。なお、STLのマップ
Tokyo Cabinet: a modern implementation of DBM
BTW, do you know Tkrzw? Actually, it is more powerful and convenient library than Tokyo Cabinet. At this distance of time, Tkrzw surpasses Tokyo Cabinet in every aspects. I strongly recommend you to use Tkrzw. Overview Tokyo Cabinet is a library of routines for managing a database. The database is a simple data file containing records, each is a pair of a key and a value. Every key and value is se
メモ化 - Wikipedia
メモ化（英: memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。 メモ化という用語は1968年にドナルド・ミッキーがラテン語の memorandum（覚えておく）から作った造語である[1]。memorization（記憶、暗記）は同根語であってよく似ているが、メモ化という言葉は情報工学では特別な意味を持つ。 メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ