Home / CMap

CMap - VC++(MFC) のマップ

CMap の構造

かなり前からあるようで、不安要素も無く、調べてみるとシンプルだし、性能もそこそこなので結構使われているのではなかろうか...

それに、重複を許さない集合を構成したい場合なんか、本来の目的と違うのを承知で使ったりもする。 素早くちょこっと使いたいんだが、なかなか使い方を忘れていたりするので覚書き。

CMap の実装は古典的で、ハッシュ法＋チェイン法が採られている。これは古～～い参考書でも十分参考になる。
←こんな本なんぞを引っ張り出して、整理の為にあらためて図を書いた。

map structure

各要素は内部定義の CAssoc 構造体に保持される。ハッシュテーブルもこのポインタの配列だし、チェインもこれ。

struct CAssoc
{
    CAssoc* pNext;
    UINT nHashValue;        // バケット位置を指す値
    KEY key;
    VALUE value;
};

VC++8 では public な CPair から継承した物になっている （実質変わらないように見えるが、ソースを良く見ていくと nHashValue メンバの意味が変わっている）。 

public:
    struct CPair
    {
        const KEY key;
        VALUE value;
    };

protected:
    class CAssoc : public CPair
    {
        CAssoc* pNext;
        UINT nHashValue;    // ハッシュ関数の値
    };

ハッシュ関数は（後で書くが）グローバル関数で、ハッシュテーブルサイズは関与しない、純粋にハッシュ値を返す仕様。この剰余でハッシュテーブルへの格納位置を決めている。

CMap - 検索:Lookup

検索 Lookup は protected な GetAssocAt() を呼ぶ。
GetAssocAt() はキーのハッシュ値を求め、ハッシュテーブルサイズの剰余をハッシュテーブルの格納位置（バケット:bucket）としてチェインリストを辿る。なお、ハッシュテーブルが空でも nHash を求めている（nHash はハッシュ値でなく bucket の位置を意味する。命名が宜しくない）。

nHash = HashKey<ARG_KEY>(key) % m_nHashTableSize;   // (1)

if (m_pHashTable == NULL)
    return NULL;

CAssoc* pAssoc;
for (pAssoc = m_pHashTable[nHash];
     pAssoc != NULL;
     pAssoc = pAssoc->pNext)
{
    if (CompareElements(&pAssoc->key, &key))    // (2)
        return pAssoc;
}

return NULL;

ふむ、ハッシュ値が同じになったり、（ハッシュ関数が優秀でも）運悪く bucket が同じになると、ユーザー定義の CompareElements 関数で１つ１つ照合しながらチェインを辿る。

この部分が速度低下になる訳だが、VC++8 ではちょっとだけ改良してある。
各要素（CAssoc）の nHashValue にはハッシュ値を記憶するように変えられてあり、CompareElements 関数を呼ぶ前に nHashValue が比較される。完璧なハッシュ関数ならそれだけで済むが、そうはいかないので CompareElements 関数は外せない。 

nHashValue = HashKey<ARG_KEY>(key);
nHashBucket = nHashValue % m_nHashTableSize;

if (m_pHashTable == NULL)
    return NULL;

CAssoc* pAssoc;
for (pAssoc = m_pHashTable[nHashBucket];
     pAssoc != NULL;
     pAssoc = pAssoc->pNext)
{
    if (pAssoc->nHashValue == nHashValue &&     // 先にハッシュ値を比較
        CompareElements(&pAssoc->key, &key))
        return pAssoc;
}

return NULL;

CMap - コレクション クラスのヘルパ

テンプレート関数として AFXTEMPL.H にデフォっぽい定義がある。

template<class TYPE, class ARG_TYPE>
BOOL AFXAPI CompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2)
{
    return *pElement1 == *pElement2;
}

template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
    return ((UINT)(void*)(DWORD)key) >> 4;
}

が、大抵、これでは済まないので独自に定義する（特殊化する）。
これが相応しくない場合は特殊化するか多重定義する。

CompareElements 関数は、一致する場合に 0 以外を返さねばならない。比較関数と言われれば-1,0,1 を返すのが普通なので、あえて変えなくても良かったように思う。

なお、CString の場合、特殊化されてないが、== 演算子があるのでそのままで使える（のだと思う）。

_AFX_INLINE bool AFXAPI operator==(const CString& s1, const CString& s2)
    { return s1.Compare(s2) == 0; }

ここで Compare 関数は大文字と小文字を区別するのだが、では大文字と小文字を区別しない CompareNoCase なんぞに変えたら大文字と小文字を区別しないマップが出来上がるかと言うと、そうはいかない。ハッシュ関数が異なる値を返すからである。
そのような場合、HashKey, CompareElements の両方に CString::MakeUpper() や CString::MakeLower() を埋めるのが１つの手だろうけど、CompareElements は何回も呼び出されるので速度は犠牲になる。

HashKey 関数はキーが CString の場合、特殊化されている。
プロトタイプ宣言は afxtempl.h にあるが、実装は STREX.CPP（strcore.cpp だったりもする）。
CString と言うか、LPCSTR。文字列ならばこれでいいのではなかろうか。

template<> UINT AFXAPI HashKey<LPCSTR> (LPCSTR key)
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

もしくは非テンプレートで書いてもいい。両方見つかれば非テンプレートを選ぶはず。

inline UINT AFXAPI HashKey(LPCSTR key)
{ …

キーが複数のメンバを持つような構造体の場合、その全てのメンバがハッシュ値に変化を及ぼすようにしないといけない。

ハッシュテーブルのサイズ

漢らしくコンストラクタで 17 に設定してある。

CMap(INT_PTR nBlockSize)
{
    m_pHashTable = NULL;
    m_nHashTableSize = 17;  // default size
    m_nCount = 0;

小さ過ぎ！　しかも引数にさえなってない。ハッシュ関数と同じ位、重要なのに...
こんなに小さくてはマップを使う意義が無いので、InitHashTable 関数を呼ぶべし。クラス定義部のコメントには // advanced features for derived classes などと書かれてあるが、コンストラクタにすべきだ。
なお、大きさは MSDN には予想データ数の 120% が良いとある。う～ん、学の無い私には根拠が判らない。

ここで、サイズは素数が良いとされている。何故か？ ... バケット位置はハッシュ値をハッシュテーブルのサイズで割った余りだから、割り切れると先頭に集中するからだと思われる。その効果は微々たるような気もしないでもないが、特に理由が無ければ素数が良かろう。
ただ、素数でなくとも警告は出ない。

ところで、CMap にキー／データを突っ込んだ後で InitHashTable 関数を呼んだらどうなるか？

InitHashTable(UINT nHashSize, BOOL bAllocNow)
{
    if (m_pHashTable != NULL)
    {
        delete[] m_pHashTable;
        m_pHashTable = NULL;
    }

見るからに消えて無くなる。CArray のように、中身を残したまま途中で拡張は出来ない。

(2011-8-11) ちらりと見聞きした処、Java のハッシュ（java.util.Hashtable）はテーブルサイズを自動拡大するそうな...自動的なのかどうか知らないのですが。
う～ん、どんな実装だろう... とりあえず実装するだけなら全要素をナメて新しいハッシュテーブルを使って挿入し直せばいい訳ですが... まさかそんな安直な実装にはしていないと信じたい。

暇があったら調べようと思います。

(2011-8-12) 早速 Hashtable.java を覗いて見る（jdk1.6.0_11）。
map じゃないけど、きっとここでいいんだろうと思う。　さて、ぱっと見た処、予想を裏切ってテーブルサイズの75%(==threshold) を越えたらテーブル再構築しているみたい（410～412）。
Java Hashtable put
rehash() はこれ↓
Java Hashtable put
後で気付いたが、Java API ドキュメントの HashMap や Hashtable に「初期容量」「負荷係数」の語でちゃんと説明されてあった。orz

その２つのクラスは大差無いように見えながら rehash については態度が少し違うみたい。

・Hashtable ... rehash メソッドがいつ呼び出されるか、および呼び出されるかどうかは、実装により異なります。
・HashMap ... 初期容量が、エントリの最大数を負荷係数で割った値より大きい場合、rehash オペレーションは起こりません。

ハッシュテーブルサイズの調整

検索時間もだけど、キー追加時間も気になったので、テストコードを書いて時間測定してみた。
500万個のキー（文字列）を追加・検索した合計時間がY軸（１回の時間じゃなく、500万回の合計時間）。
青色が追加でピンク色が検索。
X軸がハッシュテーブルサイズを5万、50万、500万、600万と変えてみたもの。
1%(=5万/500万)は論外だが、10%ならそこそこの時間、100か120%かは何だか誤差の範疇に思える。

map structure

ショボいPCを使ってたり、乱数キー、対のデータは無いに等しい、と言った条件なので絶対時間は参考にならないが、ハッシュテーブルサイズの効果に関しては参考になると思われ。
テストコードなんかはこちら

ハッシュテーブルとチェインの様子

map chainハッシュテーブルにぶら下がるチェインの分布はどうなっているか？　と思ってシリアライズで吐き出してみたのが左図。

縦方向がハッシュテーブルのインデックス、横がチェインの個数（深さ）。ページ先頭に書いた図からイメージし易いように回転してある。

流石に 全500万のグラフプロットは辛いので、最初の 1000個のみ。


全体でチェインの深さで統計を採ったのが次。
空きスロットが結構有るが、深さ1,2個が大半で、中々良い分布。最深で9個だった。 map chain total


シリアライズ、派生クラス

「ハッシュテーブルとチェインの様子」を調べる時に、シリアライズ機能を調べた。
Serialize メンバ関数が実装されているが、これ、CObject やら CArchive とか MFC/Microsoft にベッタリな流儀で、挙句、CFile しか使えませんだと。…そこらの宗教勧誘みたいで気持ち悪い設計。

一応、CMap::Serialize を見てみると…
書き出しは、最初にデータ個数を書いた後、ハッシュテーブルを基に片っ端からキーとデータを書き出しているだけ。
一方、読み込みはデータ個数を読み取った後、キーとデータを読んで SetAt() の連発。面白味は何も無い。
只、おや？と思ったのは KEY, VALUE が１個の配列が宣言されている処。 

while (nNewCount--) {
    KEY newKey[1];
    VALUE newValue[1];
    SerializeElements(ar, newKey, 1);
    SerializeElements(ar, newValue, 1);
    SetAt(newKey[0], newValue[0]);
}

おそらく無駄なコンストラクタを呼ばない為だと思う。
一見、思慮深く見えるが、KEY を無邪気に SetAt() へ渡しているので ARG_KEY が KEY の参照でないと、ここで引っ掛かる。

なお、読み込む前に RemoveAll() を呼ぶのをお忘れ無く…

さて、同じような処理を書くには PGetFirstAssoc/PGetNextAssoc を使えば良さそうだが、先のチェインの分布を知るにはハッシュテーブルそのものを参照したい。
じゃぁ、と CMap 派生クラスを拵えるが… 何と CAssoc::pNext にアクセス出来ない事に気付く。pNext/nHashValue は private。インナークラスだから CMap 派生クラスじゃ無理。優しくない設計 orz

むぅ、旨い手が思い付かず、MFC/Microsoft の流儀に従っていては前進しないので、afxtempl.h から CMap をコピペした、否、afxtempl.h をコピーして CMap 関係意外の部分を削除したファイルを拵えた。(^∇^)
これ位やらないと知りたい事は得られない。

なお、依然 afxtempl.h をインクルードすれば CMap は活きる訳で、そのままでは困るので、今回は適当な namespace で括って使った。Hoge::CMap クラス。

namespace Hoge
{
template < class KEY, class ARG_KEY, class VALUE, class ARG_VALUE >
class CMap : public CObject
…
} //namespace Hoge

インクルードガード名は変え、詳細不明な #pragma 類はそのまま。 ヘルパー関数（テンプレート関数）も必要になるはずなので afxtempl.h をインクルードした方が良いでしょう。

要素の追加

要素の追加は operator [] でのみ起こる。
SetAt() も有るが operator [] を呼ぶラッパーに過ぎない。

operator [] は GetAssocAt() を呼び、キーが見つからないと要素（CAssoc）を確保する… NewAssoc()
だから不用意に参照してはいけない。見つけるだけなら PLookup/Lookup 関数を呼ぶべし。

NewAssoc() は要素１個分ではなく、ブロック単位で確保される。CMap コンストラクタの nBlockSize 引数がその単位。
そう言う訳で余り見かけない書式の new で書かれている。

…
    m_nCount++;
#pragma push_macro("new")
#undef new
    ::new(pAssoc) CMap::CAssoc(key);
#pragma pop_macro("new")
…

pAssoc はポインタ変数で、これはプレースメントnew。さらに初期化子 CAssoc コンストラクタ付きで key がセットされる。
昔の版を見たら ConstructElements() で初期化していたようだ。

ブロック単位の確保は何やら m_pFreeList で管理されているもよう。CPlex::Create() が使われている。これ afxtempl.h でなく plex.cpp に実体が有り、CList や非テンプレート版にも使われているようだ。

内容の並び

ハッシュ法の最大の欠点で、取り出し（列挙）した時の並びは不規則？になる。
これアプリケーションではマズイ場合が多く、列挙した後に並べ替えが必要になったりする。それに GetNextAssoc では key, val とも返して来るので無駄にメモリアクセスする。
と思っていたら、VC8 版では PLookup(), PGetFirstAssoc(), PGetNextAssoc() が追加されていた。誰しも思うであろう処で、これが struct CPair を追加した理由だろう。
でも別に CAssoc * でも構わなかったんだが... それに POSITION が消えているのはいいのか？

マップのキーと値を印刷したいとか一覧表で見せるような場合なら、挿入し終えた後でゆっくりソートすれば良いが、出来れば挿入の度にソートされていると都合が良い場合もある。さて、どうするか...

挿入の度に Sorted list を作り込めば良さそう。その場合、KEY, VALUE がポインタじゃなく実体である場合を考慮して、CAssoc へのポインタで Sorted list を作りたい。（CAssocのアドレスは不変なのか？ 見た限りでは変わらないと思う。尤も、要素の削除が伴うならばそれも管理せねばならないが…）
operator[] は VALUE& を返すが、残念ながらそれが既存なのか新しい要素なのか教えてくれない （が、前後で要素数を比較すれば新しい要素だったかどうか判る。）

なお、実装を見る限り、新しい要素の VALUE はゼロ初期化されているはずなので、それを判断すれば VALUE のアドレスを採る事は可能。でもキモイな。 CMap を派生して新しく SetAt を追加した方が良さそう。

一方、Sorted list は誰が作るか？ MFC には無い。CList 系はある。比較関数はヘルパの CompareElements に絡む方法がいいかな？

CTypedPtrList を使って CMap とは別に作るとしたら...

CList

マップではないが…

スクリプト系の性能

お手軽なスクリプト系の実力はどうだろう？

Python / C++ std::map

(2020-7-2) Pythonの学習用に書いたもの。キーの型や実行環境が違う。おまけで試した C++ std::map 版は Python とほぼ同じ。

AWK

出来るだけCMapのテストコードに似せ、折角なので 100,200,500万のキー数で測定した。

>awk -f map.awk
 count: 1000000
insert: 13 sec
  find: 16 sec ... 16μsec/件
hit/nohit/total: 5444 / 991907 / 997351

>awk -f map.awk
 count: 2000000
insert: 35 sec
  find: 56 sec ... 28μsec/件
hit/nohit/total: 21561 / 1967673 / 1989234

>awk -f map.awk
 count: 5000000
insert: 179 sec
  find: 336 sec ... 68μsec/件
hit/nohit/total: 132076 / 4800030 / 4932106

流石に CMap より3桁遅いが、意外に速い。 プロトタイプとして利用するには十分。
メモリ消費は 500万で 370 MB程。 map.awk はこれ
（ハッシュテーブルサイズを設定する関数は存在しないし、そのような実装でないとも考えられる。）

連想配列内の要素数が判らないので for で回した。 (s in arr) が検索に相当する。

参考にしたサイト等

変更履歴

2020-7-1　Pythonの例をリンク追加。
2017-6-4,9 要素の追加。テストコード
2011-8-12 ハッシュテーブルのサイズについて、java の件をさらに追記。
2011-8-11 ハッシュテーブルのサイズについて、java の件を追記。
2011-5-25 履歴はここに移動。そう言えば、古参の AWK の配列が連想配列なのは良く知っていたが、PHP の配列も連想配列しか無い事を最近になって知った。PHP 単独で大量データを高速処理するケースは無いと思うが、どの辺りで無理が来るのか、その境界は知っておいた方が得だ。いつか調べよう...
2011-5-5　CList について追記。
Home / CMap

© 2008 usskim    http://usskim.web.fc2.com/
inserted by FC2 system