unordered 系コンテナの max_load_factor 周りについて

この記事は LL/ML Advent Calendar 19日目の記事です。


C++11 で追加された unordered 系のコンテナは、ハッシュを使って要素を管理するコンテナです。
そのハッシュを使ったアルゴリズムもいくつかありますが、C++11 では OpenHashing 方式を想定しているようです。
OpenHashing 方式は、同じバケットに対して複数の要素が入ってしまう場合、リンクリストなどでそれらの要素を繋いでやる方式です。
細かいことやその他の方式については SlideBoom closed down を見ましょう。


この記事では C++11 の unordered 系コンテナ特有の、バケットやリハッシュ関数について説明します。

バケット操作関数

バケットの数は bucket_count() で取得できます。また、n 番目のバケットに入っている要素数bucket_size(n) で取得できます。
つまり、以下のようなイメージです。

バケット数は構築時に指定できます。構築時に x を指定した場合、x <= bucket_count() であることが保証されます。


n 番目のバケットに入っている要素は、begin(n), end(n) を使うことで列挙できます。
つまり、以下のようなイメージです。

begin(n), end(n) が返すイテレータは local_iterator (const の場合は const_local_iterator)で、iterator や const_iterator と同じカテゴリ(つまり ForwardIterator)になります。


ある要素 k が何番目のバケットに入るのかを確認するためには bucket(k) 関数を使います。
つまり、ある要素 k がコンテナに含まれているかどうかを確認する場合、以下の様に書くことが可能です。

#include <unordered_set>
#include <iostream>
#include <iomanip>

bool contain(const std::unordered_set<int>& u, int k) {
  std::size_t bucket = u.bucket(k);
  for (auto it = u.begin(bucket); it != u.end(bucket); ++it) {
    if (*it == k) return true;
  }
  return false;
}

int main() {
  std::unordered_set<int> u = { 314, 159, 265, 359 };
  std::cout << std::boolalpha << "contain(159): " << contain(u, 159) << std::endl;
  std::cout << std::boolalpha << "contain(100): " << contain(u, 100) << std::endl;
}
contain(159): true
contain(100): false

もちろん普段はこんなのを書かず、find() や count() 関数を使ったほうがいいでしょう。

占有率の確認

1つのバケットあたりに、平均でいくつの要素が入っているかという値を、占有率(load factor)と呼びます。
占有率が高くなると、バケットから要素を辿る量が平均的に多くなるので、速度が遅くなってきます。
そこで、多くの OpenAddressing 方式では、占有率がある一定量を超えると、より大きなバケットを作り、既存の要素をそのバケットに対して入れ直します。これをリハッシュと呼びます。


C++11 の unordered 系もこの戦略を採用しています。
占有率を返す関数が load_factor() 関数です。内部的には単に static_cast(size()) / static_cast(bucket_count()) しているだけです。
占有率がどれぐらいまで増えるとリハッシュを行うかというしきい値(最大占有率)が max_load_factor() 関数です。構築直後は 1.0f になっています。
max_load_factor(0.5) などのように、最大占有率を設定することもできます。この際、リハッシュが行われることがあります。
リハッシュが行われると、そのコンテナに対する既存のイテレータは全て無効になるので注意しましょう。


ある要素を insert() などで追加した場合にリハッシュが発生するかどうかを知りたい場合、以下の様なコードで判断できます。

// u に n 個の要素を insert したときにリハッシュが発生するかどうか
template<class UnorderedContainer>
bool will_be_rehash(const UnorderedContainer& u, std::size_t n) {
  return u.size() + n >= u.max_load_factor() * u.bucket_count();
}

挿入した場合の要素数が u.size() + n で、(u.size() + n) / u.bucket_count() が新しい占有率になります。これが最大占有率以上になるかどうかなので、(u.size() + n) / u.bucket_count() >= u.max_load_factor() となり、除算は怖いので乗算に直すと上記の式になります。

ハッシュ関数

rehash(n) 関数は、n 個以上のバケット数でリハッシュを行います。
つまり実行後は必ず n <= bucket_count() となるようにリハッシュを行います。最初から n <= bucket_count() になっているなら、リハッシュを行わない可能性もあります。


reserve(m) 関数は、少なくとも m 個の要素まではリハッシュを行わないようにします。
つまり最低でも m / max_load_factor() 個より多いバケットを用意します*1


ここでの reserve() 関数は、指定した要素数以上は格納できるようにするという点で vector::reserve() とよく似ています。
しかし、vector::reserve(m) は、m が capacity() より小さい場合には何もしないと規定されている(つまりコンテナサイズは小さくならない)のに対し、unordered 系の reserve() 関数にはそのような規定はありません。つまり、reserve() によって bucket_count() が小さくなる可能性もあるということです(もちろん load_factor() が max_load_factor() を超えることはありませんが)。
これは reserve() だけでなく、rehash() や max_load_factor() などでも同じです。
ただし、必ず小さくなる訳ではないので、確実にバケット数を減らしたいなら Shrink to Fit イディオムを使いましょう。

まとめ

unordered 系のコンテナ特有のバケット関数やリハッシュ関数を見てきました。
C++ で、しかも Associative Container ではなく Unordered Associative Container が必要であるという状況は、かなり速度が必要である場面である可能性が高いでしょう。
そのため、このような関数は重要です。
このあたりの関数をうまく使って、unordered 系のコンテナを効率的に扱いましょう。


.

*1:仕様上では a.rehash(ceil(n / a.max_load_factor())) と同じ、となっています

組み込み関数を隠してしまった場合

この記事は Python Tips Advent Calendar 2012 19日目の記事です。


Python には何も import しなくても使える組み込み関数がありますが、これらと同名の変数を定義することができます。

>>> id             # id 組み込み関数
<built-in function id>
>>> id = 10        # 同名の変数を定義
>>> id             # id 組み込み関数が隠れる
10

このように、同名の変数を定義すると、その組み込み関数は見つからなくなります。


もしこの状態で組み込み関数を使いたいなら、以下のように __builtin__ モジュールから取得します。

>>> import __builtin__
>>> __builtin__.id
<built-in function id>

__builtins__ (s 付き)を使うのは間違いです。これは実装の詳細であるため、ポータビリティは無く、動作は保証されません。


.

iterable を分ける

この記事は Python Tips Advent Calendar 2012 18日目の記事です。


Python の iterable オブジェクトから生成された iterator は一度しか走査できません。

>>> xs = iter([1,2,3])
>>> for x in xs: # xs の要素を全て消費
...     pass
>>> # もう消費したオブジェクトを戻せない
>>> xs.next() #doctest: +ELLIPSIS
Traceback (most recent call last):
  ...
StopIteration

しかし itertools.tee を使うことで、複数の独立した iterator に分けることができます。

>>> from itertools import tee
>>> xs = iter([1,2,3])
>>> ys,zs = tee(xs, 2) # 2 は分割数。省略した場合は 2 になる
>>> for y in ys:
...     print y
1
2
3
>>> for z in zs:
...     print z
1
2
3

ただし、tee は単に消費した要素をキューに詰めて再度使えるようにしているだけなので、この例のように、片方を全て消費してからもう片方を消費するという場合は、全ての要素をメモリに入れて列挙するのと同じだけのメモリを取ります。
この場合、ドキュメントにも書いてあるように、単に list に格納した上で使ったほうがいいでしょう。


tee は、例えば以下の様な、隣り合った要素を取り出すようなケースで有用です。

>>> from itertools import tee, izip, islice
>>> xs = iter(range(5))
>>> ys,zs = tee(xs)
>>> for y,z in izip(ys, islice(zs, 1, None)):
...     print y,z
0 1
1 2
2 3
3 4

これは ys と zs の進んでいる数が 1 個しか違わないので、1 要素分しかメモリを取りません。
たとえ xs の要素が無限リストであったとしても、これなら処理できます。


.

iter に関数を渡す

この記事は Python Tips Advent Calendar 2012 17日目の記事です。


iter 関数は、iterable オブジェクトから iterator を取り出す関数です。

>>> xs = [1,2,3]
>>> it = iter(xs)
>>> it.next()
1
>>> it.next()
2
>>> it.next()
3
>>> it.next() #doctest: +ELLIPSIS
Traceback (most recent call last):
    ...
StopIteration

このように iter 関数に iterable オブジェクトを渡すのが通常の使い方ですが、この iter 関数の引数には、関数も渡すことができます。

>>> import StringIO
>>> msg = '''\
... aaa
... bbb
... ccc
... 
... eee
... '''
>>> strs = StringIO.StringIO(msg)
>>> for line in iter(strs.readline, '\n'): # 空行が現れるまで読む
...   print line[:-1]
aaa
bbb
ccc

このように、第一引数に関数を、第二引数にその関数が何を返したら終了するかという条件を指定すると、その条件が現れるまで関数を呼び続けます。


.

roundの桁数指定

この記事は Python Tips Advent Calendar 2012 16日目の記事です。


round 関数は、指定した桁で四捨五入してくれます。

>>> round(1234.5678, 2)
1234.57

実はこの値、マイナス値も指定できます。

>>> round(1234.5678, -2)
1200.0

マイナス値を指定すると整数部分の桁が四捨五入されます。


.

データのフラット化

この記事は Python Tips Advent Calendar 2012 15日目の記事です。


2次元のデータを1次元のデータにしてしまいたいときがあります。その場合、リストに対しては以下のように書けます。

>>> xss = [[1, 2], [3], [4, 5, 6]]
>>> sum(xss, [])
[1, 2, 3, 4, 5, 6]

タプルでも同様に書けます。
ただし、内側のデータが、ジェネレータなどの一度しか走査できないものに対してはこの方法では無理です。
そういう場合は 内包表記いろいろ で説明した多重 for を使うといいです。

>>> [x for xs in xss for x in xs]
[1, 2, 3, 4, 5, 6]

また、リスト化するとメモリに収まらないほど巨大なデータになってしまう、あるいは全てのデータが必要な訳ではないなら、これらの処理を itertools.chain で繋げるのがいいでしょう。

>>> from itertools import chain
>>> list(chain(*xss))
[1, 2, 3, 4, 5, 6]


.

2次元データの縦と横を入れ替える

この記事は Python Tips Advent Calendar 2012 14日目の記事です。


Python では、2次元配列などのデータに対して縦と横を入れ替える(transpose)が簡単にできます。
zip を使うだけです。

>>> xss = [[1, 2, 3],
...        [4, 5, 6],
...        [7, 8, 9]]
>>> zip(*xss)
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

zip の場合、縦と横の長さが違うときは、一番短いデータに合わさることになります。

>>> xss = [[1, 2, 3],
...        [4, 5],
...        [7]]
>>> zip(*xss)
[(1, 4, 7)]

長い方に合わせたい場合、filter, map に指定する関数 で書いたように、map や izip_longest を使うといいです。

>>> xss = [[1, 2, 3],
...        [4, 5],
...        [7]]
>>> map(None, *xss)
[(1, 4, 7), (2, 5, None), (3, None, None)]


.