STL風に使えるマップ型コンテナの紹介と性能比較 - Preferred Networks Research & Development
最近スマートフォンに乗り換えました。徳永です。 C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。 以下、計算量の表記をする際には、要素数をnとします。 Loki::AssocVector LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ
最速の疎ベクトルはどれだ - Preferred Networks Research & Development
海野です。 自然言語処理などで機械学習を行おうとすると、非常に疎なベクトル表現を使いたくなります。疎、というのはほとんどの要素が0である、という意味です。前々から疎ベクトルライブラリのパフォーマンスに関して気になっていたので、幾つか調べてみました。 Jubatus Workshopでも話したとおり、機械学習を適用しようとすると、普通は対象のデータをベクトル表現に落とします。特に言語データの場合は、それぞれの単語や文字などを特徴次元とするため、非常に疎なベクトルとなってしまいます。純粋な配列（C++で言えばstd::vector）を使ってしまうと、大量にメモリを食ってしまうため疎ベクトル専用の表現を使うのが普通です。 今日は様々な疎ベクトルライブラリのパフォーマンス比較を行おうと思います。比較したライブラリは以下のとおり。真の意味で、疎ベクトルのライブラリは、Eigenとublasだけで、残
Artistic Style
下記は astyle 1.15.3 の astyle.html を適当に日本語化してみたものです。 Artistic Style 1.15.3 C , C++ , C# , Javaソースコード用 フリー で速くて小さい自動整形ツール by Tal Davidson, Israel (E-mail: davidsont@bigfoot.com) Artistic Style は C, C++, C#, Java のソースコードのインデントや整形を行える。 ソースコードをインデント付けするとき、プログラマはインデントに合わせて空白とタブ の両方を用いやすい。さらに、エディタによってはデフォルトでタブキーが押されると空白を挿入したり、また(例えばEmacsでは)行中のコードの手前に自動で空白を置いたりあるいは段付けに今までタブだけを使用したコードに空白を挿入したりして行を整えたりする。 ソース
並列メッセージングフレームワーク「MessagePack-RPC for C++」リリース - Blog by Sadayuki Furuhashi
分散KVS kumofs のコードは、全体で約2万行です。 そのうち、ネットワークI/Oやプロトコルに関するコードは約1万行で、全体の約半分を占めています。 並列イベント駆動I/Oフレームワーク「mpio」リリース ネットワークアプリケーションを実装する上で、もっとも大きな障壁は、ネットワークI/Oとプロトコルです。 では、それが両方ともフレームワークでサポートされ、コードを書く必要が無くなったらどうでしょうか？ 54行で簡単な分散KVSを実装したり、140行で分散リアルタイム検索エンジンを実装することができます。すなわち、インデックス作成サーバ、検索サーバ、DBサーバなど、多数のサーバが連携し、スケールアウトの恩恵を得ることができるネットワークアプリケーションを、１台のホスト上で動作する並列アプリケーションとほぼ同じように書くことができます。 実装上の問題から解放されれば、並列性や耐障害
Boost 数学関係ライブラリの使い方
boost::numeric::ublas 線形代数ライブラリの使い方 連立方程式を解く・逆行列を求める DT Specials -> Boost -> boost::numeric::ublas 線形代数ライブラリの使い方 Last update : Jan. 13th, 2005 はじめに この文書は，線形演算ライブラリ boost::numeric::ublas の使い方の一部を簡単に説明したものです． どうも boost ― uBLAS については日本語の説明書きがないようです．頼みの日本語解説書[2]も uBLAS はたった 2 ページ．Web をあさっても私の希望にあう解説は見あたりません．仕方がないので英語のオリジナルドキュメントと格闘しました．その結果，なんとか連立1次方程式を解くことと，逆行列を求めることはできるようになったので，私と同じようなお悩みを抱えて Web を巡
全文検索エンジン Miniseをリリース + WEB+DBで全文検索の特集記事 - DO++
全文検索エンジンの Minise: MIni Search Engineをリリースしました． このエンジンは全文検索の基本的な機能をサポートしたもので，索引手法は逐次検索（索引無），N-gram，転置ファイル，接尾辞配列をサポートしており，そこそこ最適化を行ってます．Wikipedia日本語版を実験で使ったもので20万文書で構築時間が500秒前後，検索時間が一クエリあたり数msとなっています． BSDライセンスで公開しています． 割りきって，機能を絞ってシンプルな構成にしていますので改造したりしやすいようになっています。まだ、ドキュメントはないですが、C++ APIとして利用しやすいようにもなっていますので、研究用途などで新しい索引やランキングとかでの利用も想定しています（実際に研究用で使ってます）． --- 今回の全文検索ライブラリを開発する機会になったのが，私が担当した今月号のWEB+
tokuhirom blog
Blog Search when-present<#else>when-missing. (These only cover the last step of the expression; to cover the whole expression, use parenthesis: (myOptionalVar.foo)!myDefault, (myOptionalVar.foo)?? ---- ---- FTL stack trace ("~" means nesting-related): - Failed at: ${entry.path} [in template "__entry.ftlh" at line 3, column 25] - Reached through: #include "__entry.ftlh" [in template "entry.ftlh" at
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
std::priority_queue - blanket log
よく嵌るのでメモ。 大きなものから出てくる 比較関数の実装法は頭に入れておく コンパイラのエラーメッセージに期待しない priority_queue<Hoge> pq; のように使うHogeクラス では、デフォルトでは比較に std::less<Hoge> が使われるので operator< の実装が必要。 class Hoge { ... bool operator<(const Hoge &a) const; }; 二つのconst を忘れると悲惨なことになります。 比較関数の部分を分離しようとすると、「型」が必要なので普通の関数でなくファンクタクラスが必要。 struct Compare : public binary_function<Hoge,Hoge,bool> { bool operator()(const Hoge &a, const Hoge &b) { ... } };
株式会社エス・スリー・フォー » 安定な優先順位付きキュー
安定な優先順位付きキュー queueによるコマンドの受信と処理 小さなclient/serverシステムのserver側の設計/実装に関わることになりました。serverには複数のclientが接続され、各clientからのコマンドを受信し、コマンドに応じた処理を行なって結果をclientに投げ返します。 僕はこのserverアプリケーションを、2つのスレッドで実現しようと考えました。すなわち、clientからのコマンドを受信する R_thread と、コマンドの解析/処理/送信を行なう S_thread を起動します。 そしてこの2つのスレッドの間にコマンドを要素とするqueueを置くことで、スレッド間のコマンドの受け渡しを行なうことにしました。server実装のアウトラインは以下のようになります: struct command { // clientから受信したデータ... }; st
C++ Library Links
このページの他に、岡野原さんの "C++の便利ツール・ライブラリ" がオススメです。 標準ライブラリ STL その１。主に、リストやマップなどのコレクションに関する generic なデータ構造とアルゴリズム。 iostream その２。ストリーム入出力。 C.std その３。まだまだ現役。 boost 準標準。上の３つを超強力にした/するライブラリ達の集合体。 並列・ネットワーク・XML TBB (Thread Building Blocks) スレッドセーフなコンテナやスレッドをフル活用した並列アルゴリズムなど TinyXML 名前の通り軽量でまとまってるXMLパーザ。 MiX Minimalists XML parser。同じくXMLパーザ。 libcurlpp FTP, FTPS, HTTP, HTTPS, GOPHER, TELNET, DICT, FILE, LDAP によるフ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Effective STL 11
C++編（標準ライブラリ）●Programing Place