2015-03-25

Ubuntu(Debian)でインストール済みのパッケージ一覧を得る方法

Ubuntuはインストール済みのソフトウェアを一覧表示することすらできない。 | ask.fm/EzoeRyou

すこし調べた結果、

dpkg --get-selections

で、全パッケージのインストールされたものと、インストールされたが除去されたものを得ることができるようだ。除去されたものは文末にdeinstallとついているので、まずはこれをgrepで取り除いたうえで、sedで文末の空白文字とinstallを除去すればよい。

dpkg --get-selections | grep -v deinstall | sed -e "s/[[:space:]]*install$//"

メモ代わりに書いておく。

2015-03-24

メンバー関数へのポインターを返すメンバー関数へのポインターを返すメンバー関数

class Foo;が存在したとして(1)Fooのメンバ関数ポインタ(2)を戻すメンバ関数のポインタが欲しいと思った(なお(1)で戻すメンバ関数もFooのメンバ関数ポインタを戻す)のだが、どうあがいても記述出来ないものだったりするのだろうか?

ようするに、以下のようなことがしたいわけだ。

class Foo
{
public :
    // メンバー関数a
    void a() { }
    // メンバー関数aへのポインターを返すメンバー関数b
    ??? b() { return &Foo::a ; }
    // メンバー関数aへのポインターを返すメンバー関数bへのポインターを返すメンバー関数c
    ??? c() { return &Foo::b ; }
}

ここで、???の部分に戻り値の型を記述しなければならない。

もちろんこれは記述できる。ただしその記述は、C++の規格のバージョンにより難易度が異なる。

C++14

最新の素晴らしい標準規格であるC++14では、この程度の問題は赤子の手をひねるより簡単だ。

C++14に追加された戻り値の型推定は、戻り値の型を書くべき場所にautoキーワードを書くことで、return文のオペランドの式の型を戻り値の型として書いた扱いになる。

// C++14
// 戻り値の型推定
class Foo
{
public :
    // C++14
    void a() { }
    auto b() { return &Foo::a ; }
    auto c() { return &Foo::b ; }
} ;

return文のオペランドの式の型はコンパイル時に決定できるため、当然、戻り値の型もコンパイル時に決定できる。これは具体的な形名を手で書くのと全く同じである。コンパイラーができることはコンパイラーにやらせれば良い。人間様が手をわずらわす必要はない。

C++11

残念ながら、4年も前の大昔の標準規格であるC++11には戻り値の型推定がない。そのため、戻り値の型を手で書かなければならない。ただし、C++11には、戻り値の型を後置する新しい関数記法がある。戻り値の型を書くべき場所にautoキーワードを書き、関数宣言の最後に->を書いて、その後に戻り値の型を書く。

// C++11
// 新しい関数記法
class Foo
{
public :
    void a() { }
    auto b() -> void (Foo::*)() { return &Foo::a ; } 
    auto c() -> auto (Foo::*)() -> void (Foo::*)() { return &Foo::b ;}
} ;

関数aの型は、void (Foo::*)()である。あるいは、auto (Foo::*)() -> voidである。とすると、この型を返す関数は、auto b() -> void (Foo::*)()となるここまでくればもう明白だろう。そう、関数cが返すのは auto (Foo::*)() -> ???で、???に入る戻り値の型はvoid (Foo::*)()だ。

C++03

C++03を今使うものは何か苦行でも行っているとしか思えない。

まず、関数型がある。


void (int)

しかる後に、関数へのポインター型がある。


void (*)(int)

関数ポインターを返す関数は以下のように書ける。


void f(int) { }

void (* g())(int)
{
    return &f ;
}

わかるだろうか。g()が関数gの関数名と仮引数リストだ。void (* ...)(int)の部分が戻り値の型だ。関数型には仮引数リストやその他の修飾などが含まれる。関数の型の文法上、仮引数リストと修飾はg()を囲む形で記述される。

つまりこういうことだ。

void (* // 戻り値の形名
    g() // 関数名と仮引数リスト
)(int) // 戻り値の形名
;

関数gへのポインターを返す関数hは以下のように書ける。


void (* (* h())() )(int)
{
    return &g ;
}

つまりこういうことだ。

void (* // 戻り値の形名
    (*  // 戻り値の形名
        h() // 関数名と仮引数リスト
    )() // 戻り値の形名
)(int)  // 戻り値の形名
;

そして、メンバーへのポインター型がある。

struct X { void f() ; } ;

void (X::* p1)() = &X::f ;

これらを組み合わせると、C++03という化石の様な古代の標準規格でも書くことができる。

// C++03
class Foo
{
public :
    // C++03
    void a() { }
    void (Foo::* b())() { return &Foo::a ; }
    void (Foo::* (Foo::* c())())() { return &Foo::b ;}
} ;

typedefを使うことで、いくらかマシにはできる。

class Foo
{
public :

    typedef void (Foo::* a_ptr) () ;
    typedef a_ptr (Foo::* b_ptr)() ;

    // C++03
    void a() { }
    a_ptr b() { return &Foo::a ; }
    b_ptr c() { return &Foo::b ;}
} ;

結論としては、早くC++14に移行しろということだ。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-03-22

妖怪ハウスで肉会をした

本の虫: 2kgのサーロインブロックが届いたので21日の夜はステーキ会

妖怪ハウスの住所の私宛に、突然2kgのサーロインブロックが届けられた。真空パックの冷蔵品で、何と賞味期限が週末までだ。これはまずい。なんとか週末に使ってしまわねばならない。

しかし、物は2kgの牛肉の塊である。私はそこまで大量の肉を食べたいとは思わない。こんなに急で人が集まるかわからないが、とにかく週末に人を呼んで肉会でも行うしかないだろう。

かくして、21日の夜に妖怪ハウスで肉会が計画された。

さて、2kgの牛肉をどうやって調理するべきだろうか。やはり、無難にステーキにするべきだろうか。ローストビーフにするという意見も出た。妖怪ハウスにはガスオーブンがあり、ローストビーフは調理可能だ。シチューにするという意見も出た。しかし、せっかくの巨大な肉の塊なのだから、やはりステーキにするべきだろうと結論した。

さて、サーロインブロックをステーキにするには、まず脂を切り取り、塩をすり込んで、包丁で軽く切れ目を入れた後、コショウを振ってフライパンで焼く。最初は強火で、ひっくり返して弱火で焼くとよいらしい。今回はバターも使った。

ステーキは、想定していたより手間も時間もかからなかった。これがカレーとなると、まずタマネギを5,6個みじん切りにするところからはじめなければならないのだから、段違いの手軽さだ。

また、妖怪ハウスにはガスオーブンが設置されているので、付け合せに野菜を焼いてみた。人参とタマネギとピーマンをオリーブオイルをかけて焼くだけだ。人参は最も調理に時間がかかるので先に焼く。人参を皮付きのまま数センチの厚みに切り、オリーブオイルをかけてすこし焼く。その後にタマネギとピーマンも入れて焼く。何の味付けもしなかったが、十分にうまかった。

さて、ステーキの味はなかなかのもので、客の食欲も旺盛であり、2kgの肉塊が一瞬にしてなくなってしまった。2kgでは足りなすぎる。

なかなか盛況であったので、今度は自前で肉を調達して、また近いうちに肉会をやりたいものだ。

2015-03-18

2kgのサーロインブロックが届いたので21日の夜はステーキ会

妖怪ハウスに私宛で以下のような品物が送りつけられた。

[The Meat Guy] サーロイン 2kg ブロック

箱を開けてみると、2kgのサーロインブロック、真空パックの冷蔵品だ。賞味期限を見ると、なんと3月の23日、週末までではないか。丸鶏の冷凍品が送られてきた時は、何ヶ月も期限があったので、しばらく放置した後にスタッフドチキンを作ったが、これには猶予がない。週末には調理しなければならない。

すこし考えたが、やはりなにも考えずにステーキにするのが一番だと結論した。

そんなわけで、3月21日土曜日の夜は、ステーキを焼く会を開こうと思う。ステーキを焼くのは初めてだが、食べたい人は妖怪ハウスまで来るといい。

2015-03-16

金の使い道が分からない

「毎日のように飲みに行っている」と男は我々に語った。我々は土曜日を丸一日エンジニアボードゲーム会@本郷に費やした後、会場の近くの中華料理屋で食事をしているのであった。

「毎日のように飲みに行っている。だいたい終電を逃してタクシーで帰る」

よく金が続くものだ。

「結局、タクシー代を考えると、都内に住んだほうがいいので、都内に住んでいる。しかし、家など寝るためにあるようなものなので、いらないのではないか。最近は荷物をどんどん減らしている」

「貯金がないし、たまらない。どうやって貯金をしたらいいのだろう」

贅沢な悩みだ。私と、その場にいたある女は、金の使いどころがなくて貯金額のみむなしく増えていく一方だというのに。

毎月の給与所得というものが発生するようになって早一年、最初こそ、東京に身ひとつで引っ越してきたばかりであり、色々と物入りであったが、基本的な日用品を買い揃えてしまえば、後はなにも要らなくなってしまった。一体、世間の人は金をなにに使っているのだろうか。

酒に金を使う種類の人間がいる。外で飲むと高くつく。これは、飲み屋には酒と食材の他にも、場所や建物や人員が必要なためである。また、終電を逃して家に帰りたければタクシー代もかかる。私は飲み歩きたいとは思わない。まず、飲み屋というものは大抵がタバコという薬物に中毒している救いようのない人間の多い場所であり、そのような場所に身を置きたくはない。また、酒も、相手が入ればこそ飲んでも楽しいが、一人寂しく飲みたいとは思わない。また、東京の飯はまずいので、食べ歩きたいとも思わない。

旅はどうか。旅には金がかかる。新幹線や飛行機はそれなりの値段であるし、宿も高い。私は旅に出たいとは、今のところ思っていない。特に見たい名所もないし、温泉というものにも興味がない。広い湯船につかりたければ、銭湯に行けばいい。

車やバイクにも興味がない。

ビデオゲームはどうか。私にとって、ビデオゲームとはマウスとキーボードで行うものである。当然、十分な性能のCPUとGPUとメモリ容量と高速なストレージを備えたコンピューターでなければならぬ。これを用意するには、数十万円かかる。それでもたったの数十万円だ。一度PCを組んでしまえば、一年以上使えるので、やはり月あたり数万円の出費でしかない。それに、今のところ、あまりおもしろそうなゲームがないため、数年はビデオゲームを控えるつもりである。

ボードゲームはどうか。ボードゲームは高い。僅かなコンポーネントの、実質ルールを書いた紙切れだけのようなボードゲームが数千円する。とはいえ、どんなに高いものでも、せいぜい一万円程度であり、一度買ってしまえば何年も遊べる。それを考えれば、それほど高くはない。MTGや遊戯王のような、高くつくゲームもあるが、私はデッキ構築ゲームにはそれほど興味がない。

最近は、ボルダリングをしている。ボルダリングは高くつくかというと、それほどでもない。ボルダリングジムの使用料は、一回あたり二千円弱だからだ。ボルダリング用の靴は高いが、一年以上使えることを考えると、やはりそれほどでもない。

妻子でもいれば色々と物入りなのかもしれぬが、あいにくと結婚とは縁遠いようだ。

最近、月一で江添ボドゲ会を開いているが、菓子や飲み物やビールを用意したり、カレーを5リットル作ったりするのに、それなりに金がかかる。とはいえそれほどでもない。

ただ、妖怪ハウスの賃貸契約が3年なので、来年以降存在しているかどうか怪しい。ボドゲ会のために、都内に広いリビングを備えた物件を借りるのにはそれなりに金がかかる。とりあえずはまだ先の話だ。

そういえば、このエンジニアボードゲーム会の後の食事の席で、コミット申請書とかコンパイル申請書などと言った闇の話を聞いたのだが、それはまたの機会に。

2015-03-11

最近のC++17事情

C++1z、あるいはC++17とも呼ばれている次のC++規格の、最近の事情はどうなっているのか。すでにドラフトに取り入れられた機能もあるので、現在の最新の状況を見ていこう。もうすでに紹介したものも含まれているが、おさらいとしてみていく。また、ここで解説する新機能は、いずれもすでにドラフト入りしているが、正式に規格制定される際に変わる可能性がある。

N3928: メッセージなしstatic_assert

C++11で入ったstatic_assertは、必ず文字列リテラルを書かなければならなかった。

static_assert( INT_MAX >= 2147483647, "This code assumes at least 32-bit int." ) ;
static_assert( true == true, "You're compiler is fundamentally wrong." ) ;

しかし、この文字列リテラルの使われ方は規定されていない。特にメッセージを書きたくなくても、文字列リテラルは、文法上必ず書かなくてはならない。


static_cast( std::numeric_limits<double>::is_iec559, "" ) ;

C++1zでは、文字列リテラルを書かなくてもよくなる。


static_cast( false ) ;

N4086: Removing trigraphs??!

トライグラフが取り除かれる。

// C++14までは#
// C++1zでは??=
std::cout << "??=" ;

N4051: Allow typename in a template template parameter

テンプレートテンプレートパラメーターにtypenameキーワードが使えるようになる。

template <
    template < typename T >
    class U
>
struct X ;

が、

template <
    template < typename T >
    typename U
>
struct X ;

とも書けるようになる。

N3922: New Rules for auto deduction from braced-init-list.

auto指定子で直接初期化でリスト初期化を書いた場合の挙動を変更する。C++14で合法なコードが違法になる珍しいケースだ。


auto a{ 1, 2, 3 } ;

このコードは、C++14までは合法なコードであり、decltype(a)は、std::initializer_list<int>となる。

C++1zでは、このコードは違法である。auto指定子で直接初期化でリスト初期化の場合は、単一のinitializer-clauseしか書くことができなくなった。

// aの型はint
auto a{ 1 } ;

N4295: Fold expressions

今回紹介する新機能の中で、一番面白い機能がこれだ。パラメーターパックに対するfold式がC++に入る。

パラメーターパック全てに対して演算子を適用したい場面がある。

// 与えた実引数にoperator +を適用して合計値を返す関数テンプレートsum
sum( 1, 2, 3 ) ; // 6
sum( 1, 2, 3, 4 ) ; // 10

このようなsumをC++14で書くと以下のようになる。

template < typename T >
T sum( T && t )
{
    return t ;
}

template < typename T, typename ... Args >
T sum( T && t, Args && ... args )
{
    return t + sum( std::forward<Args>(args)... ) ;
}

やりたいことは、パラメーターパックのそれぞれの実引数にoperator +を適用したいだけなのに、やたらと面倒なコードだ。

そこで、C++1zには、パラメーターパックに対するfold式が入る。

template < typename ... Args >
auto sum( Args && ... args )
{
    return ( args + ... ) ;
}

これは、sum( 1, 2, 3, )に対して、 (((1 + 2) + 3) + 4)のようにleft foldされる。

逆に以下のように書けば、

template < typename ... Args >
auto sum( Args && ... args )
{
    return ( ... + args ) ;
}

(1 + ( 2 + ( 3 + 4 ) ) )のように、right foldされる。

fold式は、必ず括弧で囲まなければならない。


( pack + ... ) ; // OK
pack + ... ; // エラー、括弧で囲まれていない

fold式には、unary(単項) foldとbinary(二項) foldがある。binary foldは、(e1 op1 ... op2 e2)という形を取る。op1とop2は同じfold演算子でなければならず、e1とe2は、どちらか片方だけがパラメーターパックでなければならない。e2がパラメーターパックであった場合はleft fold、e1がパラメーターパックであった場合はright foldとなる。


template < typename ... Types >
void f( Types ... args )
{
    ( 1 + ... + args ) ; // binary left fold
    ( args + ... + 1 ) ; // binary right fold
}

それぞれ、(( ( 1 + args0 ) + args1) + ... + argsN )と、args0 + ( args1 + ( ... argsN + 1) )のようにパック展開される。

N4267: Adding u8 character literals

UTF-8文字リテラルの追加。プレフィクスu8の文字リテラルで、UTF-8のコード単位一つで表現可能な文字が記述できる。


char a = u8'a' ; // OK
char b = u8'あ' ; // エラー、UTF-8で符号化するにはコード単位が3個必要。

N4230: Nested namespace definition (revision 2)

名前空間の宣言をネストできるようになる。

namepsace A {
    namespace B {
        namespace C {
            // ...
        }
    }
}

のようなコードが、

namespace A::B::C {
// ...
}

のように書ける。

N4266: Attributes for namespaces and enumerators

名前空間とenumeratorにattributeが記述できるようになる。C++14までは、文法上の制約で記述することができなかった。これにより、名前空間やenumeratorにdeprecatedが指定できる。記述する場所は、名前空間ならnamespaceキーワードの前、識別子の後、enumeratorならば、識別子の後だ。


namespace [[deprecated("This namespace is deprecated.")]] libv1 { }

enum class E { value [[deprecated("This enumerator is deprecated.")]] = 0 ; }

N4268: Allow constant evaluation for all non-type template arguments

すべての非型テンプレート実引数でコンパイル時評価を可能にするように制限を緩和する。

以下のコードは違法である。

template<int *p> struct A {};
int n;
A<&n> a; // ok

constexpr int *p() { return &n; }
A<p()> b; // エラー

理由は、定数として渡せるポインターはnullだけだからである。

constexpr int *p() { return nullptr ; }
A<p()> b; // OK

constexprがある今、この制約は時代にそぐわない。そこで、非型テンプレート実引数に、任意の定数式を渡せるように制限を緩和された。つまり、上のコードは違法ではなくなる。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

江添ボドゲ会3月の様子

江添ボドゲ会3月が開催された。

当日は16人ほどのボドゲ好きの男が集まり、なかなかできない大人数ボドゲをした。

筆者は、ソビエトロシア・・・もとい妖精の国の原子力潜水艦を火災や漏水から協力して救うゲーム、レッドノーベンバーを救えを人から借りて用意したが、展開しただけでやらなかった。このゲームは火災を消すために日に飛び込む必要があり、そのためにはウォッカをひとあおりしなければならないという、とても面白い設定のゲームなのだが、残念ながら肝心のゲームの設計が悪く、同じく協力ゲームであるパンデミックやフラッシュポイントに面白さで劣るゲームとなっている。

なお、前日は花金を満喫して会社で徹夜でボドゲをしており、帰ってから、カレーを作って、またボドゲをして、日曜日も残った面子でやはりボドゲをした。実にボドゲ三昧の週末であった。

ドワンゴでは、ボドゲは社内で昼からやっているのだが、なかなかそういう環境にいない人にはボドゲを日常的にするのは難しいようだ。

そういえば、火曜日にギャモンボードが妖怪ハウスに届いた。

2015-03-09

ChromiumがLinuxカーネル3.17より前のサポートを打ち切り

Chrome/Chromium To Require Newer Version Of Linux Kernel - Phoronix

ChromiumがLinuxカーネル3.17以前のサポートを打ち切るようだ。

というのは釣りタイトルだが、Linuxカーネル3.16までで、最新のChromiumを使うと、ブラウザー拡張がインストールできないという問題がある。この理由は、Linuxカーネルのサンドボックス機能であるseccompに最近入ったTSYNC(SECCOMP_FILTER_FLAG_TSYNC)をChromiumが使っているためだ。

興味深いは、LinuxカーネルにTSYNCをいれたのは、Chromium開発者で今はGoogle社員でもあるKees Cookだ。Ubuntuの12.04と14.10のLinuxカーネルには、TSYNCをbackportするパッチがあたっているが、これもKees Cookが用意したらしい。

これは適切に情報共有されなかったらしく、かやの外の人間は、最新のChromiumが動かなくなった理由を、手探りで解明する必要に迫られた。

Issue 758063005: Linux sandbox: report TSYNC status in chrome://sandbox - Code Review

さて、ChromiumがLinuxカーネル3.17以上を必要とするようになったというバグ報告は、WontFixとされてしまった。なぜならば、「これは技術的にはregressionではあるが、ユーザーにはカーネルのアップデートという、十分にリーズナブルなworkaroundが存在するから」だそうだ。はたして、本当に十分にリーズナブルだろうか。

Linuxカーネル3.16というのは、去年リリースされたばかりのだいぶ新しいバージョンである。3.17以上を要求するのはあまりにも難しい。3.17以前のカーネルでChromiumを使うには、TSYNCのbackportが必要だが、少なくともDebianは、backportに消極的のようだ。

Debian 8/jessie - SECCOMP_FILTER_FLAG_TSYNC

2015-03-08

毎月第一週の土曜日は江添ボドゲ会

4月4日に妖怪ハウスでボードゲーム会を開催する。

江添ボドゲ会@4月 - connpass

毎月第一土曜日に開催する定例会にしていきたいところだ。

2015-02-27

range-based forで固定回ループ

本の虫: Dwangoプログラミングコンテストの感想で固定回のループがあればいいと書いたが、range-based forにそういうイテレーターを与えてやればいいのではないかと気がついた。つまり、こういうことだ。

class counter_iterator
{

    std::size_t i ;

public :
    

    counter_iterator() : i(0) { }
    counter_iterator( std::size_t n ) : i(n) { }

    bool operator == ( const counter_iterator & rhs ) const
    {
        return i == rhs.i ;
    }

    bool operator != ( const counter_iterator & rhs ) const
    {
        return i != rhs.i ;
    }

    std::size_t & operator * ( )
    {
        return i ;
    }

    counter_iterator & operator ++ ()
    {
        ++i ;
        return *this ;
    } 
} ;

class nth_loop
{
private :
    std::size_t i ;

public :
    nth_loop( std::size_t n ) : i(n) { }

    counter_iterator begin() const
    {
        return counter_iterator() ;
    }

    counter_iterator end() const
    {
        return counter_iterator(i) ;
    }
} ;

nth_loop rep( std::size_t n )
{
    return nth_loop( n ) ;
}
 
int main()
{
    for ( auto elem : rep(10) )
    {
        std::cout << elem << std::endl ;
    }
}

とはいえ、for ( elem : 10 )と書きたいところだ。

追記:ユーザー定義リテラルを使う方法を思いついた。unsigned long long intに書き変えるのは省略。

nth_loop operator "" _( unsigned long long int n )
{
    return nth_loop( n ) ;
}

int main()
{
    for ( auto i : 10_ )
    {
        std::cout << i << std::endl ;
    }
}

だいぶ簡略化された。

なお、Boostに同等のライブラリ、boost::iragenがある。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-26

C++11/14の採用が進んでいないのはだいたいRHELのせい

C++11やC++14は、すでにGCCやClangの最新の安定版で実用的に使えるようになっているが、なかなか現場で広く使われるようにはなっていないように見える。これはなぜか。やはり教育者の不足か。参考書がないのか。それもあるかもしれないが、最大の理由がある。

RHELが悪い。

RHEL 6のGCCのバージョンは4.4である。これは。C++11をまともにサポートしていない。GCC 4.4当時といえば、まだC++11がC++0xと呼ばれていた時代で、一部機能を当時のドラフトに基づいて実験的実装をしていた。正式な規格とはだいぶ異なっているだろうし、不具合もたくさんあるものと思われる。

次のRHELのバージョンは7であるが、これにはGCC 4.8が入るものと思われる。しかし、すでにGCCの安定版は4.9だ。GCC 4.8もC++11実装に不具合が色々あってあまりお勧めできない。これがあと何年も使われるのかと思うとげんなりする。

結局、LTSというのは本当に有益なのだろうかという疑問が湧いてきた。挙動が変わらないとはいっても、不具合もそのままなので、そのコストは支払わなければならない。そして、いずれはソフトウェアをアップデートせねばならず。5年10年もの積みかさなかった挙動の変更を一気に修正しなければならない。

とはいえ、C++の簡単な入門書は必要だと思うので、簡単に読めるC++の解説を今書いている。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-24

goのgcコンパイラーがC実装を除去

all: merge dev.cc (a91c2e0) into master · b986f3e · golang/go

Go言語のGoogleが実装するコンパイラーであるgcから、Cコードが取り除かれた。

今後のgc実装は、goによるセルフホストのみになる。

ブートストラップ計画は至って常識的なもので、前のリリースは次のリリースをコンパイル可能な状態を保つことで、ブートストラップ可能な状態を保つのだという。

Go 1.3+ Compiler Overhaul - Google Docs

go言語の実装としてのgcは、libcにすら依存しておらず、ツールチェインがすべて既存のものにたよらず自前になっている。Googleの本気度を感じる。

ドワンゴ広告

この記事はC++に関係ないがドワンゴ勤務中に書かれた。ドワンゴではGoも使っているようだ。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

xkcd: 基本の力

xkcd: Fundamental Forces

粒子間における基本的な力が4つある:

(1) 重力、これは次のような逆2乗の法則に従う。

\(F_{gravity}=G\frac{M_{1}M_{2}}{d^2}\)

なるほど・・・

(2) 電磁気力、これは次のような逆2乗の法則に従う。

\(F_{static}=K_{e}\frac{q_{1}q_{2}}{d^2}\)

それからマクスウェルの方程式とか。

それから何だって?

(3) 強い核力、これが従うのは・・・えと、えーと・・・これは陽子と中性子を結びつけているんだ。

なるほど

強いんだよ。

そして、(4) 弱い力、これは[ペラペラペラペラ] 放射性減衰 [ペラペラペラペラ]

それじゃ説明になっていないじゃないか。単に放射

これが4つの基本的な力なんだ!

title要素: 「これら4つの力のうち、ひとつだけよくわかっていないのがある」、「弱いやつか強いやつ?」、「重力」

人類は重力が一番わかっていないそうだ。

エンジニアボードゲーム会に参加してきた

去る週末、エンジニアボードゲーム会に参加してきた。

【初心者歓迎】第1回 エンジニアボードゲーム会@本郷【今日は一日ボドゲ三昧】 - connpass

当日はなかなか広い快適な場所で、用意された大量のボードゲームを遊んできた。

中でも興味深かったのが、今話題の枯山水だ。コンポーネントが手作りで生産数が少なく、供給が需要に追いついていないため、にわかに市場価格が上がっている。コンポーネントに凝ったものを使うべきではない教訓になるゲームだが、その出来はどうなのであろうか。

私は残念ながら枯山水をプレイしなかったのだが、プレイした人によると、「いやぁ、徳がお高いですね」とか、「徳を奪います」などといった会話がでてくるシュールなゲームらしい。

会話がシュールなゲームといえば、心臓発作もなかなかのもので、

「あれ、働かないんですか?」
「いやぁ、鬱で働けないんですよ」

「ちょっと痩せないと」
「チョット今は血圧が危険で」
「血糖値がやばい」

などと言った会話が行われる。

ボドゲ会といえば、3月7日に筆者の住んでいる妖怪ハウスでボドゲ会を行おうと思っている。

本の虫: 江添ボドゲ会@3月

江添ボドゲ会@3月 - connpass

江添ボドゲ会@3月

3月7日の土曜日に妖怪ハウスでボドゲ会を開くことにした。

月一で第一週の土曜日に定例化していきたい。

江添ボドゲ会@3月 - connpass

場所

中野区野方5-30-13 ヴィラアテネ401、コンクリート打ちっぱなしの建物の4階。

当日場所が分からなければ、@EzoeRyouかboostcpp@gmail.comまで連絡。

2015-02-23

C++標準 2015-02 mid-meetingのレビュー: N4370-N4380

N4370: Networking Library Proposal (Revision 4)

Boost.Asioを土台にしたネットワークライブラリの提案。

N4371: Minimal incomplete type support for standard containers, revision 2

一部のSTLのコンテナーの要素型に不完全型をサポートする提案。

以下のようなコードが書けるようになる。

struct Entry
{
    std::vector<Entry> v ;
} ;

クラスは、定義の終了である}を持って、完全型になる。クラス定義内ではまだ不完全型である。したがって、vectorにテンプレート実引数に渡す時点では、まだ不完全型なのだ。これをサポートするかどうかは、これまで規格上は未規定だったのだが、この提案では、vector, list, forward_listに限ってはサポートするとしている。

これ以外のコンテナーについては、更に議論をして緩和していくという。

N4372: A Proposal to Add a Const-Propagating Wrapper to the Standard Library

クラスのデータメンバーがポインターの場合、ポインターの参照先は、constメンバー関数からでも変更できる。


struct A
{
    void f() ;
    void f() const ;
} ;

class B
{
    std::unique_ptr<A> ptr ;

public :
    // コンストラクターやデストラクターなど

    void f()
    {
        ptr->f() ; // 非const版が呼ばれる
    }

    void f( ) const
    {
       ptr->f() ; // 非const版が呼ばれる
    }
} ;

これは完全に規格通りの挙動だが、意味的にはここでconst版が呼ばれて欲しい。そこで、そのようなconst性を伝播させるライブラリ、propagate_constを提案している。


class B
{
    std::propagate_const< std::unique_ptr<A> > ptr ;

public :
    void f()
    {
        ptr->f() ; // 非const版が呼ばれる
    }

    void f( ) const
    {
       ptr->f() ; // const版が呼ばれる
    }
} ;

N4373: Atomic View

非atomicオブジェクトをatomic操作できるラッパーライブラリ、atomic_viewの提案。

// 並列実行される何らかのタスク
void spawn_task( std::experimental::atomic_array_view<int> v ) ;

void f( int * ptr, std::size_t size )
{
    // 非atomic操作
    std::for_each( ptr, ptr + size, []( auto & elem ) { elem = 0 ; } ) ;

    {
        std::experimental::atomic_array_view<int> v( ptr, size ) ;

        // vを経由してしか操作できない。

        spawn_task( v ) ;
        spawn_task( v ) ;
        spawn_task( v ) ;
    // vが破棄される
    }

    // これ以降、配列に直接操作が可能
}

atomic_array_view<T>は、既存の非アトミック型の配列をラップして、アトミックな操作ができるようにしてくれる。atomic_array_viewでラップする前に起こったアクセスは、atomic_array_viewのコンストラクターの実行が完了する前に起こる(happens before)。

atomic_array_viewのオブジェクトが存在する間は、配列に直接アクセスすることはできず、atomic_array_viewのオブジェクトを通してしかアクセスできない。

atomic_array_viewはコピーすることができる。その際には、アトミック操作を実現するためのロックなどのリソースが、もしあれば、共有される。最後のatomic_array_viewのオブジェクトが破棄された後に、元の配列は直接アクセスすることが出来るようになる。

配列ではなく単一のオブジェクトに対するarray_viewである、atomic_concurrenty_view<T>も存在する。

これらのatomic_viewには、二つの利用方法が想定されている。ひとつには、High Performance Computing用途で、巨大な配列を、まず競合しない方法で初期化し、次に並列に変更し、その後に競合しない方法で読み書きを行うような処理に使える。

もうひとつは、既存のコードで非atomicな型を使っていて、atomic<T>に置き換えるコストが現実的ではない場合に使うことができる。

N4374: Linux-Kernel Memory Model

これまで、Linuxカーネルのメモリーモデルは、memory-varriers.txtatomic_ops.txtにラフにドキュメント化されていた。これはLinuxカーネルの開発には用を為すが、厳密な規格を書き起こすには不適切である。N4374は、初めてLinuxカーネルのメモリーモデルを厳密にドキュメントする試みである。

Linuxカーネルのメモリーモデルがまとめられていて、C++との対応も考察されている。Linuxカーネルで使われている既存のメモリーモデルをC++コミュニティに紹介することで、今後の規格化に役立てる意図がある。

N4375: Out-of-Thin-Air Execution is Vacuous

オブジェクトへの並列アクセスによる競合により、本来現れるはずのない値が現れてしまう、Out Of Thin Air(OOTA) Effectの具体的な例と、それに酔ってもたらされる害悪を紹介した論文。

N4376: Use Cases for Thread-Local Storage

TLSは20年以上も使われている実績ある機能ではあるが、最近、SIMD畑とGPGPU畑の連中が、TLSの有用性に疑問を持っていて、会議でもそう主張している。この論文はTLSの有用性を解説している。

ただし、SIMDやGPGPUによる軽いスレッド風並列処理を行う際に、TLSは共有する実装がもっとも効率的であり、悩ましいところで、論文ではそこの考察も行っている。

[PDF] N4377: C++ Extensions for Concepts PDTS

Concept Liteのドラフト

N4378: Language Support for Contract Assertions

契約プログラミングのためのcontract_assertライブラリ。

contract_assertには、3種類のassertion levelが設定されている。min, on, maxだ。minは最小限、maxは最大限のレベルになっている。これ以外にも、完全に無効にするoffがある。assertion levelは、何らかの実装依存の方法で設定するようだ。レベルは、コンパイル時にpredefine macroで取得することができる。

#ifdef contract_assertion_level_max
#endif

これは、従来のNDEBUGのようなマクロに相当する。

contract_assertには、contract_assert_min/contract_assert_on/contract_assert_maxがある。それぞれ、レベルに対応していて、そのレベル以上の場合にチェックが走る。contract_assertマクロは、contract_assert_onと同じだ。

void * contract_memcpy( void * dest, const void * src, size_t n )
{
    // 軽い契約チェック
    // nullポインターではないかどうか調べる
    contract_assert( dest != nullptr ) ;
    contract_assert( src != nullptr ) ;

    // 重たい契約チェック
    // 環境依存の方法を使って有効なメモリ領域かどうかを調べる
    contract_assert_max( platform_specific::is_valid_memory_area( dest, n ) ) ;
    contract_assert_max( platform_specific::is_valid_memory_area( src, n ) ) ;

    char * d = static_cast<char *>(dest) ;
    char const * s = static_cast<char const *>(src) ;
    char const * const end = s + n ;

    for ( ; s != end ; ++s, ++d )
    {
        *d = *s ;
    }

    // 重たい契約チェック
    // 宇宙線やハードウェア破損などの可能性を考慮
    contract_assert_max( std::memcmp( dest, src, n ) == 0 ) ;

    return dest ;
}

契約違反時には、ハンドラーが呼ばれる。このハンドラーは呼び出し元にreturnしてはならない。デフォルトのハンドラーは、std::abortを呼び出す。set_contract_violation_handlerでカスタムハンドラーを設定できる。


int main()
{
    std::experimental::set_contract_violation_handler(
        []( std::experimental::contract_violation_info & info )
        {
// assertionレベルを表すenum値
// enum class contract_assertion_level { min, on, max };
            auto level = info.level ;

// contract_assertの式の文字列
// contract_assert( is_okay(x) ) ;の場合、"is_oaky(x)"
// phase 3なので、プリプロセッサーマクロ展開前の文字列が得られる
// 複数の連続した空白文字はスペース文字ひとつになる。
            std::cout << info.expression_text << '\n' ;

// contract_assertが存在するソースファイルの__FILE__
            std::cout << info.filename << '\n' ;

// contract_assertが存在するソースファイルの__LINE__に相当
            std::cout << info.line_number << '\n' ;

            // ハンドラーは呼び出し元に戻ってはならない
            std::abort() ;

        } ) ;

}

contract_violation_infoクラスのメンバーの中でも、expression_textが興味深い。Phase of translationのphase 3の文字列なので、マクロも展開されない。また、複数の連続した空白文字(スペース、改行、水平タブ、垂直タブ、ラインフィード)は、スペースひとつに変換される。

#define identity(x) x

// "identity ( x ) "
contract_assert(
    identity
    (
        x
    )
) ;

C++としてはだいぶ頑張ったようだ。

[PDFうざい] N4379: FAQ about N4378, Language Support for Contract Assertions

contract_assertに対するFAQ集。

興味深いものを紹介すると・・・

contract_assertはコンパイル時チェックやデッドコード除去、最適化、静的解析用途にも使えるように設計されている。

どうやってデッドコード除去を行うのか?

コンパイラーにとってasssert式とシンボルを関連付けるのはお手の物だ。

なぜ関数本体でしか使えないのか?

それ以上のものは、全く経験のないまったく新しい文法や機能を必要とする。そこまで冒険したくない。

N4380: Constant View: A proposal for a std::as_const helper function template

<utility>にstd::as_constの提案。

int main()
{
    std::string text("text") ;
    std::string const & const_ref = std::as_const(text) ;

    // std::string::const_iterator
    auto iter = std::as_const(text).begin() ;
}

as_const(obj)は、以下のように実装できる

template< typename T >
inline typename std::add_const< T >::type &
as_const( T &t ) noexcept
{
    return t;
}

as_constの提案理由としては、const版と非const版の同名のメンバー関数がある場合、const版のメンバー関数を明示的に呼び出すことだ。


int main()
{
    std::string s ;
    // std::string::iterator
    auto iter1 = s.begin() ;
    // std::string::const_iterator
    auto iter2 = std::as_const(s).begin() 
}

cbeginはこの目的のためにあるが、すべてのクラスに存在するわけではない。const版のメンバー関数を明示的に呼ぶ際に、const_cast< std::add_const< decltype( object ) >::type & >( object )と書くより楽になる。

xvalueやprvalueをサポートすることに意義があるかという点について、議論が分かれている。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

どうやら、ドワンゴ社内に競技プログラミング部なるものができるそうだ。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-21

ボルダリング

去年の冬から、週一でボルダリングをしている。かねてからブログに書こうと思っていたが、もう少し経験をためてからと考えるうちに、あまりブログに書くほどの新鮮さも薄れて、特に何も書くことはなかった。この文章も、特に強く書きたいとは思わないまま、無理やり文章をひねり出している。

ボルダリングを始めた時は、ひどい筋肉痛に悩まされたものだ。特に最初にボルダリングを行った後は悲惨で、腕と指に全く力が入らず、頭を洗ったり、ジッパーの上げ下ろしに苦労したりした。しかも筋肉痛が4日ほど続いたものだ。

ところが、週一でジムに通って慣れてくると、筋肉痛は次第にマシになり、とうとう気にならないレベルにまでなってしまった。

当初は、一時間もすると腕が疲れて体が持ち上がらなくなってしまったのだが、今では一時間たっても、まだ体を持ちあげられるまでに腕の力が残っているようになった。

問題は、握力だ。握力は依然として一時間ほどで限界に達してしまう。握力の持久力はどうやって鍛えればいいのだろうか。

ボルダリングのジムは、主に秋葉原のB-PUMPに行っている。別のところにもいくつか行ったが、ドワンゴにはボルダリング部があり、部の活動として、たいてい水曜日の21時頃から始めている。

さて、気のせいかもしれないが、ボルダリングを始めてから、シャツの腕周りと胸回りが、少しきつくなったような気がする。

やはり、無理矢理にひねり出した文章はぱっとしないし繋がりもない。

2015-02-19

C++標準 2015-02 mid-meetingのレビュー: N4360-N4369

ISO/IEC JTC1/SC22/WG21 - Papers 2015の紹介を進めていく。

[PDF] N4360: Delayed Evaluation Parameters

遅延評価引数の提案。この提案は具体的な文法の提案にまでは踏み込んでいない。

遅延評価引数とは、呼び出し元が関数の実引数に渡した式がその場で評価されず、関数内で最初に値が使われた時に評価される機能である。

// とても遅い関数
int f() ; 

void g( int x )
{
    bool b ;
    std::cin >> b ;
    if ( b )
        std::cout << x << std::endl ;
    else
        std::cout << 0 << std::endl ;
}

int main()
{
    g( f() + 1 ) ;
}

関数fは、値を返すのに、とてつもない重い計算を行うものとする。しかし、その値は、入力次第によっては必要がないものである。関数gに引数として与える式の評価は、実際に使う必要があるときまで遅延させたい。

これを現行のC++でやろうとすると、関数オブジェクトを引数にとって関数呼び出しするようなコードになる。

// とても遅い関数
int f() ; 

template < typename LazyInt >
void g( LazyInt x )
{
    bool b ;
    std::cin >> b ;
    if ( b )
        std::cout << x() << std::endl ;
    else
        std::cout << 0 << std::endl ;
}

int main()
{
    g( [](){ return f() + 1 ; } ) ;
}

しかし、このようなコードを手で書くのは面倒だ。このような遅延評価引数機能をコア言語に追加してはどうか。

論文は設計方針として、いくつかの提案をしている。

引数はキャッシュ風に一度だけ評価されるべきか、インスタンス風にそのつど評価されるべきか - 一度だけ評価されるべき

引数はいつ評価されるべきか - 値が必要とされるとき。値へのポインターやリファレンスを取る場合も含む。sizeof, typeid, alignas, decltypeでは評価されない。

遅延評価引数がさらに別の遅延評価引数の中に入れられた場合はどうするか - 遅延評価引数は自動的に評価されるべきではない。

遅延評価引数はstd::functionのようにラッパーであるべきか、lambdaのように別のオブジェクトであるべきか - ラッパーのようであるべき

文法は?

三案ある。

  1. シンボル。これはシンボルは型の一部であるという既存の手法と異なる。
  2. lazyのような新しいキーワード。新しいキーワードは既存のコードを壊す恐れがある。既存の文法を折り合う文脈依存キーワードもない
  3. 既存のキーワードを再利用する。inlineがよさそうだ

規格準拠の実装は、観測可能な副作用がない場合、遅延評価引数をthunkを使わずに実行することができる。

[PDf] N4361: Concepts Lite TS

タイトル通り、Concept LiteのTSドラフト。

軽量コンセプトは、SFINAEに毛が生えたような設計になっている。

N4362: WG21 2015-01 Skillman Minutes

2015年1月26-27日にSkilmanで行われた会議の議事録。

[PDf] N4365: Responses to National Body Comments, ISO/IEC PDTS 19568, C++ Extensions for Library Fundamentals

Library Fundamentals TSに対するNBコメントへの回答。

日本からはmake_applyを追加すべきだというコメントを送ったが、合意がないとして却下された。提案論文を出せとのことだ。

N4366: LWG 2228: Missing SFINAE rule in unique_ptr templated assignment

unique_ptrのdeleterの型に互換性のない場合でも、オーバーロード解決の候補に上がってしまうことの修正。

以下のコードを修正する。

#include <memory>
#include <type_traits>

struct do_nothing
{
    template <class T>
    void operator()(T*) {}
};

int
main()
{
    int i = 0;
    std::unique_ptr<int, do_nothing> p1(&i);
    std::unique_ptr<int> p2;

    // OK
    static_assert(std::is_assignable<decltype(p2), decltype(p1)>::value, "");

    // コンパイルエラー
    p2 = std::move(p1);
}

なぜかというと、unique_ptrのムーブ代入演算子がオーバーロード解決の候補関数に上がらない条件(SFINAEで阻止される条件)が、デリーターを考慮していないからだ。デリーターを考慮するように規格を修正する提案。

N4367: Comparison in C++

比較関数の提案。

そもそも比較というのは様々ある。同値関係と順序とがあり、同値関係にはequivalenceとequalityがあり、順序には、partial ordering, weak ordering, total orderingが存在する。例えば、通常のソートにはweak orderingが必要で、メモ化にはweak orderingとequalityが必要だ。

三種類の異なる順序を、operator <ひとつで扱うという既存の仕組みがそもそも間違っていたのだ。そこで、これら三種類の順序比較をテンプレート関数として標準ライブラリに追加してはどうか。

template<typename T> bool partial_less(const T&,const T&);
template<typename T> bool weak_less(const T&,const T&);
template<typename T> bool total_less(const T&,const T&);

また、同値関係についても同様に追加してはどうか。

template<typename T> bool partial_unordered(const T&,const T&);
template<typename T> bool weak_equal(const T&,const T&);
template<typename T> bool total_equal(const T&,const T&);

また、strcmpのように、less, greater, neitherの三値を返す関数テンプレートを追加するべきではないか。三値はstrong enumで以下のように提供する。

enum class partial_ordering { less, unordered, greater };
enum class weak_ordering { less, equivalent, greater };
enum class total_ordering { less, equal, greater };

これに対応する関数テンプレートは以下の通り。

template<typename T> partial_ordering partial_order(T,T)
template<typename T> weak_ordering weak_order(T,T)
template<typename T> total_ordering total_order(T,T)

これにより、比較の結果と目的の比較方法を取り違える間違いは型安全に回避できる。

N4368: Introducing alias size_type for type size_t in class std::bitset

std::bitsetにネストされた型名であるsize_typeを追加する提案。

vector<bool>を利用している既存のコードをbitsetに移行する際に、よく使われる共通のネストされた型名が存在しないと既存のコードがうごかないため、その対応。

N4369: Default argument for second parameter of std::advance

C++11に追加されたstd::nextとstd::prevの第二引数には、デフォルト実引数として1が使われている。そのため、

auto it2 = std::next( it1, 1 ) ;

と書くかわりに、

auto it2 = std::next( it1 ) ;

と書くことができる。

std::advanceにも同等のデフォルト実引数があってもよいはずだ。

std::advance( ita, 1 ) ;

と書くかわりに、

std::advance( ita ) ;

と書くことが出来る。

ドワンゴ広告

サーバールーム兼野菜室というのは、冷蔵室にサーバーラックと野菜が詰め込まれているものかと想像したが、サーバーからの排熱を利用した温室だという説もあり、はっきりしない。

特定のグループに所属する人間専用のシェアハウスというのはすぐに平凡な日常に陥ると思うのだが、大丈夫なのだろうか。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-17

C++標準: 2015-02 mailingsのレビュー: N4340-N4359

2015-02 mailingsが公開された。

N4340: Remove Deprecated Use of the register Keyword

registerキーワードを非推奨扱いに変更する提案。将来的には廃止して、registerキーワードは別の機能に使うことができるようになるだろう。

N4346: Multidimensional bounds, index and array_view, revision 5

連続したストレージを多次元配列に見せかけるライブラリ、array_viewの提案。

N4349: WG21 2014-12-05 Ballot Resolution Telecon Minutes

2014年12月5日に行われた電話会議の議事録。

[面倒なPDF] N4350: Agenda and Meeting Notice for WG21 Concepts Meeting Notice (revision 1)

2015年1月15日に行われたConcept会議の予定表。

[PDF注意] N4351: Responses to National Body Comments, PDTS 19570, C++ Extensions for Parallelism

並列実行アルゴリズムライブラリに対するNBコメントに対する返答。今回、C++WG JPからは結構なコメントが出ている。

JP1のtypo報告は受理。

JP2の純粋なベクトルポリシーを付け加える提案は、議論する時間が足りないために却下。

JP3、規格はベクトル化非安全となる条件を定義しているが、具体的にどの標準ライブラリの関数が該当するのかわかりにくい。該当する標準ライブラリ関数の一覧を作成すべきであるという意見は、却下されている。

JP4、実行ポリシーを受け取るオーバーロードがないとする意見は却下。既存の文面は該当のオーバーロードの存在を暗に規定しているとのこと。

N4352: Technical Specification for C++ Extensions for Parallelism, Working Draft

並列実行アルゴリズムライブラリ、Parallelism TSのドラフト。

#include <experimental/algorithm>

int main()
{
    int a[10] = { 1,2,3,4,5,6,7,8,9,10 } ;

    // 並列実行される
    std::for_each( par, std::begin(a), std::end(a),
        [&]( auto & x ) { x *= 2 ; } ) ;

    // シリアル実行
    bool b1 = std::is_sorted( std::begin(a), std::end(a) ) ;
    bool b2 = std::is_sorted( seq, std::begin(a), std::end(a) ) ;

    // パラレル実行
    bool b3 = std::is_sorted( par, std::begin(a), std::end(a) ) ;

    // パラレルベクトル実行
    
    bool b4 = std::is_sorted( par_vec, std::begin(a), std::end(a) ) ;
}

並列実行アルゴリズムは、既存のアルゴリズムに対するオーバーロードで提供される。seqはシリアル実行、parがパラレル実行(スレッドなど)、par_vecがパラレルベクトル実行(スレッド+SIMDやGPGPUなど)

[PDFである必要がない] N4353: Parallelism TS - Editor's Report

Parallelism TSの編集者の報告書。変更点がまとめられている。

[PDF] N4354: Parallelism TS - DTS Ballot Document

おなじくParallelismのドラフト

[PDF] N4355: Shared Multidimensional Arrays with Polymorphic Layout

array_viewとshared_ptrを組み合わせたshared_view/weak_viewの提案。

多次元配列のレイアウトは古い問題だ。C/C++で伝統的なフォーマット、FORTRANで伝統的なフォーマットなどなど。多次元配列の処理がハードウェアで実装されている場合に、そのハードウェアがサポートするレイアウトにあわせる必要があるなど。

レイアウトを変更する場合、ソースコードの大規模なリファクタリングや、あるいは本質的には同一のコードが重複するなどの煩わしいことが起こる。

これを防ぐために、ポリモーフィックにレイアウトを指定できるarary_viewを提案している。

[PDf] N4356: Relaxed Array Type Declarator

配列の宣言子の制限緩和の提案。

多次元配列の要素数は、最初のものだけが省略可能である。

T [ N0 ] [ N1 ] [ N2 ] ...

この場合、N0のみが省略可能となる。

この提案は、N4355で提案されている、shared_viewのために、最初以外の要素数の省略を認める。つまり、N1やN2も省略可能になる。これはどのように使うかというと、以下のように、テンプレート実引数のための型として使う。

std::shared_array< T[N1opt][N2opt][N3opt]...,  Layoutopt >

省略した部分は、実行時に指定できる設計にできる。

N4357: [[noexit]] attribute for main

main関数のみに指定できるattributeである[[noexit]]の提案。これを指定すると、main関数からは戻らないことを指定したことになり、staticストレージ上のオブジェクトのデストラクター呼び出しを抑制できる。すなわち、その分のコード生成をする必要がない。

前回の提案、N4226では、既存の[[noreturn]]をmain関数に指定した時にそのような意味にしようと提案していたが、今回は、別の名前が提案されている。

N4226をUrbana-Champaign会議で議論したところ、実装するにはあまり好ましくないリンカーマジックが必要になるので、その実装方法についてより議論が必要だとしている。

N4358: Unary Folds and Empty Parameter Packs

folding expressionでoperator +, operator *, operator &, operator |で空のパラメーターパックを展開した時のフォールバック値を廃止する。

N4295で提案されているfolding expressionは、パラメーターパックに対して以下のように演算子を適用できた。

template < typename ... Types >
auto sum( Types && ... args )
{
    // args#0 + args#1 + ... + args#N
    return (args + ...) ;
}
 
int main()
{
    // 6
    sum( 1, 2, 3 ) ;
}

N4295で提案されたFolding Expressionは、空のパラメーターパックを展開した場合、一部の演算子にフォールバック値が定義されていた。たとえば、operator +の場合は0、operator *の場合は1

sum() ; // 0

N4358は、一部の演算子について、このフォールバック値を問題あるものとして、廃止する。

当初の設計思想として、フォールバック値は、その演算でよく使われる単位元ではある。operator +の場合は0、operator *の場合は1となっている。しかし、これは純粋に数学的な処理ぐらいにしか役に立たない。

例えば、ベクトル型のクラスVectorTypeがあるとして、そのoperator =はスカラー値を取って、すべての要素をその値にするような処理をするかもしれない。

VectorType vec = { 1, 2, 3, 4, 5 } ;

vec = ( some_vecs + ... ) ;

もし、パラメーターパックsome_vecsが空であった場合、vec = 0 となってしまう。これはVectorTypeクラスの設計次第で、意図しない結果をもたらすかもしれない。

そのため、N4358は廃止を提案している。operator &&, operator ++, operator ,に対しては、これらをオーバーロードするのは通常は推奨できないし、それでもオーバーロードする一部のDSLライブラリなどは、十分に考慮されているので、問題にはならないとして維持するという。

もし、フォールバック値が欲しい場合、binary foldingを使えばよい。

VectorType vec = { 1, 2, 3, 4, 5 } ;

vec = ( some_vecs + ... + 0 ) ;

N4359: A Proposal to Add vector release method just like unique_ptr release method to the Standard Library

vector::releaseの提案

これはunique_ptrのreleaseと同じ発想だ。vectorの内部のストレージの先頭へのポインターが返される。そして、vectorはそのストレージの所有権を放棄する。

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5 } ;

    auto size = v.size() ;
    auto alloc = v.get_allocator() ;
    int * ptr = v.release() ;

    alloc.dealloc( ptr, size ) ;
}

vectorは所有権を放棄するので、ストレージの破棄や、非トリビアルな型の場合、デストラクター呼び出しも自分でやらなければならない。vectorの所有するストレージを奪うことにより、従来ならばコピーせざるをえなかった低級な処理でも、そのままアドレスを渡すことができる。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-15

Dwangoプログラミングコンテストの感想

2016年2月14日、dwangoプログラミングコンテスト2016が行われた。「ドワンゴからの挑戦状」というタイトルもつけられている。

今回の競技プログラミングの参加者は、1月24日に行われた予選を勝ち残った、2016年度新卒予定者から上位20名、一般から上位10名の者である。予選では、以下のような問題が出された。

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder

この予選が終わった後で、筆者が予選問題を試みた結果が以下である。

本の虫: ドワンゴのプログラミングコンテストをクリアできなかったお話

筆者は、C問題のゲーマーじゃんけんの期待値計算が分からなかったので、バカにでも書けるモンテカルロ法を使い、力技で解こうと試みたが、少数点6桁という圧倒的に高い精度が要求されているため、必要な精度が出ずに敗北した。後に聞くところによると、問題で要求される精度をモンテカルロ法で出すには、1兆回ぐらいの試行回数が必要で、制限時間が2分であることを考えると、一回の試行辺り0.12ナノ秒しかかかってはならない計算になる。モンテカルロ法では不可能だ。とはいえ、入力がたったの98通りしかないので、答えを埋め込んむという手もあるのだが。

問題を解くだけでも難しいのに、予選はたったの2時間しか与えられていなかった。見事予選を突破した30人は、一体どのくらいの問題をクリアしたのであろうか。

まず、16新卒枠の20人は、C問題までは通過し、残りのDE問題で部分点まで取れたものが残ったようだ。一般人枠の10名は、D問題も完全に通過することが必要だったようだ。2時間で全問通過した参加者は、たったの一人だった。また、今回は、ドワンゴ社員の代表として、Kusanoが参戦することになった。予選の成績から評価すると、16新卒枠の20人には入れる実力がある。

さて、本線の問題は、以下から挑戦することが出来る。

Welcome to dwangoプログラミングコンテスト - dwangoプログラミングコンテスト | AtCoder

さて、当日の話をしよう。私は当日、非常に眠かった。というのも、プロコンの前日はちょうど金曜日である。花金である。ドワンゴでは、金曜日の夜は大抵ボードゲームが行われる。もちろん、金曜日以外にも突発的にボードゲームは行われるのだが、金曜日の夜は、ドワンゴでボードゲームのかからない日はないといってよい。金曜日も、会社の設備であるセミナールームを借りて、徹夜でボードゲームをしていた。カタン、カルカッソンヌ、キングオブトーキョー等など。そのため、プロコンが行われた会場であるセミナールームは、当日の朝まで大量のボードゲームが散らかっていたのであった。

さて、その徹夜ボードゲームの最中に、私がプロコンの懇親会のメンバーに入っていると、同僚から聞かされた。社内のスケジュール管理システムをみてみると、なるほど、確かに予定が追加されている。すでに午前0時を回っているので、私が知ったのは当日ということになる。タダ飯であり、しかも勤務扱いになるそうだ。

懇親会は夜なので、とりあえず午前中は歌舞伎を見て過ごし、午後になってから、会場となるセミナールームに顔を出してみると、すでに机が配置されていて、準備があらかた整っていた。机にはお菓子と飲み物が置いてあった。そして、前方に大量のきのこの山とたけのこの里・・・まさか、ここでおっ始めるつもりか。戦争を!

さて、その後は問題通過を示す風船を膨らますなどの作業をしていると、時間よりやや早く、人がやってきた。参加者であろうか。いや違う。これこそ世に隠れもなきAtCoderの高橋 直大(chokudai)御仁であった。この仁について、筆者がここで筆を弄して拙い紹介めいた文章を書く必要はないものと信ずる。

さて、御仁から、今回の問題を早々と見せてもらったが、白状すると、一番簡単であるべきA問題:ニコニコ文字列2ですら、筆者には解答方法が皆目見当がつかぬ。chokudai御仁によると、A問題は、今日来ている全員が正解するであろうとのことであった。全問正解はかなり難しいのではとも言っていた。

さて、そうこうしているうちに、参加者がぼつぼつ集まってきた。今回の予選を突破した参加者は、若い人は高校生。遠い人はなんと韓国からやってきている韓国人であった。そして、全員が男であった。一体、プログラマーにおけるいびつな男女比はなぜであろうか。やはり、まだ社会的な理由があるのであろうか。

筆者は、参加者の持ち込み物に注目してみた。本を持ち込んでいる者がいたが、なぜか皆、まったく同じ本を持ち込んでいる。一体あの本は何なのか。筆者は同じくドワンゴ社員であり、問題C: ゲーマーじゃんけんの問題作成をしたtayamaにたずねてみた。 その本はプログラミングコンテストチャレンジブック、通称をアリ本といい、競技プログラマーの間では知らぬ者のない名著であるという。また、chokudai御仁も、 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイドという参考書を出しているそうだ。

6面ダイスを持ち込んでいる者もいた。tayamaによれば、もしダイスを使う問題が出てきた場合、問題の解法を考える際に、実際に回転させられる物理的なダイスがあると便利なのだという。あるプログラミングコンテストで、20面ダイスを使う問題が出てきたのだが、そんな珍しいダイスまで持ちあわせていない会場の参加者の中には、問題用紙に印刷された20面ダイスの展開図を切り取って組み立てはじめる者までいたそうだ。その中で、唯一20面ダイスを持ち込んだチームがいたのだが、そのチームは、せっかく持ち込んだダイスには目もくれず、さっさと頭の中だけで考えて問題を解いたそうだ。なかなか寓話めいた話である。

他には、物理的な紙とペンを用意している人も多かった。

肝心のコンピューターであるが、ラップトップ一台だけを持ち込んだ者がほとんどであった。マウスを持ち込んでいる者はそれなりにいたが、意外にもキーボードを持ち込んでいる者は少なかった。ディスプレイを持ち込んだ猛者はいなかった。

ちらっと眺めたところ、WindowsでもMacでもないOSとしては、UbuntuのUnityが目立った。それ以外のDEを使っている参加者もいたような気がする。

今回のドワンゴのプログラミングコンテストは、AtCoder社のシステムを使い、問題作成もAtCoder社に依頼したと聞いている。現在主流の競技プログラミングのシステムは、Webブラウザー上から、コードを提出し、サーバー側で実行される。競技プログラミングというのは、入力が与えられ、問題から期待される出力を返せば、テストに通過する。競技プログラミングには、正しい出力という条件以上に、最大の実行時間やメモリ使用量などがあらかじめ設定されている。

AtCoderのシステムでは、かなり多くの言語(なんとBashまである)を用いることができるが、今回の参加者は、一人を除いて皆、C++11を使った。一人はJavaを使った。

なぜC++を使うのか。競技プログラミングコンテストは様々あるが、大抵の競技プログラミング用のシステムは、C++はまずサポートしているというのがある。標準ライブラリで著名なデータ構造やアルゴリズムは網羅している。また、実行速度の問題もある。AtCoderのシステムと問題は、言語によって制限時間を変えることがないので、pythonやrubyやphpのようなネイティブコードにコンパイルしない言語は、その分不利となる。

ちなみに、chokudai御仁はC#を使うという。これは、彼の初めて参加した競技プログラミング大会が、Microsoftが主催したものであり、言語がC#限定であったからだという。また、御仁が始めた書いたプログラムは、競技プログラミングの問題に対する解答であり、hello,worldをすっ飛ばし、ifもforも知らない状態で千行ほどのCのコードを書いたという。

プログラミングの目的は様々ある。ソフトウェアを作ることが目的の者もいれば、プログラミング自体に楽しみを覚える人間もいる。しかし、今回のプログラミングコンテストの参加者は、競技プログラミングに回答するためにプログラミングをしているという者がいる。何と純粋な動機だろうか。

ちなみに、当日の参加者におけるきのこの山とたけのこの里であるが、どうやら勢力は拮抗していたように思われる。

さて、競技が始まった。我々は別室にて、AtCoderの管理用のアカウントを用いて様子を見ていた。最初の数分は、何の提出もない。当然だ。まず少なからぬ文章量の問題を読む必要があり、次に書く必要がある。

開始から6分6秒にして、A問題の通過者が現れた。驚くべき速さである。問題を理解するのにすら時間がかかり、解凍方法が思い浮かばない筆者としては、呆然とするしかないのだが、chokudai御仁からすれば、「まあ、解く人は解くでしょ。もちろん、すごい速いし難しいことに変わりはないけれど」と落ち着き払った様子。どうやら生きている世界が違うようだ。

やや時間が経過するが、A問題通過者はそれほど増えない。普段の実力を考えれば、そろそろ解いていてもおかしくない人たちが一度も提出に至らない。どうやら、たったの20点というA問題の配点を見て、後回しの判断をした可能性があるという。今回のプログラミングコンテンストは、たったの2時間である。ただ解けるだけではなく、このような戦略も必要になってくるのだという。

競技開始から一時間を経過したところで、ニコ生を行うことにした。ただ、後から考えると、競技開始と同時にニコ生を行ったほうが、「おお、6分6秒で最初の通過者!」などと実況ができて面白かったように思う。ドワンゴの@mesoとAtCoderの@chokudaiとドワンゴのtayamaと、ゲリラ的に筆者も出た。

dwangoプログラミングコンテスト「ドワンゴからの挑戦状」本選 - 2015/02/14 17:00開始 - ニコニコ生放送

色々と話はあったが、テキストエディターの宗派が全員違ったのは、なかなか興味深かった。chokudai御仁はVisual Studioを使っている。@mesoはSublime Textを、tayamaはEmacsを、筆者はVimを使っている。

さて、競技時間が残り少なくなってきた。

順位を見ると、A問題を通過して、BCを完全解答なりほぼ完全に近い部分点を取得をした人が上位に来ていた。D問題のコインの取り合いはなかなか通過する人がいない。ただし、部分点の10点を取得する人が出てきた。この10点は結構大きく、ABCを完全回答した上位者の中で、部分点10点によりさらに上位に位置する人が出てきた。ただし、部分点とはいえ、落書き回数0の場合も相当に難しいのだが。

順位表と各問題の配点を見ると、まだ、D問題を完全通過すれば、一発逆転のチャンスが残っているようだ。D問題さえできれば、いきなり上位に踊り出ることができる。できればの話であるが。

競技開始から一時間も立つと、手を動かしている人はまばらになった。何やら紙に書いたり、手で頭をおさえて顔をしかめながら虚空を見つめている人が多い。なんとか解法をひねり出そうをしているのだろうか。chokudai御仁によれば、どのような解法を適用すべきか見当がついていない人もいるので、例えばここで適切な解法の名称をぽろりと言ってしまうと、大いなるヒントとなり得るのだという。

さて、いよいよ残り時間が少ない。あと6分ぐらいだ。とそこへ、chokudai御仁がうなり声を上げた。一体何が起こったのか。提出された解答の一覧を見ると、なぜかある一人の参加者が、同じ問題に短時間で何十回も提出を繰り返しているではないか。コードを眺めたchokudai御仁が一言、

「rand使ってます」

その瞬間、全員の顔がニヤリとゆがんで爆笑が起こった。

要するに、入力に対して正解となる出力ができればいいのだ。その出力をどのようにして行ったかというのは、どうでもいいことなのだ。たとえそれが、たまたま正解に一致する乱数列であったとしても。

ただし、さらに詳しく調べたchokudai御仁によれば、これは全くの博打でもないようだ。というのも、この大量提出者の書いたコードは、一部のテストケースで制限時間に引っかかる十分に速度の出ない実装であるので、実行時間を計測して、あまりに時間がかかる場合だけ乱数を返すようにしてあった。chokudai御仁によれば、まっとうな方法の過去の提出で時間切れで失敗しているテストケースの数を考えると、乱数に頼る部分はそれほど多くなく、1/64ぐらいの確率で通ってしまうのではないかとのことであった。のこり5分ならばやる価値のある博打である。

そして、この博打はうまくいった。なんと、無事にテストに通過した提出があったのだ。実に熱い展開であった。

一言だけ付け加えておくと、Cの標準ライブラリのrand()は、C++では非推奨扱いになっている。C++11には新しい乱数ライブラリである<random>があり、C++17に向けてrand_intというrandのように使いやすくて安全なライブラリも提案されているので、そちらを使うべきである。もちろん、このときのAtCoderの環境はGCC 4.8なので、最新のC++14の機能をあますことなく使えるというわけではないのだが。どうやら、AtCoderは近々C++コンパイラーの更新を予定しているらしい。

さて、競技は終了した。ほぼ全員が解答にC++を使っていたので、懇親会で色々と気になることを聞いてみた。

まず、どのようなC++11の新機能を使っているのか。参加者全員が共通して答えた機能は、Range-based forであった。

int main()
{
    std::vector<int> v{ 1, 2, 3, 5, 6, 7, 8, 9 } ;

    for ( auto && elem : v )
    {
        std::cout << elem << std::endl ;
    }
}

range-based forがもてはやされるのには理由がある。もちろん、コンテナーのすべての要素に対して何らかの処理をしたい場合はよくあるのだが、その最大の理由は、自分でイテレーターを使う必要がないという点である。range-based forを使わないと、以下のように書くのだが

for ( auto iter = v.begin(), end = v.end() ; iter != end ; ++iter )
{
    std::cout << *iter << std::endl ;
}

これはバグの元である。人間が手でこのように書いて間違わないわけがない。競技プログラミングにおいて時間はとても貴重であり、くだらないtypoのために何分もデバッグに費やすようなことは大変に痛い時間の浪費である。

これにつけて言及すべき、競技プログラミング特有のC++のテクニックがある。競技プログラミングの解答であるソースコードは、大抵がまずよく使うヘッダーファイル群の#includeに始まり、数十行の、極めて特徴的なプリプロセッサーマクロの定義が続く。

たとえば、以下のようなマクロ

#define ll long long
#define ull unsigned long long

long long a = 0 ; // だるい
ll b = 0 ; // 楽

あるいは以下のようなマクロ

#define pb push_back

int main()
{
    std::vector<int> v ;

    v.push_back( 1 ) ; // だるい
    v.pb( 2 ) ; // 楽
}

長い識別子は打つのに時間がかかり、typoの元でもある。

このような単純な置き換えはまだいいものの、以下のようなマクロまである。

#define rep(i,n) for (int i=0;i<(n);i++)

int main()
{
    int a[10] ;

    // だるい
    for ( int i = 0 ; i < 10 ; ++i )
        a[i] = i ;

    // 楽
    rep( i, 10 )
        a[i] = i ;
    
}

あるいは以下のようなマクロ

#define all(a) (a).begin(),(a).end()

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;

    {// だるい
        int sum = 0 ;
        std::for_each( v.begin(), v.end, [&](auto x){ sum += x ; } ) ;
    }

    {// 楽
        int sum = 0 ;
        std::for_each( all(v), [&](auto x){ sum += x ; } ) ;
    }
}

競技プログラマーとしては、できるだけこのような機械的な人間が間違える可能性のあるコードは書きたくないのだろう。

ただ、この中でrepがとても気になる。指定した回数ループするというのはよくある処理に思える。なぜC++はそのような文法を提供していないのか。ライブラリで十分に出来ることに。

template < typename Integer, typename Func >
void rep( Integer count, Func func )
{
    for ( Integer i = 0 ; i != count ; ++i )
    {
        func(i) ;
    }
}
 
int main()
{
    int a[10] ;
    rep( 10, [&](auto i){ a[i] = i ; } ) ;
}

とはいえ、やはりラムダ式が冗長に見えるかもしれない。

C++に欲しい機能としては、全員が何はともかく無限精度整数を挙げた。たしかに、いい加減に標準ライブラリに存在すべきであると思う。

さて、16新卒枠の中で、ドワンゴの求人応募で、最終面接までのパススルー権を獲得した人が出たそうだ。その権利を実際に行使するのだろうか。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-02-02

闘会議2015のアナログゲームエリア、とある運営スタッフの感想

週末に、闘会議2015が行われた。これはアナログゲームの上級エリアの運営スタッフであった筆者による感想記事である。

筆者は名を江添亮と言う。闘会議ではカタンのインスト要員として参加した。当日はスキンヘッドで口ヒゲを伸ばしていたのが筆者である。

さて、今回の闘会議では、アナログゲームエリアとして、様々なボードゲームを遊べる場所が設置された。

今回初めてとなる闘会議では、色々と突貫作業であり、ボードゲームの理解の浅い人間が企画をしたようで、色々と準備に難があった。

まずボードゲームのインストを出来るスタッフが絶望的に足りないということだ。ドワンゴのボドゲ部員にスタッフ参加の応援要請が来て、開催日の数日ぐらい前に打ち合わせをしたほどだ。

前日にリハーサルで現地を見てみると、ボードゲーム用に用意された机は表面がツルツルと滑り、しかも細長い机を二つ並べたもので、隙間があって使いづらかった。テーブルクロスが欲しいところだが、そのようなものは用意されていなかった。しかたなく100円ショップで安い布切れを買ってきた。

ボードゲームの選択としては、

初級:おばけキャッチ、ワードバスケット、どうぶつしょうぎ、よんろのご

中級:ポーカー、ラブレター、ワンナイト人狼、赤ずきんは眠らない、ゴキブリポーカー、エセ芸術家ニューヨークへ行く。

上級:カタン、モノポリー、カルカソンヌ、スコットランドヤード、将棋、麻雀

初級や中級のボードゲームの選択が実に残念だ。もっとボードゲームらしい面白いゲームで、プレイ時間もそれほどかからないものがたくさんあるというのに。例えば、ダンジョンオブマンダム、クー、ブラフなど。

上級ボードゲームの選択もやや難がある。モノポリーやカタンは運要素があるようにみえて、経験者と初心者の実力差が圧倒的に開き、もし恐ろしいガチ勢がやってきた場合、初心者は何もできないまま時間を浪費することになるのだが、その懸念を全く考えていないようであった。

また、将棋は指導できるほど強いスタッフがおらず、麻雀は完璧に点数計算できるスタッフがいない。初心者がやってきたらどうすればいいのか。この懸念に対し企画者は「え、麻雀って点数計算面倒なんですか?」と言い出す始末。当日が思いやられる。

そもそも、幕張メッセにぽつねんと置かれた将棋盤や手積みの麻雀卓など、成立するのだろうかという懸念もある。

そして、何よりも人員が足りなすぎる。ボードゲームをインストをする必要があるので、誰でもよいというわけではない。

こうして不安なまま迎えた闘会議一日目の朝。スタッフなので、午前7時半に会場入りするため、筆者は午前5時に起きて家を出た。

入場開始時間を待つ間、アナログゲームの上級エリアにどのように人が集まるかについて予想していた。おそらく、開始から30分ぐらいは上級エリアには人は来ないであろう。というのも、上級エリアのボードゲームは、いずれも時間がかかるものばかりであるからだ。最初に成立する卓はどれであろうか。筆者は、麻雀か将棋であろうと予想した。古典的で有名なボードゲームであるし、常に機会さえあれば打ちたいという熱狂者は存在するものだ。

入場時間の午前10時になると、人がなだれ込んできて、アナログゲームの上級エリアを素通りして奥のブースに向かっていった。これは予想通りだ。

とそこへ、一人のオッサンがやってきて、目ざとく麻雀牌を見つけ、近寄ってきた。

「お、麻雀があるやん。やっていこかな」
「麻雀のルールとかは分かりますか?」
「はい、大丈夫です」
「あと3人集まる必要がありまして」
「待ちます」

ドサッと、オッサンは椅子に深く座り、待ちの姿勢に入った。

幸いにして、このオッサンは長く待つ必要がなかった。すぐに同じような面子が3人、椅子に座り、麻雀卓が成立したのであった。あとは話が早い。

「えっと、麻雀は分かりますか?」
東「大丈夫です」
西「大丈夫です」
南「大丈夫です」
北「大丈夫です」
「東風戦で、60分打ち切りで、ありありで・・・」
東西南北、無言でうなづく。
「それではどうぞ」
ジャラジャラジャラジャラ

4人の雀士たちは無言で牌を混ぜ始めた。

なお、当日は任天堂から貸し出された麻雀牌が2セットあったが、二卓目も同様にしてすぐに成立した。麻雀卓の周りには、一歩出遅れたがために卓につけなかった者達が指をくわえてうらやましそうに眺めているではないか。

ここは闘会議2015の会場、幕張メッセである。今は開場直後である。今ここで麻雀を打っている面子は、闘会議のチケットを買い、朝早くに海浜幕張までやってきて、入場列の前列に並んでいたはずの者達である。それがこうして粗末なパイプ椅子に座り、手積みの麻雀卓で無言で麻雀をしているとは。しかも周りを取り囲む観戦客も増えるばかりで一向に減らないときている。

どうやら、筆者は麻雀というものをあまく見ていたらしい。麻雀がこんなにも人の気を惹きつけるほどの魅力があるものだとはつゆ思わなかった。

こうして、アナログゲーム上級エリアの麻雀卓は、終日人が絶えることがなく、観戦客も周りに満ち満ちていたのであった。当初の懸念である、点数計算や、そもそも麻雀のルールを知らない者が来るかもしれないという懸念は、まったくの的はずれであった。

この様子では、麻雀卓があればあるだけ成立するだろう。二卓しか用意していないのが残念だ。当日の運営スタッフがやるべきことは、にわかに「テンゴで」などと言い出したりしないかどうかを監視することだけであった。

将棋卓も同様にして、途切れることなく成立していった。

さて、筆者が担当するカタンは、そうすぐには人が集まらなかった。3人集まったので、やむことを得ずして仕方なく筆者も卓に着いてプレイせざるを得なかった。ただし、それは最初の一ゲームだけで、周りには常に観戦客が4人以上いて、次の4人のプレイヤーに不足することはなかった。実に残念・・・いや良かった。

実に様々な面々がカタンをプレイしていった。カタン未経験者はカタンというボードゲームの名前は知っていて、つねづねやりたいとは思っていたが、やる機会に恵まれない者達であった。中には、カタンを持っているにもかかわらず、一度もやったことがない者までいた。これは無理もない話で、カタンを習得するには先達が必要である。今回、筆者は何十人ものカタン未経験者にカタンを教えることができたので、満足であった。これをいい機会に、外でもカタンをプレイしてほしいものだ。休憩の暇がなかったが。

また、用意されたカタンは一卓しかなかったのだが、筆者は個人的な私物のカタンも持ち込んでいて、ゲリラ的に二卓立てた。また、別のボードゲームも個人的に持ち込んでゲリラ的に行った。このような裁量がもっと強く発揮できればよかったのだが、来年の闘会議に期待したい。

カタンにも周りに観戦客が多く、もう一卓あればよかったのにと思う。また、初心者も参加できる卓と、上級者のみのガチ卓という区別があればよかったように思う。ガチ卓は地獄の様相の飾り付けをして、「この卓に座るものは一切の希望を捨てよ」とイタリア語で書いておくと雰囲気が出るのではないか。

また、あまりにも運営スタッフが最初から最後までインストして出しゃばり過ぎる必要はないように思う。ボードゲームなのだから、卓に座ってプレイするもの同士で交流を促したほうがよい。そういう意味で、もっと卓が欲しかった。

もうひとつ思ったこととして、外でボードゲームをする機会を増やせないかと漠然と思った。ボドゲは好きであるが、時間、友人、対人能力など、様々な理由により、あまりボードゲームができていない人がいるようだ。ドワンゴでは昼からボドゲをしている社員までいるので恵まれていると言える。何とかこういう特別の機会にたよらずに広くボードゲームができるようにならないものか。

闘会議2日目

寝坊して6時半に起きた。開場には何とか間に合った。

またもや開場とともに人がなだれ込んでくる。2日目とあって目当てのブースが定まっているのか、迷わず一直線にブースまで走っていく人が多かった。

その中で、悠然と上級エリアに歩み寄ってくる者達がいた。座った椅子はもちろん、麻雀卓である。すぐに卓が埋まり、麻雀が始まった。周りには初日と同じく、指をくわえてうらやましそうにながめている者達がいる。

程なくしてカタン卓も人が埋まった。二日目は実に残念、いや、良かったことに、カタン卓は初日に増して盛況で、筆者がプレイする余地は一切なかった。

ところで、初級、中級エリアは凄い人だかりで、列をなしていた。初級中級のボードゲームは、あまりにも簡単すぎるので、筆者にとっては最高に面白い選択ではないように思うのだが、これは意外だ。どうやら、説明に30秒以上を要するようなボードゲームは、重いと判断されてしまうのかもしれない。筆者としては、もう少しルールが複雑だが面白いボードゲームを体験して欲しいのだが。

次の超会議や闘会議に、筆者の裁量で自由にボードゲームが出来るボドゲ卓スペースが欲しいとまで思った。

ドワンゴ広告

ドワンゴでは昼間から会社でボドゲを行う社員がいる。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-29

闘会議2015のアナログゲームエリアのボードゲームの紹介

きたる闘会議2015アナログゲームエリアでは、様々なボードゲームが遊べる。すでに当日設置されるゲームは決まっているのだが、公式サイトはまだ更新されていない。

闘会議はスタッフの多くがドワンゴ社員である。ボドゲのインストができるスタッフが少なく、急遽社内のボドゲ好き社員に応援が要請されて、私もスタッフとして参加することになった。

何しろ、闘会議というのは今回が初めてなので、当日の雰囲気が全く予想できない。全くのボドゲ初心者が来るのか、はたまた、ガチ勢が来るのか。初心者にはボドゲに触れてもらい、上級者はそのまま楽しめるような雰囲気なればいいのだが。

ともかく、当日設置されているボドゲの一覧を紹介しようと思う

初級エリア

初級エリアのボードゲームは、どれも説明が簡単で、未経験者でもすぐに遊べるボードゲームが選ばれている。

  • おばけキャッチ

    参加人数は2-6人。短時間のアクションゲームである。カードに描かれた物を早いものがちで取るゲームだ。

  • ワードバスケット

    参加人数は2-8人。しりとりだ。はじめの文字だけではなく、終わりの文字も指定されている。筆者はこのゲームが非常に苦手だ。強い人はとてつもなく強いのだが。

  • どうぶつしょうぎ

    参加人数は2人。大胆に簡略化した将棋だ。

  • よんろのご

    参加人数は2人。大胆に簡略化した碁だ。

中級エリア

中級ボードゲームは、事前に少し長い説明が必要になってくるものもある。

  • ポーカー

    十分に有名なゲーム。ガチ勢に初心者が混じった場合、すぐに飛ぶだろう。

  • ラブレター

    手札を回していきながら相手の手札の中身を予想して勝負を仕掛けるゲーム。

  • ワンナイト人狼

    参加人数3人から7人。人狼系

  • 赤ずきんは眠らない

    参加人数4-6人。人狼系

  • ごきぶりポーカー

    参加人数2-6人。「これはゴキブリです」と言いながらハエやクモを渡すブラフゲーム。

  • エセ芸術家ニューヨークへ行く

    参加人数5-10人。ひとつのキャンバスにみんなで一筆づつ指定された物の絵を書いていく。ただし、参加者の中に一人だけ何の絵を描くか知らされていないエセ芸術家がいる。エセ芸術家をあてれば芸術家達の勝ち。ただし、何の絵を描いているかエセ芸術家にバレてしまうと芸術家達は負ける。

初級と中級のゲームは、未経験者でもできるし、時間もそれほどかからない。問題は、上級エリアだ。

上級エリア

上級ゲームは、説明にも時間がかかるし、プレイ時間も長い。1時間以上は確実にかかるゲームが多い。

  • カルカソンヌ

    参加人数2-5人。土地をつなげていくゲーム。ルールはそれほど複雑ではない。ガチ勢が来るかどうかはわからない。

  • カタンの開拓者たち

    参加人数4人。サイコロを振って資源を獲得して建築をし、10点先取するゲーム。ガチ勢の来る可能性がある。主に筆者がインスト要員として割り当てられている。

  • スコットランド・ヤード:東京

    参加人数2-8人。怪盗一人を刑事達が捕まえるゲーム。プレイ時間は長いが、ルールは簡単。ガチ勢もいない。

  • モノポリー

    参加人数2-8人。すごろくのように環状のマス目を回りながら不動産取引をして、他のプレイヤーを破産させて勝ち残るゲーム。ガチ勢の来る可能性がある。

  • 将棋

    参加人数2人。ご存知の将棋。指導できるほどの棋力を持つスタッフはいない。いい勝負になるほど実力が拮抗した参加者同士で対戦できるといいのだが、どうなることやら。

  • 麻雀

    参加人数4人。ご存知の麻雀。自動卓がないので手積み、東風戦。麻雀のルールが分からない全くの未経験者はお断わりいただく予定。

上級エリアのうち、カルカソンヌとスコットランドヤードは未経験者でも楽しめるゲームだ。ただし、プレイ時間が長めなので注意。

モノポリーは有名なゲームだ。ルールはそれほど複雑ではないが、ガチ勢がやってくる可能性もある恐ろしいゲームだ。

カタンはルールの説明にも時間がかかり、プレイ時間も長い。加えてガチ勢がやってくる可能性もある。

将棋と麻雀に関しては、どのくらいの実力を持った人間がやってくるのか予測できない。あらかじめプロを配置しているわけでもないので、完全に参加者が遊べる場所を提供するだけになる。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-28

ドワンゴのプログラミングコンテストをクリアできなかったお話

dwangoプログラミングコンテスト2016

ドワンゴが主催するプログラミングコンテストの予選が、24日に行われたそうだ。筆者はクリアできなかったが、簡単なものだけ解説する。本格的な解説が読みたい人は、わざわざこの記事を読まずとも、以下で解説されているようだ。

「dwangoプログラミングコンテスト」予選問題解説 // Speaker Deck

A: プレミアム会員 - dwangoプログラミングコンテスト | AtCoder

ニコニコ動画には、プレミアム会員という制度があります。このプレミアム会員制度には月額一定の額を支払うことで加入できます。

ニワンゴくんは、この n ヶ月間連続してプレミアム会員です。 また、x ヶ月前に月の一定支払い額が 525 円から 540 円に変わったことを知っています。 つまり、この n ヶ月のうち最近の x ヶ月間は月額 540 円支払っていて、それ以外の月では 525 円払っていたことが分かっています。

n と x が与えられるので、この n ヶ月間でニワンゴくんがプレミアム会員制度に支払った合計額を出力してください。

\(525(n-x) + 540x\)を計算すればよい。

#include <iostream>
 
int main()
{
    int n = 0 ;
    int x = 0 ;

    std::cin >> n >> x ;
 
    int payment = ( n - x ) * 525 + x * 540 ;
 
    std::cout << payment << '\n' ;
}

B: ニコニコ文字列 - dwangoプログラミングコンテスト | AtCoder

0 から 9 の数字から成る文字列 S が与えられます。

ある文字列 X について、X="25" または X="2525" または X="252525" …… というふうに "25" を何回か繰り返した文字列になっているとき、X はニコニコ文字列であるといいます。 たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

あなたの仕事は、文字列 S について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。

与えられた文字列から連続した"25"をすべて探し出し、25の数を数える。N個の"25"が連続した文字列の部分文字列の取り出し方は、1+2+3+...+N通りあるので、\(\frac{N(1 + N)}{2}\)で計算すればよい。

ただし、Sの長さは100000以下であるとのことなので、もし\(\frac{N(1 + N)}{2}\)の計算に32bit符号付き整数を使っていた場合、50000回連続した文字列が渡されると、50001 * 50000を計算しようとするとオーバーフローしてしまう。

連続した"25"文字列は、C++11で追加された<regex>ライブラリを使えばよい。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{
    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::sregex_iterator iter( str.cbegin(), str.cend(), re ) ;
    std::sregex_iterator end ;

    unsigned long long int sum = 0 ;
    for ( ; iter != end ; ++iter )
    {
        auto n = iter->str().length() / 2 ;
        sum += count( n ) ;
    }

    std::cout << sum << '\n' ;
}

ただし、このコードはatcoderを通らない。理由は、atcoderのC++11のコンパイラーがGCC4.8.1という2年前の化石バージョンで、libstdc++がregex_iteratorをサポートしていないからだ。そのため、以下のようにregex_searchを複数回呼び出すというマヌケなコードを書かなければならない。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{
    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::smatch m ;

    unsigned long long int sum = 0 ;

    auto iter = str.cbegin() ;
    auto end = str.cend() ;


    while ( iter != end )
    {
        std::regex_search( iter, end, m, re ) ;
        auto n = m.str().length() / 2 ;
        sum += count( n ) ;

        iter = m[0].second ;
    }

    std::cout << sum << '\n' ;
}

と思ったが、これも時間制限内に終わらない。Wandboxで試しても終わらないので、どうもlibstdc++ 4.8.1のregexライブラリには問題があるようだ。

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

2年前のC++コンパイラーなど使うべきではないという教訓が得られた。

C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

期待値の計算方法がわからないのでモンテカルロ法で解こうとしたが、必要な精度が出ずに敗北した。小数点以下6桁は辛い。

なんでも、必要な精度を出すためには、1兆回は試行しなければならないそうだ。制限時間は2分。すると、一回の試行は0.12ナノ秒で終えなければならない。無理だ。

本の虫: 全プログラマーが知るべきレイテンシー数

最終的に以下のようなクソコードを書きちらしたが、もちろん必要な精度は出ない。ちなみに、atcoderはfutureを使うと実行時エラーになる。

#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <future>
 
enum { Rock = 0, Paper = 1, Scissors = 2 } ;
 
template < typename Iter, typename RNG >
unsigned long long int play( Iter begin, Iter end, RNG rng )
{
    unsigned long long int i = 0 ;
 
for ( ; ; ++i )
{
    int n = std::distance( begin, end ) ;
 
 
    // 勝者決定判定
    if ( n == 1 )
    {
        break ;
    }
 
    // じゃんけん
    std::generate( begin, end, rng ) ;
 
 
    // 出された手が 1 種類の場合 
    int first_hand = *begin ;
    bool b = std::all_of( begin, end,
        [=](int x) { return x == first_hand ; } ) ;
 
    if ( b )
    {
        continue ;
    }
 
    // 出された手が 2 種類以上の場合
 
    // 手をカウント
    
    auto rock = std::count( begin, end, Rock ) ;
    auto paper = std::count( begin, end, Paper ) ;
    auto scissors = std::count( begin, end, Scissors ) ;
 
 
    // 出したプレイヤーの数が最も少ない手に注目する。 
 
    // そのような手が 3 種類あった場合
    if ( rock == paper && rock == scissors )
    {
        continue ;
    }
 
 
    auto hands = { rock, paper, scissors } ;
    auto minor = std::min( hands ) ;
 
    // 出ていない手がある場合
    if ( minor == 0 )
    {
 
        typename Iter::difference_type h[3] = { rock, paper, scissors } ;
        std::remove( h, h + 3, 0 ) ;
        auto m = std::min( h[0], h[1] ) ;
        end = begin + m ;
        
    }
    else {
        // すべての手が出た場合
        end = begin + minor ; 
    }
   
}
 
    return i ;
 
}
 
 
constexpr unsigned long long int trial = 10000 ;
 
 
unsigned long long int gamer_zyanken( int n )
{
    std::mt19937 engine ;
 
    std::uniform_int_distribution<> dist( 0, 2 ) ;
 
 
    std::vector<int> players( n ) ;
 
    unsigned long long int sum = 0 ;
 
    for ( int i = 0 ; i != trial ; ++i )
    {
        sum += play( players.begin(), players.end(), [&]{ return dist(engine) ; } ) ; 
    }
 
    return sum ;
}

 
int main()
{
    int n ;
    std::cin >> n ;
 
    auto f1 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f2 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f3 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f4 = std::async( std::launch::async, gamer_zyanken, n ) ;
 
    unsigned long long int sum = f1.get() + f2.get() + f3.get() + f4.get() ;
 
    double result = double(sum) / double(4 * trial) ;
 
    std::cout << result << '\n' ;
}

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-26

Convictedというボドゲが送られてきた

私宛に、Convictedというボードゲームが贈られてきた。調べたところ、Kickstarterで出資を受けたボードーゲームらしい。

The Convicted - expand your town and fight for survival by Mateusz Albricht — Kickstarter

設定としては、囚人が未開地の開拓を条件に王から恩赦を受けて、野蛮人や怪物などの襲撃から防衛しつつ、都市を発展させていくというものらしい。

具体的なルールは把握していないが、極めて重いゲームで、プレイには90分以上かかるらしい。

C++11の時間ライブラリ: chrono

<chrono>は、C++11で追加された時間ライブラリである。

単位時間を扱うためのduration、起点からの経過時間を扱うためのtime_point、現在の起点からの経過時間を取得するためのclockからなる。Cの標準ライブラリのtime_tとtime(), clock_gettime()を置き換えることが出来る。日付機能は含まれていない。

duration

時間について考える。一時間は60分である。1分は60秒である。1秒は1000ミリ秒である。

単位の異なる時間の値を相互に変換するのは、簡単な計算だ。

unsigned int min_to_sec( unsigned int min )
{
    return min * 60 ;
}

しかし、実引数minに渡される値の単位が分であることを保証する方法はない。間違えたとしても、コンパイルエラーにはならない。

chronoでは、時間単位を扱うライブラリ、durationを追加した。これは型安全に時間の計算をしてくれる。


#include 

int main()
{
    // 15分
    std::chrono::minutes min(15) ;

    // 分を秒に変換
    std::chrono::seconds sec = min ;

    // 900
    std::cout << sec.count() << std::endl ;

    // エラー、余りが発生する可能性があるため
    min = sec ;

    // OK
    min = std::chrono::duration_cast<std::chrono::minutes>( sec ) ;
}

durationテンプレートには、よく使う時間単位、hours, minutes, seconds, miliseconds, microseconds, nanosecondsというtypedef名があらかじめ宣言されている。

また、C++14からは、時間単位のtypedef名へのユーザー定義リテラルが定義されている。それぞれ、h, min, s, ms, us, nsとなっている。

auto hours = 3h ;
auto seconds = 100s ;

auto sum = 1h + 5min + 3s ;

durationクラスは、メンバー関数countにより、内部表現の値を得ることができる。単位はdurationテンプレートの特殊化のとおりだ。

int main()
{
    std::chrono::seconds s(10) ;

    s.count() ; // 10

    auto s2 = s + s ;

    s2.count() ; // 20

    std::chrono::hours h(1) ;
    h.count() ; // 1

    s = h ;

    s.count() ; // 3600
}

time_point

time_pointは、ある起点時間からの経過時間を表現するクラスだ。time_point同士を減算すると、その結果はdurationになる。time_pointを直接構築することはあまりない。time_pointは、clockから得ることができる。C標準ライブラリのtime_tに比べて、型安全になっている。

clock

clockは、現在のtime_pointを取得するクラスだ。staticメンバー関数のnowでtime_pointを取得できる。

int main()
{
    // 処理前の起点からの経過時間
    auto t1 = std::chrono::system_clock::now() ;

    // 処理
    std::this_thread::sleep_for( std::chrono::seconds(1) ) ;

    // 処理後の起点からの経過時間
    auto t2 = std::chrono::system_clock::now() ;

    // 処理の経過時間
    auto elapsed = t2 - t1 ;

    // 単位は未規定
    std::cout << elapsed.count() << std::endl ;
}

system_clockは、システム上のリアルタイムクロックを表現するclockである。

このクロックの使うdurationは未規定である。そのため、経過時間を実際の時間単位で知りたければ、duration_castが必要になる。

int main()
{
    // 処理前の起点からの経過時間
    auto t1 = std::chrono::system_clock::now() ;

    // 処理
    std::this_thread::sleep_for( std::chrono::seconds(1) ) ;

    // 処理後の起点からの経過時間
    auto t2 = std::chrono::system_clock::now() ;

    // 処理の経過時間をミリ秒で取得
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(t2 - t1) ;

    // 単位はミリ秒
    std::cout << elapsed.count() << std::endl ;
}

C++規格は、起点時間がいつなのかを規定していない。経過時間はtime_pointのメンバー関数tiem_since_epochで取得できる。また、system_clockから得られるtiem_pointは、time_tに変換できる。

int main()
{
    // time_point
    auto t1 = std::chrono::system_clock::now() ;
    // 起点時間からの経過時間
    std::cout << t1.time_since_epoch().count() << '\n' ;

    // time_t
    auto t2 = std::chrono::system_clock::to_time_t( t1 ) ;
    std::cout << t2 << '\n' ;

    // tme_point
    auto t3 = std::chrono::system_clock::from_time_t( t2 ) ;

    std::cout << t3.time_since_epoch().count() << std::endl ;
}

system_clockのtime_pointとtime_tが、同じ時間単位の分解能を使っているとは限らない。

clockはsystem_clockだけではない。他にも、steady_clockがある。これは、実時間の経過によって、time_pointの経過時間が減らないことが保証されている。

int main()
{
    // time_point
    auto t1 = std::chrono::steady_clock::now() ;

    // この間にシステムの時刻が過去に変更されるかもしれない


    auto t2 = std::chrono::steady_clock::now() ;


    // trueであることが保証されている
    bool b = t2 >= t1 ;
}

その他のclockにも、constexpr staticデータメンバーのis_steadyの値によって、steady_clockと同じ保証があるかどうかを確かめることができる。

// true/false
bool b = std::chrono::system_clock::is_steady ;

C++規格はもうひとつ、high_resolution_clockを規定している。これは、時間の分解能が高いclockであると規定されている。

auto t1 = std::chrono::high_resolution_clock::now() ;
// 処理
auto t2 = std::chrono::high_resolution_clock::now() ;

// 処理のかかった時間
auto e = t2 - t1 ;

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

GCCのoverrideのバグらしきもの

ask.fmにこのような質問がきた。

C++では、overrideはキーワードではない。overrideは、特定の文脈でだけ文法で認識され、それ以外の場所では、単なる識別子となる。

そのため、以下のようなコードが書ける。

struct override { } ;

struct B
{
    virtual auto f() -> override ;
} ;

struct D : B
{
// GCC: error: two or more data types in declaration of 'type name'
    auto f() -> override override ;
} ;

しかしなぜかGCCは開発版の5.0ですら、コンパイルエラーとなる。

まさか未だにこのような面白い問題が残っているとは。

GCC Bugzillaを検索したところ、同じ不具合は報告されていないようなので、報告してみた。

Bug 64794 – GCC failed at virtual function with "override" trailing return type name, followed by override virt-specifier

Clangでは問題がない。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-25

人の顔が認識できない

どうも、私は人の顔を認識する能力が劣っているのではないかと、最近考えるようになった。

妖怪ハウスに何度か遊びに来ている客に、つい、「どちら様でしたっけ」と訪ねてしまうことがよくある。そのたびに、「もう何度も会いましたよ」とか、「何度も同じことを聞かれていますよ」などと言われるのだが、やはり思い出すことができない。

極めつけは、妖怪ハウスに住んでいた元住人ですら、顔を忘れていたことだ。なるほど、言われてみれば確かに、住んでいた当時はそのような顔をしていた気もする。しかし確証が持てない。名前は忘れていないし、その人物の言動も覚えている。話してみると、なるほど、確かにそのような声でそのような口調であったので、本人なのであろうが、やはり問題の顔面がそのようなものであったかどうか断定できない。

どうも私は、個人を識別するのに、服、髪型、体型などの情報を使っているのではないかと思われる。

思えば、同じような体型と髪型の人間が似たような服を着ていた場合、間違えてしまうことがよくあるのだ。

関係しているかどうかわからないが、私は人の顔面がイケメンや美人であるかどうかをうまく評価することができない。よく人が、「誰々はイケメンである、美人である」などと評しているのを聞いても、私にはよくわからないのだ。

これまでの経験から推定するに、世の中のイケメン、美人と他人が評価している人間に共通する項目というものは、頬骨が張り出るほど頬が痩せこけていて、髪が頬を隠すほど長いものを言うものだと思われる。しかし、これは思えば顔の外側の特徴だ。目鼻や口の特徴ではない。

はてさて、困ったことだが、どうしようもない。

2015-01-20

C++の正規表現ライブラリ: std::regex

いまさらながら、C++の正規表現ライブラリを調べている。

C++の正規表現ライブラリ、std::regexは、boost::regexを土台に設計されている。boost::regexの正規表現の文法は、perlなのに対し、std::regexは、ECMAScriptである。この理由は、しっかりと正規表現の文法が定義されていて、外部規格として参照できる品質のものが、perlには存在しないためだ。std::regexはposixと拡張posixとawkとgrepとegrepの正規表現にも対応している。

本記事では、ECMAScriptの正規表現を使う。また、参考のためのECMAScriptのコードも使う。

全体一致

文字列全体が正規表現に一致するかどうかを調べたいとする

var re = /1234/ ;
var text = "1234" ;

var result = re.test( text ) ;

これを、std::regexを使って書くと以下のようになる。

#include <regex>

int main()
{
    std::regex re("1234") ;
    std::string text("1234") ;

    bool result = std::regex_match( text, re ) ;
}

C++には、正規表現リテラルはないので、文字列リテラルで正規表現を記述する。

もうすこし正規表現らしいことをしてみよう。連続した数字に一致する正規表現を使ってみる。

var re = /\d+/ ;
var text = "1234" ;

var result = re.test( text ) ;

残念ながら、C++の文字列リテラルで/\d+/を書こうとすると、エスケープシーケンスのためにエラーになる。

std::regex r1 = "\d+" ; // エラー
std::regex r2 = "\\d+" ; // OK

"\\d+"と書けば動くのだが、これはとても書きづらい。C++11で追加された生文字列リテラルを使えば、自然に書けるようになる。

std::regex re = R"(\d+)" ;

外側の括弧は生文字列リテラルの文法なので紛らわしいが、バックスラッシュを二重に書くよりはマシだろう。

部分一致の検索

以下のようなECMAScriptのコードをC++で書きたいとする

var re = /\d+/ ;
var text = "There are 99 bottles." ;

var a = re.exec( text ) ;
var result = a[0] ; // "99"

C++では、以下のように書ける。

int main()
{
    std::regex re( R"(\d+)" ) ;
    std::string text="There are 99 bottles." ;

    std::smatch m ; // std::match_results<string::const_iterator>
    std::regex_search( text, m, re ) ;

    std::cout << m.str() << std::endl ;
}

部分一致を検索するには、regex_searchを使う。結果は、match_resultsで受け取ることができる。

部分一致をすべて検索。

以下は、部分一致をすべて検索するECMAScriptのコードである。

var re = /\d+/g ;
var text = "123 456 789" ;

// ["123", "456", "789"]
var result = text.match( re ) ;

C++では、イテレーターを使ってregex_searchを繰り返し呼び出すことで書くことができる。

std::vector< std::string >
search( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    auto iter = text.cbegin() ;
    auto end = text.cend() ;

    std::smatch m ;

    while ( std::regex_search( iter, end, m, re ) )
    {
        result.push_back( m.str() ) ;
        iter = m[0].second ;
    }

    return result ;
}

int main()
{
    std::regex re( R"(\d+)" ) ;
    std::string text="123 456 789" ;

    auto result = search( text, re ) ;

    for ( auto & elem : result )
    {
        std::cout << elem << std::endl ;
    }
}

とはいえ、これは面倒だ。

C++には、このように部分一致を複数見つける用途に、regex_iteratorを用意している。これを使えば、以下のように書くことができる。

std::vector< std::string >
search( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    std::sregex_iterator iter( text.cbegin(), text.cend(), re ) ;
    std::sregex_iterator end ;

    for ( ; iter != end ; ++iter )
    {
        result.push_back( iter->str() ) ;
    }

    return result ;
}

置換

以下のように、DogをCatに置き換えたいとする。

var re = /Dog/g ;
var text = "Dog is nice. Dog is cute. Dog is awesome." ; 

// "Cat is nice. Cat is cute. Cat is awesome."
var result = text.replace( re, "Cat" ) ;

C++では、regex_replaceを使って書くことができる。


int main()
{
    std::regex re( R"(Dog)" ) ;
    std::string text("Dog is nice. Dog is cute. Dog is awesome.") ;

    // "Cat is nice. Cat is cute. Cat is awesome."
    auto result = std::regex_replace( text, re, "Cat" ) ;
}

以下のように最初の一致だけを書き換えたい場合、

var re = /Dog/ ;
var text = "Dog is better than dog." ; 

// "Cat is better than dog."
var result = text.replace( re, "Cat" ) ;

以下のように書くことができる。

int main()
{
    std::regex re( R"(Dog)" ) ;
    std::string text="Dog is better than dog." ;

    // "Cat is better than dog."
    auto result = std::regex_replace( text, re, "Cat",
        std::regex_constants::format_first_only ) ;
}

置換はECMAScriptの文法と同じだ。

// ECMAScript
var text = "123 456"
var re = /(\d+) (\d+)/ ;

// "456 123"
var result = text.replace( re, "$2 $1" ) ;
// C++
std::string text("123 456") ;
std::regex re(R"((\d+) (\d+))") ;

// "456 123"
auto result = std::regex_replace( text, re, "$2 $1" ) ;

サブマッチ

正規表現は括弧でキャプチャをすることができる。

var re = /(\d+) (\d+) (\d+)/ ;
var text = "123 456 789" ;

// ["123 456 789", "123", "456", "789"]
var result = text.match( re ) ;

C++では、match_resultsから得られるsub_matchをたどることで、同等のことができる。


std::vector< std::string >
match( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    std::smatch m ; // match_results

    std::regex_match( text, m, re ) ;

    for ( auto && elem : m )
    {// elemはsub_match
        result.push_back( elem.str() ) ;
    }

    return result ;
}

int main()
{
    std::regex re( R"((\d+) (\d+) (\d+))" ) ;
    std::string text="123 456 789" ;

    // {"123 456 789", "123", "456", "789"}
    auto result = match( text, re ) ;

    for ( auto && elem : result )
    {
        std::cout << elem << std::endl ;
    }
}

std::regexを一通り触ってみた感想としては、Boost.Regexのうち、規格として定義できる部分だけ定義したという感じだ。

std::regexと現行の主要なライブラリ(libstdc++とlibc++)の実装を調べると、ASCII文字か、あるいは単なるバイト列に対して使うことが出来る正規表現でしかなかった。charとwchar_tには対応している。ただし、ASCII文字以外には対応していない。UTF-8を使えばバイト列として一致させることはできた。つまり、

// 通常の文字列リテラルのエンコードはUTF-8の環境
std::regex re(R"(いろは にほへ)") ;
std::string text("いろは にほへ") ;

std::regex_match( text, re ) ;

これは動く。ただし、wchar_tは動かない。

std::wregex re(R"(いろは にほへ)") ;
std::wstring text(L"いろは にほへ") ;

// 動かない
std::regex_match( text, re ) ;

UTF-8は単なるバイト列だと考えるしかない。例えば以下は動かない。

// 通常の文字列リテラルのエンコードはUTF-8の環境
std::regex re(R"(.)") ;
std::string text("あ") ;

// 動かない
std::regex_match( text, re ) ;

char16_t、char32_tは、libstdc++とlibc++では、コンパイルすら通らない。

というわけで、現状の規格と実装状況から言えば、ASCII文字だけに限定していいのならば、std::regexとstd::wregexは使える。Unicodeが扱いたければ、規格外の正規表現ライブラリを使うべきだ。

ドワンゴ広告

そろそろC++のブログ記事を増やしていきたい。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-16

インドでC型肝炎の薬の特許が無効化された理由

How India's Patent Office Destroyed Gilead's Global Game Plan - Businessweek

インドの特許庁が、Gilead Sciences社のC型肝炎の薬、Sovaldiの特許を無効化した理由が取り上げられていて興味深い。

該当の特許の化合物は、既存の化合物と似通っているためと、発明者が既存の薬に比べて劇的な効果の違いを証明できなかったためだという。

2015-01-15

ガラケー時代の翻訳

When I was in Japan I did proof reading for a Japanese feature phone. A major Ja... | Hacker News

Hacker Newsのコメントが面白かった

日本にいた時に、日本のガラケーの翻訳検証をしたことがある。ある有名な日本のブランドだった。あれは実に喜劇であった。

英語を検証するオーストラリア人と、ドイツ人の男と、イタリア人の女と、フランス人の私がいた。検証前に行われていたこと:英語力の貧弱な人間(おそらくはソフトウェアエンジニア)による日本語から英語への翻訳があり、その不思議な英語を、文脈を一切与えられずに文字列だけを与えられた翻訳家が別の言語に翻訳していた。

現場では、我々に示されたものは文字列だけであった。そして、製造元からやってきた「超企業秘密」な未公開のデバイスにアクセスできる担当者が一人。

半分以上もの翻訳は、文脈の欠如により間違っていた。フランス語の翻訳家は、「ゴミの日」を、「クソな日」と訳していた。おそらく、とてつもなくついていない一日をカレンダーに書き込むのに使うと考えたのだろう。

「(あるものを)削除する」のような文章が頻繁に現れた。当然、我々には、「あるものって何だ? 男性名詞か女性名詞か中性名詞かどれだ?」という疑問が生じた。もちろん、それはできない相談であった。すでにコードを書き変えるには遅すぎるため、我々は、"%n item(s)"のような汚い手法を取る必要があった。

ところで、現場のオーストラリア人は人類への希望を失いつつあった。ある文章が、完全に間違っていたのだ。その文章は英語で何らの意味をも持たなかった。それを読んだ現場の人間は「なんじゃこりゃ?」というしかなかった。我々には英語の文字列を変えることは許されていなかった。それはすでに検証済みであったからだ。

さもありなん