高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
巡回セールスマン問題で、Qtの使い勝手を体感してみた
QtはC++のクロスプラットフォームなアプリケーション・フレームワークで、C++が抱える互換性の問題を大きく解消しつつ、スタイリッシュなGUIを扱いやすくするツールキットだ。2009年3月に無料だが業務開発に使いやすいLGPL版がリリースされており、Google Trendsでは2009年の秋からMacintosh OS XのCoCoaより人気の検索キーワードになっている。 1. C++/Qtで巡回セールスマン問題を解く こんなQt（バージョン4.7）を、ハチが得意な巡回セールスマン問題を解くミニ・アプリを作りつつ、その使い勝手を確認してみた。下の図が完成品で、ダイアログにキャンバス、プログレスバー、チェックボックス、ボタン二つがあるシンプルな構成となっている。 巡回セールスマン問題は、任意の地点を巡回する最短経路を求める問題だ。巡回箇所が多くなると演算回数が飛躍的に増えるNP問題の典型例
C++0x で多クラス分類器を実装してみた - ny23の日記
C++ の次期標準，C++0x (C++11) の標準案が ISO に全会一致で承認されて一ヶ月半ほど経つので C++0x でプログラムを書いてみることにした．折角なので，以前から実装しようと思っていたサポートクラスに基づく多クラス Passive Aggressive アルゴリズム Exact Passive-Aggressive Algorithm for Multiclass Classification Using Support Class (SDM 2010) を実装してみる． コンパイラには現時点で C++0x に最も対応していると期待できる GCC 4.7 (SVN 先端; 20110927) を利用．GCC の C++0x の対応状況は以下を参照． C++0x Support in GCC - GNU Project - Free Software Foundation
std::(unordered_)map でメモリ使用量を見積もる - ny23の日記
以前，トライと STL コンテナの比較をした際，std::map, std::tr1::unordered_map についてはメモリ使用量をちゃんと測っていなかったが，都合により，コンテナ本体のメモリ使用量を見積もる必要が出てきたので gcc 4.7 の実装を眺めてみた． 結論から言うと，gcc では std::map <_Key, _Tp> のメモリ使用量は， template<typename _Val> struct _Rb_tree_node { _Rb_tree_color; // ノードの色 (enum; int) _Base_ptr; // 親ノードへのポインタ _Base_ptr; // 左ノードへのポインタ _Base_ptr; // 右ノードへのポインタ _Val; // value_type (std::pair <const _Key, _Tp>) }; -> si
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
高速なサーバの書き方補遺 - id:kazuhookuのメモ置き場
Kazuho@Cybozu Labs: 高速なCometサーバを書いてみた件, Kazuho@Cybozu Labs: C++ テンプレートを使って高速な高機能サーバを書く方法 の実装で、やっていることやさぼっていることについて。 epoll や kqueue のような高速な select(2) を使う syscall の数を減らす ソケットをノンブロッキングにしておいて、とりあえず write(2) して EWOULDBLOCK が返ってきた場合のみ poll に登録すべき time(2) 等を毎回呼ばない (キャッシュしておいて別スレッドかメインループで定期的にアップデート) 不必要な抽象化を避ける poll がサポートできるのはソケットとタイムアウトだけ ステートの確認や変更が高速にできるようなデータ構造を使う ソケットオブジェクトはデスクリプタ番号が添字の配列で タイムアウトはビッ
Kazuho@Cybozu Labs: C++ テンプレートを使って高速な高機能サーバを書く方法
« C++ テンプレートで(いまさら)FizzBuzz | メイン | データベースの差分バックアップとウェブサービスのお引っ越し » 2008年04月18日 C++ テンプレートを使って高速な高機能サーバを書く方法 「C++ のメンバ関数ポインタって何のためにあるの」という質問を耳にすることがあります。実際は、たとえばステートマシンを書くのに便利なのですが、ちょうどサイボウズ・ラボの C++ 熱が盛り上がっていることもあり、昔の作ったサーバフレームワークを再実装してみました。ちなみにもともとは、1990年代に東京大学駒場キャンパスで使われていた friends というサービスのバックエンドだった、finger プロキシ用に書いたコードです。ソースコードは /lang/cplusplus/friends_framework - CodeRepos::Share - Trac においてありま
Big Sky :: C++で軽量Webサーバ書いた。
書いたといっても結構前からあったのですが、いらん所を削ぎ落として軽量Webサーバとして仕立て上げました。 軽量とは言えど、CGIを使って結構色々動きます。 例えば、ソースアーカイブを解凍したらCGIがあって、apacheから見える場所にコピーして...とか面倒くさかったりしますよね。 おれは今すぐWebサーバを起動したいんだ！そして今いるディレクトリのファイルをWebサーバからサーブしたいんだー！ って事ないですか？blogソフトウェアをダウンロードして今すぐ試したいけど、apacheインストールされてなかった...とか悲しすぎます。 今回紹介する"tinytinyhttpd"(tthttpd)はそんな、小さい様で大きな問題を解決出来るかもしれないソフトウェアです。 mattn's tinytinyhttpd at master - GitHub tiny tiny httpd http:
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
