発表者：江添亮
言語：C++
仕事：ドワンゴ
趣味：ボルダリング、factorio
C++17
2017年に発行される予定の標準規格
変更点
多数のマイナーな問題の修正
コア言語の新機能は少ない
新しいライブラリが多い
正式な規格はまだ変わる可能性がある
みんな文字列検索してますか？
boyer moore search
Robert S. BoyerとJ Strother Mooreが1977に発表した
高速な文字列検索アルゴリズム
みんな知ってるよね？
知らない方に朗報
Donald Knuth著
The Art of Computer Programming Vol.4A
アスキードワンゴから今秋発売予定
コード例
auto pattern = "..."s ;
auto text = "..."s ;
auto bm_search =
make_boyer_moore_searcher
( begin(pattern), end(pattern) ) ;
auto iter = bm_search( begin(text), end(text) ) ;
ジェネリックな実装になっている
char型以外でも使用可能
よくあるcharに対するBM法の実装
パターン中の文字に対応するスキップ数をテーブルで持っておく
// charの全状態数
std::size_t skip_table[256] ;
std::string pattern ;
auto len = pattern.size() ;
std::fill_n( table, 256, len ) ;
for ( auto c : pattern )
{
skip_table[c] = len-- -1 :
}
char16_tなら？
// 524KB
// sizeof(size_t) == 8
std::size_t skip_table[65536] ;
char32_tなら？
// 34GB
std::size_t skip_table[4294967296] ;
パターンに含まれている文字種は少ないので
unordered_mapで管理すればいい
std::basic_string<T> pattern ;
auto len = pattern.size() ;
std::unordered_map<T, std::size_t> skip_table ;
for ( auto c : pattern )
{
skip_table[c] = len-- -1 ;
}
unordered連想コンテナーを使うことで
hash対応した任意の型に対して使用できる
charの場合に最適化することも可能
boyer_moore_horspool_searcher
実行時間と引き換えにメモリ消費量が少ない版
optional<T>
T型のオブジェクトを持っているかもしれないクラス
期待するオブジェクトを生成できず
エラー通知の必要のある関数
// 除算する関数
int div( int x, int y )
{
if ( y != 0 )
return { x / y } ;
else
return // どうする？
}
特別な値を返す
この場合は使えない
結果として通知する型はすべての値を取りうる
戻り値と引数で結果を返す
極めて読みづらい
// 戻り値でエラー通知、引数で結果
bool div( int x, int y, int & result ) ;
// 戻り値で結果、引数でエラー通知
int div( int x, int y, bool & error ) ;
グローバル変数
並列処理と相性が悪い
if ( (fp = fopen("foobar", "r")) == NULL )
{
if ( errno == EINVAL )
std::cout << "引数が間違っている\n" ;
else if ( errno == ENOMEM )
std::cout << "メモリが足りない\n" ;
}
<例外
この場合、頻繁に発生する可能性があるので使いづらい
optional<T>
値を格納するか、していないクラス
関数側
std::optional<int> div( int x, int y )
{
if ( y != 0 )
return { x / y } ;
else
return {} ;
}
呼び出し元
値がある場合boolに変換される
値はoptional::value()で取り出せる
void f( int x, int y )
{
auto result = div( x, y ) ;
if ( result )
// 値あり
result.value() ;
else
// 値なし
}
値がないのにvalue()を呼び出すと例外
bad_optional_accessがthrowされる
auto result = div( 1, 0 ) ;
result.value ; // 例外
value_or
値がないときにデフォルト値を使う
auto result = div( 1, 0 ) ;
result.value_or(0) ; // 0
any
どんな型でも格納できるクラス
使い方
It Just Works.
std::any a ;
a = 0 ; // int
a = 0.0 ; // double
a = "hello"s ; // std::string
a = std::vector<int>{} ;
どんな型でも代入できる
CopyConstructibleでさえあればいい
テンプレートとか考える必要なし
値の取り出し方
any_cast<T>を使う
値を取り出すには型を指定する必要がある
型を間違えるとbad_any_castがthrowされる
void f( std::any a )
{
auto x = std::any_cast<int>(a) ;
}
anyへのポインターを渡すと結果もポインターになる。
型が違うとnullptrが返る
void f( std::any a )
{
auto p = std::any_cast<int>( &a ) ;
if ( p != nullptr )
*p ; // int
}
string_view
文字列ラッパー
文字列を扱う方法がバラバラだ
ライブラリはそれぞれに対応する必要がある
// null終端配列
void f( const char * str ) ;
// 配列と要素数
void f( const char * str, std::size_t len ) ;
// basic_string
void f( std::string const str ) ;
string_view
文字列の差異を吸収してくれる
文字列は所有しない
使い方
関数側
引数をstring_viewで受けるだけ
void f( std::string_view str )
{
// std::stringと同じ感覚で使える。
} ;
使い方
呼び出し側
string_viewが差異を吸収
// null終端配列
f( str ) ;
// 配列と要素数
f( std::string_view{str, len} ) ;
// basic_string
f( str ) ;
みんな乱択してますか？
乱択とは
ある要素の集合からN個の要素をランダムに選ぶ
みんな知ってるよね？
知らない方に朗報
Donald Knuth著
The Art of Computer Programming Vol.2
アスキードワンゴから発売中
C++17なら簡単
std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
std::size_t const n = 5 ;
std::vector<int> output( n ) ;
std::sample( begin(input), end(input), begin(output), n ) ;
gcdとlcm
追加される
std::gcd( m, n ) ;
std::lcm( m, n ) ;
先ほどのスライドがわからなかった方に朗報
Donald Knuth著
The Art of Computer Programming Vol.1
アスキードワンゴから発売中
source_location
ソースコード情報の取得ライブラリ
ソースコード中の情報がほしい
どうする？
int main(){
if ( !f() )
{
std::cout <<
"in function X,"
" f() returned false"
" in filename Y at line Z." ;
}
}
Cプリプロセッサーマクロを使う
__FILE__, __LINE__, __func__が使える
ただしその場に書かなければならない。
その場に定数として展開される
単なるトークン列の置き換え
使いづらい
ソースコード情報をC++の言語から扱いたい
ちゃんとC++でサポートされていて
コードの中で使えるもの
そこでsource_location
ソースコードの情報を取得できる
オブジェクトとして保持できる
使い方
// この場所のソースコード情報を取得
auto s = std::source_location::current() ;
// 行数
auto line = s.line() ;
// 行頭からの文字数
auto column = s.column() ;
// ファイル名
auto file_name = s.file_name() ;
// 関数名
auto function_name = s.function_name() ;
関数のデフォルト実引数に使った場合
呼び出し元のソースコード情報が得られる
void log
(
std::string msg,
std::source_location s = std::source_location::current()
)
{
// ログを取る
}
int main()
{
log("main executed.") ; // この場所のソースコード情報を取得
}
みんな知ってるよね？
知らない方に朗報
Donald Knuth著
The Art of Computer Programming Vol.2
アスキードワンゴから発売中
Knuth本は乱数の均一分布方法についてまともに解説していない
はっきりいって時代遅れ
texのように
C言語時代の乱数ライブラリ
rand関数
はっきり言ってクソ
乱数の範囲がクソ
rand()の戻り値Nの範囲は
\[0 \leq N \leq RAND\_MAX \]
乱数の範囲を変える方法はない
乱数の生成もクソ
rand()はどのように乱数を生成するのか規定していない
周期が短く、規則性がある、貧弱な実装もある
乱数の生成方法を変える手段もない
使われ方もクソ
実際にほしい乱数は0からRAND_MAXまでの範囲ではない
6面ダイスを実装するなら1から6までの範囲で均一に分布する乱数がほしい
ではどうするのか？
現実に書かれているクソコード
このようなコードを書いてはならない
int dice()
{
return rand()%6 + 1 ;
}
何故か
乱数の生成方法がわからない
値が均一に分布しないため
6面ダイスならば1から6まで6種類の値がそれぞれ等確率で出るはず
C++11の乱数ライブラリ
とても美しい設計
世のプログラマーの乱数需要はだいたい満たしている
<random>
乱数エンジン
(random number engine)
生の乱数ビット列を生成するクラス
線形合同法: minstd_rand, minstd_rand0
メルセンヌツイスター: mt19937, mt19937_64
Ranlux: ranlux24_base, ranlux48_base, ranlux24, ranlux48
KnuthのAlgorithm B: knuth_b
/dev/urandom : random_device
デフォルトの乱数: default_random_engine
使い方
operator ()を呼び出すだけ
std::knuth_b knuth ;
std::cout << knuth() << '\n' ;
ではさっそく
これでは一様に分布しない
int dice()
{
thread_local std::knuth_b knuth ;
return knuth()%6 + 1 ;
}
なぜ一様に分布しないのか
6通りに分布させる必要がある
コンピューターはバイナリで乱数を表現する
最低3bit必要
3 bitは8通りに分布する
\(\frac{6}{8}\)は割り切れない
割り切れるバイナリ乱数はあるのか？
\[2^n \bmod 6 = 0\]
となるn(\(n \geq 1\))を探せばよい
よーし探すぞ
\[ 2^n \bmod 6 = 2^n \bmod {2 \times 3} = 2^{n-1} \bmod 3 \]
2は3で割り切れない
存在しなかったよ
無限のビット列を持ってこい
6通りに均一に分布させる方法
int dice()
{
thread_local std::knuth_b knuth ;
auto rand_3bit = [&]{ return knuth() & 0b111 ; } ;
auto r = rand_3bit() ;
while ( r >= 6 )
{
r = rand_3bit() ;
}
return r + 1 ;
}こんなのいちいち
手で書いていられるか
分布ライブラリ
(distribution)
生の乱数ビット列を望みの分布に加工するクラス
プログラマーは望みの分布の情報だけ書けばよい
整数の一様分布
\(a \geq r \geq b\)の範囲に一様に分布する乱数rを返す
int dice()
{
thread_local std::knuth_b knuth ;
std::uniform_int_distribution<int> dist( 1, 6 ) ;
return d( knuth ) ;
}
浮動小数点数の一様分布
\(a \geq r \gt b \)の範囲の浮動小数点数の乱数rを返す
範囲に注意
値bは返さない
namespace Math {
double random()
{
thread_local std::knuth_b knuth ;
std::uniform_real_distribution dist( 0.0, 1.0 ) ;
return dist( knuth ) ;
}
}
その他の分布
ベルヌーイ分布、二項分布、幾何分布、負の二項分布
ポアソン分布、指数分布、ガンマ分布、ワイブル分布、極値分布
正規分布、対数正規分布、カイ二乗分布、コーシー分布、F分布、t分布
離散分布系: 離散確率分布、区分的定数分布、区分的線形分布
どの分布も目的に応じて役に立つ
ベルヌーイ分布の使い方
ある確率pでtrueを、1 - pの確率でfalseを返す
お題: 宝箱
素人の実装
0から9までの一様分布する整数の乱数を作って
2以下だったらtrueを返す
値の範囲を与える必要がある
比較も自分で書く必要がある
間違いの元
bool open_chest()
{
thread_local std::default_random_engine e ;
std::uniform_int_distribution<int> dist( 0, 9 ) ;
return dist( e ) <= 2 ;
}
C++プログラマーの実装
確率だけ与えればよい
bool open_chest()
{
thread_local std::default_random_engine e ;
std::bernoulli_distribution dist( 0.3 ) ;
return dist( e ) ;
}
結論
C++11でプログラマーはあらゆる需要を満たす
乱数ライブラリを手に入れた
めでたしめでたし
本当にそうか？
エンジンと分布が分かれている設計
実際に使うのは面倒じゃないか？
ベルヌーイだのポアソンだのと言われてわかるか？
1680年
天空に突如として巨大な彗星が出現
昼間でも尾を引いて見えるほどの規模
数カ月間も続いた
一般大衆と坊主は大混乱
神がお怒りに違いない
その中、スイス、バーゼルで
彗星を見つめる一人の若い神学徒がいた
ヤコブ・ベルヌーイ
(1655-1705)
スイスのバーゼル生まれ
父親の意向で神学を学ぶ
後に数学者に転向
ベルヌーイは考える
この天変地異は物理学で説明できるはずだ
神学は己の生涯をかけるに値する学問ではない
己の人生は数学のためにある
ベルヌーイは圧倒的な数学力で頭角を現す
1686年にはバーゼル大学の教授になる
ベルヌーイの疑問
コインを投げて表になる確率は\(\frac{1}{2}\)
6面ダイスを投げて1がでる確率は\(\frac{1}{6}\)
しかし現実のコインやダイスには歪みがある
確率のわからないものに対してはどうすればいいのだ
ベルヌーイの発想
何度も試行した結果を観測し
確率を計測すれば良い
しかし
何度計測すれば
十分に真の確率に近づいたと言えるのだろう
当時はこの問題に使える数学が発明されていなかった
ニュートンとライプニッツ
微積分を発明
嫌がらせのように読みにくい論文
ベルヌーイなら読めた
ベルヌーイ
大数の弱法則を発明
元の論文Ars conjectandiでは
黄金定理
そういう経緯がありまして
2種類の結果のうち
いずれかをランダムで出す
独立した試行を
ベルヌーイ試行と呼ぶようになった
rand()ほど簡単に使えない
使い方を暗記するのは難しい分量
リファレンスを参照しながら書くしかない
初心者には理解することが多すぎて使えず
プログラマーには統計の知識を要求され
統計学の素養ある人間にもコード量が多くて使いづらい
しかし、rand()は問題がある。
プログラマーが本当に欲しかったもの
\[a \geq r \geq b \]
の範囲に一様分布する整数の乱数rを返す
randint( a, b ) ;
使い方
int dice()
{
return std::randint( 1, 6 ) ;
}
randint()
生の欄数列から整数の範囲指定の一様分布までを一気に扱う関数
クラスではないのでオブジェクト管理が不要
randint()のオブジェクト
スレッドごとにdefault_random_engine型のオブジェクトを確保
予測不可能な状態に初期化される
万人に使いやすい乱数ライブラリ
質問
スライド資料