stdext Relations:データテーブル(DataTable)

stdext Relations:データテーブル(DataTable)許式偉
2008-7-22
Relationコンテナの概要
Relationは複雑な容器です.簡単に言えば、データテーブル(DataTable)です.データベース(Database)のテーブルに似ています.もちろん、単純なテーブルです.単純化は、複雑なSQL文がなく、キーワード(インデックス)ベースのselectをサポートするだけです.
適用シーン:データに複数の列があり、相互検索(複数対複数の関係)が必要な場合は、Relationコンテナが適しています.
有名なGLib(GNOME Library)にはGRelationがあり、stdext Relationの機能と似ています.しかし、stdext Relationの機能はもっと強いです.これは以下のように表現されています.

stdextのRelationは、真のデータテーブル(DataTable)であり、2列だけでなく任意の複数列のデータを作成することができる.2列のテーブルを作成するには、stlのstd::pair(もちろんboost::tuple)を使用することができる.2列を超えるテーブルを作成するには、boost::tupleを使用する.

は、任意のカラムのインデックスを作成し、各カラムがインデックステーブルとしてmap(赤黒ツリー)またはhash map(ハッシュテーブル)を使用するかを独立して指定することができる.

は、複数のカラムの結合プライマリ・キーを作成し、これらのカラムの結合データが重複しないようにすることができる.

Relation単純サンプル
次に、Relationの例を示します.簡単にするために、この例は2カラムのテーブルであり、すべてのカラムはhash mapをインデックスとして使用します.この例はstdext/examples/relation/Simplest.cppで見つけることができる.

typedef std::AutoFreeAlloc AllocT;
typedef std::pair<std::string, int> TupleT;
typedef std::Relation<TupleT, 3, 0, std::HashMapIndexing, AllocT> RelationT;
typedef RelationT::Indexing<0> Indexing0;
typedef RelationT::Indexing<1> Indexing1;

AllocT alloc;
RelationT rel(alloc);

rel.insert(TupleT("Mon", 1));
rel.insert(TupleT("Monday", 1));
rel.insert(TupleT("Tue", 2));
rel.insert(TupleT("Wed", 3));
rel.insert(TupleT("Wednesday", 3));
AssertExp(rel.size() == 5);

Indexing1::range rg = rel.select<1>(3);
AssertExp(std::distance(rg.first, rg.second) == 2);
for (Indexing1::iterator it = rg.first; it != rg.second; ++it) {
const TupleT& i = Indexing1::item(it);
AssertExp(i.first == "Wed" || i.first == "Wednesday");
AssertExp(i.second == 3);
}

Indexing0::range rg2 = rel.select<0>("Mon");
AssertExp(std::distance(rg2.first, rg2.second) == 1);
Indexing0::iterator it2 = rg2.first;
const TupleT& i2 = Indexing0::item(it2);
AssertExp(i2.first == "Mon" && i2.second == 1);

AssertExp(rel.count<1>(1) == 2);
AssertExp(rel.erase<1>(1) == 2);
AssertExp(rel.count<1>(1) == 0);
AssertExp(rel.size() == 3);

Indexing0::range rg3 = rel.select<0>("Mon");
AssertExp(std::distance(rg3.first, rg3.second) == 0);
AssertExp(rel.count<0>("Monday") == 0);

Relationその他の例...
もしこれがあなたのニーズを満たしていない場合、私たちはもっと複雑なサンプルを持っています(同様に、これらのサンプルはstdext/examples/relation/Simplest.cppで見つけることができます):
testCustomIndexing
この例では、インデックスをカスタマイズする方法を示します.
//Field 0: rb-tree indexing//Field 1..(N-1): hash-table indexing
すなわち0列目はrb-tree(赤黒ツリー)を用い,他の列はhashテーブルをインデックスとする.
testTupleRelation
複数列のサンプルをサポートします(boost::tupleを使用しています).
stdext Relation vs.GRelation(GLib)性能比較
試験手順:stdext/performance/relation/Performance.cpp
主に2つの操作を比較します:挿入(insert)と検索(select).注意:最新のコードを取ると、stdext Relationの表現はもっと良いはずです.これは私が再び最適化したためですが、ここのテストデータを更新していません.
挿入(insert)の比較結果===== GRelation (insert) =====
---> Elapse 37163475 ticks (37.16 ms) (0.00 min) ...
---> Elapse 38908908 ticks (38.91 ms) (0.00 min) ...
---> Elapse 37951608 ticks (37.95 ms) (0.00 min) ...
---> Elapse 38112183 ticks (38.11 ms) (0.00 min) ...
---> Elapse 38991814 ticks (38.99 ms) (0.00 min) ...
---> Elapse 37209503 ticks (37.21 ms) (0.00 min) ...
---> Elapse 37091604 ticks (37.09 ms) (0.00 min) ...
---> Elapse 38056097 ticks (38.06 ms) (0.00 min) ...
---> Elapse 37491538 ticks (37.49 ms) (0.00 min) ...
---> Elapse 37197071 ticks (37.20 ms) (0.00 min) ...
---> Elapse 36716046 ticks (36.72 ms) (0.00 min) ...
---> Elapse 35923233 ticks (35.92 ms) (0.00 min) ...
---> Elapse 36989910 ticks (36.99 ms) (0.00 min) ...
---> Elapse 36041970 ticks (36.04 ms) (0.00 min) ...
---> Elapse 37710083 ticks (37.71 ms) (0.00 min) ...
---> Elapse 38065317 ticks (38.07 ms) (0.00 min) ...
Average: ---> Elapse 37476272 ticks (37.48 ms) (0.00 min) ...

===== Relation (insert) =====
---> Elapse 7990647 ticks (7.99 ms) (0.00 min) ...
---> Elapse 8297058 ticks (8.30 ms) (0.00 min) ...
---> Elapse 9548964 ticks (9.55 ms) (0.00 min) ...
---> Elapse 8238109 ticks (8.24 ms) (0.00 min) ...
---> Elapse 8142560 ticks (8.14 ms) (0.00 min) ...
---> Elapse 8000914 ticks (8.00 ms) (0.00 min) ...
---> Elapse 7674457 ticks (7.67 ms) (0.00 min) ...
---> Elapse 7784394 ticks (7.78 ms) (0.00 min) ...
---> Elapse 8068944 ticks (8.07 ms) (0.00 min) ...
---> Elapse 7860595 ticks (7.86 ms) (0.00 min) ...
---> Elapse 7785512 ticks (7.79 ms) (0.00 min) ...
---> Elapse 8525382 ticks (8.53 ms) (0.00 min) ...
---> Elapse 7681512 ticks (7.68 ms) (0.00 min) ...
---> Elapse 7877846 ticks (7.88 ms) (0.00 min) ...
---> Elapse 7896565 ticks (7.90 ms) (0.00 min) ...
---> Elapse 7597069 ticks (7.60 ms) (0.00 min) ...
Average: ---> Elapse 8060658 ticks (8.06 ms) (0.00 min) ...検索(select)の比較結果===== GRelation (select) =====
---> Elapse 18511577 ticks (18.51 ms) (0.00 min) ...
---> Elapse 15667689 ticks (15.67 ms) (0.00 min) ...
---> Elapse 16131391 ticks (16.13 ms) (0.00 min) ...
---> Elapse 15866818 ticks (15.87 ms) (0.00 min) ...
---> Elapse 15679213 ticks (15.68 ms) (0.00 min) ...
---> Elapse 16461061 ticks (16.46 ms) (0.00 min) ...
---> Elapse 15717209 ticks (15.72 ms) (0.00 min) ...
---> Elapse 16135303 ticks (16.14 ms) (0.00 min) ...
---> Elapse 15502853 ticks (15.50 ms) (0.00 min) ...
---> Elapse 16177000 ticks (16.18 ms) (0.00 min) ...
---> Elapse 15647992 ticks (15.65 ms) (0.00 min) ...
---> Elapse 15948956 ticks (15.95 ms) (0.00 min) ...
---> Elapse 15846702 ticks (15.85 ms) (0.00 min) ...
---> Elapse 15622359 ticks (15.62 ms) (0.00 min) ...
---> Elapse 16597469 ticks (16.60 ms) (0.00 min) ...
---> Elapse 15605666 ticks (15.61 ms) (0.00 min) ...
Average: ---> Elapse 16069953 ticks (16.07 ms) (0.00 min) ...

===== Relation (select) =====
---> Elapse 3047628 ticks (3.05 ms) (0.00 min) ...
---> Elapse 3125855 ticks (3.13 ms) (0.00 min) ...
---> Elapse 2869383 ticks (2.87 ms) (0.00 min) ...
---> Elapse 2919881 ticks (2.92 ms) (0.00 min) ...
---> Elapse 3014382 ticks (3.01 ms) (0.00 min) ...
---> Elapse 2921627 ticks (2.92 ms) (0.00 min) ...
---> Elapse 2875459 ticks (2.88 ms) (0.00 min) ...
---> Elapse 2843331 ticks (2.84 ms) (0.00 min) ...
---> Elapse 3197377 ticks (3.20 ms) (0.00 min) ...
---> Elapse 2871687 ticks (2.87 ms) (0.00 min) ...
---> Elapse 2821260 ticks (2.82 ms) (0.00 min) ...
---> Elapse 3263100 ticks (3.26 ms) (0.00 min) ...
---> Elapse 2905074 ticks (2.91 ms) (0.00 min) ...
---> Elapse 2855135 ticks (2.86 ms) (0.00 min) ...
---> Elapse 3093517 ticks (3.09 ms) (0.00 min) ...
---> Elapse 2958995 ticks (2.96 ms) (0.00 min) ...
Average: ---> Elapse 2973980 ticks (2.97 ms) (0.00 min) ...なぜstdext RelationはGRelationよりこんなに良いのですか?
実は両者の実現案は完全に似ている.唯一の違いは、GLibが不要なHashTableを1つ増やしたことであり、GLibは挿入時に余分な検索を1回増やした(ただしselect性能はこの余分なHashTableの影響ではない).しかし、この点では、どうしてもそれほど悪くない:両者の性能差が5倍程度あることがわかります.
この例は典型的だ.CがC++よりも効率的なコードを書きやすいと考えている人は、パフォーマンスの違いが主にどこにあるかを考えるべきです.
実は肝心な性能の違い(一つ)はCがコールバック(callback)、C++がシミュレーション関数(functor)を使ったことだと思います.
この問題はsort関数でより顕著である.sortでは関数呼び出しが非常に頻繁であり,HashTableよりも頻繁であるからである.
したがって,C++のstd::sortの性能はどの言語でも同列に論じられない.シミュレーション関数(functor)の詳細については、http://cpp.winxgui.com/cn:functorを参照してください.