こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。 例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置 といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。 例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[

形態素の頻度をカウントするというシンプルなタスクで std::tr1::unordered_map の性能について実験してみました．std::string より const char * の方がメモリを節約できるというような軽い内容です． 実験概要 実験環境は以下のとおりです． 実験環境 CPU：Core 2 Duo U9600 1.60GHz コンパイラ：gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) 入力として使用したのは，ウェブコーパスから抽出した形態素を改行区切りで保存したファイルです． 入力 サイズ：815,793,701 bytes 形態素数：133,940,786 異なり数：516,612 形態素の入力については，std::ios::sync_with_stdio(false) を呼び出した後で std::getline() を使うようにし

k-means を実装していて，疎ベクトルと密ベクトルのトレードオフ（距離計算の速度差）が気になったので軽く実験してみた．具体的に知りたかったのは，どれぐらい疎なら疎ベクトルを使った方が距離計算が速くなるか，という問に対する答え．空間使用率の改善については sparse vector における index と value の型のサイズ比でほぼ自明に分かるが，速度に関してはコンパイラの最適化の加減もあるので良く分からない．以下がテストコード（ややずぼらな実装）． [追記] 折角なので，Eigen 3.0-beta2 とも比べてみた． #include <sys/time.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <tr1/random> #include <eig

新米と秋刀魚のわた焼き お刺身用の秋刀魚を買いました。1尾250円です 3枚におろして、秋刀魚のわたに酒、味醂、醤油で調味して1時間ほど漬け込み、グリルで焼きました 秋刀魚のわた焼き わたの、苦味が程よくマイルドに調味され、クセになる味わいです 艶やかな新米と一緒に 自家製お漬物 土…

大規模データで単語の数を数える - ny23の日記 でみたように，単純に高頻度の item が欲しい場合には，小規模データで単語の数を数えてみた (1) - ny23の日記 で使った sketch-based なアルゴリズムよりは，counter-based なアルゴリズムの方が（キーを陽に保存するので）使い勝手が良い．というわけで，space saving アルゴリズムを実装してみた．カウンタのデータ構造には，原著論文 Space saving (Efficient computation of frequent and top-k elements in data streams, ICDT 2005) に書いてある stream summary をほぼ定義通り素直に実装して利用． // GNU GPL version 2 copyright@ny23 #include <cstdio

大規模データで単語の数を数える - ny23の日記 で書いた Count-Min Sketch で，誤差を減らすヒューリスティクス (conservative update) New directions in traffic measurement and accounting (SIGCOMM Comput. Commun. Rev., 32(4), 2002) を実装して，動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 の小規模データ（1.5GiB の Wikipedia 本文）の単語カウントでその効果を見てみた．考えるところはハッシュ関数に何を使うかぐらいで（キーを陽に保持しない限りは）実装はとても簡単． // GNU GPL version 2 copyright@ny23 #include <cstdio> #include <cstdl

C++の最近の必読書を3冊挙げるなら"Pattern-Oriented Software Architecture Vol.2","Java Concurrency in Practice","The Art of Multiprocessor Programming"ですね（ぉ

最近は新しいアルゴリズムが提案されると，素早く実装する人が沢山いる．また，色々な実装を比較して情報を公開している人もたくさんいる．いずれにせよ，そこに多分の労力が割かれていることは間違いない．利用者側の立場からすると，「取り敢えず公開されていたから」という理由で，非効率的な実装を運悪く選択し，ボトルネックになっていると気がつかないで使い続けたりするのはなるべく避けたい．実装する側からすると，高級言語が隠蔽するライブラリの落とし穴にどういうものがあるのかは，把握しておきたい． さて，なるべく労力を使わず，（非）効率的な実装を自動的に判別することは可能だろうか．例えばプログラム言語を限定して (C++ とか)，ある特定の問題を解く実装の中から，（例えば機械学習などを用いて）時間／空間効率の良い（悪い）実装を見つけることはできるだろうか．あるいは逆に，時間／空間効率の良い（悪い）実装を示唆する素

大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは

http://longgate.co.jp/products.html 弊社、株式会社ロングゲートで、プログラミング雑誌を作るというプロジェクトが進行しています。 本書創刊の目的は、プログラミングの入門記事が巷に溢れる今、プログラマのさらなる成長のため情報発信を行い、業界全体の技術力を向上させることです。 雑誌といっても、記事の質を保つために不定期刊行としていることから、実際には雑誌ライクな書籍となります。 書籍名は「プログラミングの魔導書〜Programmers' Grimoire〜」です。 創刊号となる今回のテーマは、サブタイトルにも含まれている「C++」です。全ての記事がプログラミング言語C++に関するものとなっています。 Vol.1のテーマをC++としたのは奇をてらったものではありません。 C++は習得の難しい言語と言われておりますが、近年はBoost C++ Librariesに

以前，liblzma のヘッダを眺めているときに気づいたのですが，gcc 3.4 以降では，warn_unused_result という属性を関数に与えておくと，返り値を確認していない場合に警告を出してくれるようです． わざわざエラーコードを返すような設計にしても，手抜きで確認しなかったり，途中で忘れてしまったりということはよくありますから，重要なところに付けておくことで，バグの発生を防ぐことができるかもしれません．片端から付けておくという荒技も，一つの選択肢としてはあります．ただし，ちょっとしたコードを書いて試したいというときには邪魔です． 属性の指定は，関数の宣言に対しておこないます．関数の定義に対して属性を指定しようとすると gcc に ``error: attributes are not allowed on a function-definition'' と怒られてしまい，コン