melpon日記 - HaskellもC++もまともに扱えないへたれのページ

2012-12-21

[]yield の戻り値を受け取る 10:02 yield の戻り値を受け取るを含むブックマーク

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


yield の呼び出しには戻り値があります。

普段は None ですが、呼び出し元が send 関数を使った場合、その引数が yield の戻り値として渡されます。

>>> def f(xs):
...     n = None
...     for x in xs:
...         if n is None or n == 0:
...             n = yield x
...         else:
...             n -= 1
>>> it = f([1,2,3,4,5,6,7,8,9])
>>> it.next()
1
>>> it.send(1) # skip 1
3
>>> it.send(4) # skip 4
8

it.send(1) によって n = yield x の n に 1 が渡されます。


.

トラックバック - http://d.hatena.ne.jp/melpon/20121221

2012-12-20

[]関数のデフォルト値の初期化タイミング 20:20 関数のデフォルト値の初期化タイミングを含むブックマーク

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


Python の関数にはデフォルト値が付けられます。

このデフォルト値は、その関数を呼び出したタイミングではなく、その関数を定義したタイミングで初期化されます。

>>> def f():
...     print 'called f'
...     return []
>>> def bar(x = f()): # この bar 関数の定義で f() が呼ばれる
...     x.append(1)
...     return x
called f
>>> bar() # この呼び出しのときには f() は呼ばれない
[1]
>>> bar() # 同じデフォルト値を使っているので、前回のリストが残ったままになっている
[1, 1]
>>> bar()
[1, 1, 1]

このようになります。

もし呼び出したタイミングでデフォルト値を決めたいなら、その引数に通常入ってこない定数と比較するのが一般的なようです。

>>> def bar(x = None):
...     x = x or f() # x が False として評価できる値だったら f() を代入する
...     x.append(1)
...     return x
>>> bar()
called f
[1]
>>> bar()
called f
[1]

.

トラックバック - http://d.hatena.ne.jp/melpon/20121220

2012-12-19

[]組み込み関数を隠してしまった場合 17:39 組み込み関数を隠してしまった場合を含むブックマーク

この記事は 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 付き)を使うのは間違いです。これは実装の詳細であるため、ポータビリティは無く、動作は保証されません。


.

[] unordered 系コンテナの max_load_factor 周りについて 23:49  unordered 系コンテナの max_load_factor 周りについてを含むブックマーク

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


C++11 で追加された unordered 系のコンテナは、ハッシュを使って要素を管理するコンテナです。

そのハッシュを使ったアルゴリズムもいくつかありますが、C++11 では OpenHashing 方式を想定しているようです。

OpenHashing 方式は、同じバケットに対して複数の要素が入ってしまう場合、リンクリストなどでそれらの要素を繋いでやる方式です。

細かいことやその他の方式については あなたの知らないハッシュテーブルの世界 を見ましょう。


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


バケット操作関数

バケットの数は bucket_count() で取得できます。また、n 番目のバケットに入っている要素数は bucket_size(n) で取得できます。

つまり、以下のようなイメージです。

f:id:melpon:20121219212440p:image:w360

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


n 番目のバケットに入っている要素は、begin(n), end(n) を使うことで列挙できます。

つまり、以下のようなイメージです。

f:id:melpon:20121219212441p:image:w360

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<float>(size()) / static_cast<float>(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() 個より多いバケットを用意します((仕様上では a.rehash(ceil(n / a.max_load_factor())) と同じ、となっています))。


ここでの 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 系のコンテナを効率的に扱いましょう。


.

kariya_mitsurukariya_mitsuru 2012/12/20 00:06 max_load_factor(float z) って標準では Complexity が Constant なんで、リハッシュできないはずなんですよね・・・
gcc も vc もリハッシュするんですが・・・

melponmelpon 2012/12/20 09:52 標準的には void max_load_factor(float z) { mlf_ = max(z, load_factor()); } を想定してた感がありますね…。
探してみるとこの問題は issue に上がってるようです。
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2198

kariya_mitsurukariya_mitsuru 2012/12/20 11:02 さっそくの返信ありがとうございます!
2012/10/09って結構新しいですね。
Proposed resolutionは書いてないですが、私の疑問点はほとんど書いてありました。
私も Complexity は Constant じゃなくてもいいんではないかと思います。

ついでに言うと、insert とかの際のリハッシュの条件(てか、イテレータが無効になる条件) (N+n) < z * B と rehash の事後条件 a.bucket_count() > a.size() / a.max_load_factor() に等号がないのも微妙に気になってます。

kariya_mitsurukariya_mitsuru 2012/12/20 11:40 すみません、リハッシュしない条件(イテレータが無効にならない条件)でしたm(__)m

そして、そっち関連の issue もありますね(^^;
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2156

トラックバック - http://d.hatena.ne.jp/melpon/20121219

2012-12-18

[]iterable を分ける 13:40 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 の要素が無限リストであったとしても、これなら処理できます。


.

トラックバック - http://d.hatena.ne.jp/melpon/20121218

2012-12-17

[]iter関数を渡す 18:08 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

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


.

トラックバック - http://d.hatena.ne.jp/melpon/20121217