C++ 高速化 - speedkumoのプログラミング日記
研究でC++でソフトウェアの開発を行っていますが データ量が少ない場合は速度はあまり、気にしなくていいのですが、 データ量が増えてくると、計算量などを意識して、高速化をする必要性を感じてきました。 自分は実装でSTLのmapやmultimapを使っているのですが、mapの検索の計算量がO(log n),multimapの計算量がO(nlogn)なのでここで、時間を食っているのだと考えられます。 そのため、この部分の計算量を減らす方法を検討しました。 まず、STLのmapの計算量がlog(n)なのは、実装に二分木が用いられるためです。そのため、このmapの実装をhashで行ったら高速化されるのではないかと考えました。 詳しい説明は以下 BoostでC++0xのライブラリ「TR1」を先取りしよう (5) (1/2)：CodeZine（コードジン） そこで、調べていくと、boostで計算量がO(
C++, STL: 基礎的な覚え書き（サンプルソース）
/* キーをカテゴリとして、複数の要素（配列）を持つmapオブジェクトを作る */ #include <iostream> #include <vector> #include <map> #include <string> using namespace std; /* 複数の要素を指定された区切り文字で連結した */ /* 文字オブジェクトを返す */ string join(vector<string> &v, char *delim) { string out; vector<string>::iterator ite = v.begin(); for(; ite != v.end(); ite++) { out.append(*ite); if((ite + 1) != v.end()) out.append(delim); } return out; } int main()
相互の関係性をうまくモデリングする : あんちょこ
さてさて、std::mapの解説も終わったところで本命の双方向の関係性について書こう。前回はポインタで相互に連結しようとして問題にぶち当たった。今回は総当り表のような構造をclassの外部に持たせることを考えてみよう。 まずは関係を表すRelationshipクラスを定義する。 //Relationship.hpp #ifndef INC_RELATIONSHIP_HPP #define INC_RELATIONSHIP_HPP #include <map> #include <string> #include "Person.hpp" enum Relation{ None, Friend, Teacher, Student }; std::string toStr(Relation); class Relationship{ public: void registerRelation(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
