競技プログラミングという言葉の誕生

一定時間内に題意を満たすようなプログラムを、よりたくさん、より高速に書くことを競うプログラミングコンテスト、およびその形式のことはしばしば「競技プログラミング」と呼ばれています。今となっては当たり前となった言葉ですが、私が現役でこのような競技に参加していた頃 (2005年まで) はそのような言葉はなく、単に「プログラミングコンテスト」と呼ばれていました。

さて、競技プログラミングという言葉はいつ生まれたのでしょうか? 一部では “competitive programming” の訳語であると思われていますが、実はそうでもないのです。

自分の体験談を少し振り返ると、私が YUHA で競技プログラミングに関連する同人誌的なものを書き始めた 2008 年夏 (C74) には、「競技プログラミング」という言葉はまだ広くは知られてはおらず、同人誌中でも競技プログラミングという言葉は使われていませんでした。2010 年夏 (C78) に発行した同人誌からタイトルに「競技プログラミング」という言葉が使われ始めています。この頃売り子も自分がやっていましたが、「競技プログラミング」という言葉は全く浸透しておらず、興味を持ってもらった人に「競技プログラミング」とは何かを一から説明するような状況でした。ただ、「競技」という言葉はキャッチーだったようで、2010 年冬 (C79) に発行するものからは「競技」という言葉を前面に出したことを覚えています。それでも浸透度は低く、数年は「競技プログラミング」という言葉の説明が必要でした。2019 年現在「競技プログラミング」という言葉は十分に浸透していると思われ、もうプログラマ向けには説明はほとんど必要がないと思われることを考えると、隔世の感がします。

さて、twitter で 2008 年 12 月 31 までの期間で競技プログラミングという言葉を検索してみると、その言葉が使われ始めた萌芽はあるものの、出てくるツイート数も少なく、まだ一部でしか浸透していないことがわかります。Google Trend で検索してみても、2004, 2005年になぜか突発的に「競技プログラミング」という言葉がトレンドに現れてはいるものの、2007年頃から継続的に現れ始めた言葉であることがわかります。

twitter のこれらの発言 1 2 をきっかけに「競技プログラミング」という単語のルーツを追ってみた結果、どうやら「東京大学競技プログラミングクラブ」という東大の勉強会が存在したことがわかりました。そしてそのクラブ名の名付け親である @ymatsux により、彼の思いつきが発端であるということがわかりました。

それであれば、自分は卒業しているため 2007 年にその言葉を知らず、一方後輩からその言葉を知ったおかげで広く知られる前から使い始めたということで、納得ができます。

なお、@nya3jp のツイートによると、「競技プログラミングクラブ」が発足したメーリングリストの一通目は 2007 年 3 月 30 日ということなので、この日が公の「競技プログラミング」発祥の日なのかもしれませんね。これから毎年祝いましょう。(追記: どうやら発足はもう少し前に遡れるようです。)

なお、英語の “competitive programming” ですが、Google scholar によると、2007 年よりも前からなくはなかったようです。この PDF によると、1999 年にはそのような講義 (CS3233 Competitive Programming in July 1999) があったことが示されています。ただ、ここから日本語の「競技プログラミング」が訳されたというよりは、独立に同じ言葉が生まれたと考えるのが適切ではないか、と考えています。


以下は 2019-07-28 にした追記です。

どうも、「競技プログラミング」という単語はもうちょっとだけ日付を遡れるようで。いわゆる仲間内での合宿(という名前の旅行)に「東京大学競技プログラミング同好会」と名前をつけたのが初出のようです。

というわけで、2007年3月21日には今の意味での「競技プログラミング」が始まっていたようです。

2019-07-25

異世界に転生しました

主に友人知人向けへの周知です。2019 年 3 月末で G を退職しています。

何か新しいことをやろうと思って水面下で様々準備していたのですが、事業を 0 から起こすというのは経営のスキルも足らずなかなか難しいなと攻めあぐねていたところ、前前職 (W) の上司の紹介で VISITS technologies の CTO 職をやってほしいという話になり、社長と話してみるとやりたかった事業ドメインに近かったため、引受けてみることにしました (万が一事業に失敗したらどこか拾ってください)。

いわゆる退職エントリはドラフトを長々と書いてみたのですが、書いた結果あんまり公にすることではないなと思ってお蔵入りにしました。積もる話は直接聞いてください。

現在丸の内勤務になったので、主に丸の内近辺の方(わかる範囲だとPFNとかTDとか)、遊んでください。ただ、G の頃より異常に忙しいので(これがスタートアップか)、なかなか時間取れないかもしれません。

こちらからは以上です。

2019-07-24
告知 

パスにおいて /a/b/../c と /a/c は等価か

今、分散コンパイラのキャッシュを作るようなお仕事をやっています。キャッシュを作るときには、キャッシュヒット率を上げるためにファイル名はなるべく正規化して持ちたいと思うことがしばしばあります。

コンパイラですと、-I で指定されたインクルードディレクトリ名とインクルードファイルを join してパスを得ることがあります。インクルードディレクトリやファイルが ../ を含んでいることは多分にあり、もし、../などを解決して絶対パス名にして保持できると、その後の扱いが楽にあります。例えば、パス名として /a/b/../c が与えられたとき、/a/c の形で保持できると少し嬉しいわけです。ファイルにアクセスすると遅いため、できればパス名だけでこのような正規化ができると嬉しいわけです。

さて、このような正規化をしてもいいのでしょうか。ダメだとするとどういう例があるでしょうか。

ダメそうな例として、b がどこかの directory への symlink である場合が考えられます。例えば /s/t への symlink であったとします。/a/b/../c を symlink を辿って解決すると、/s/c になり、/a/c とは違う場所を指しています。

実際、gcc で次のような ファイル構成および内容のとき、

a/b
  s/t への symlink
a/c.h
  #define KOTORI 100
s/c.h
  #define KOTORI 200
s/t
  空ディレクトリ
test.h
  #include <a/b/../c.h>
test.cc
  #include <stdio.h>
  #include <test.h>
  int main() { printf("%d\n", KOTORI); return 0; }

gcc -I. test.c として出来上がった実行ファイルは何を出力するでしょうか。symlink を解決していれば 200 が、解決されてなければ 100 が表示されるはずです。

$ gcc -I. test.c
$ ./a.out
200

実際は 200 となるため、symlink が解決されており、/a/b/../c/a/c は等価ではないという結論になりました。

一見 /a/b/../c/a/c にしたくなるのはわかりますが、これは悪魔の囁きです。

2017-06-05

王様達のヴァイキング×SECCON スペシャルトークセッション 終わりました

王様達のヴァイキングの技術監修役としてSECCON 2016 東京大会でちょっとしゃべってました。

まさか花が飾られているとは……。

普通 IT 系の勉強会だと技術がわかっている人が多いので、その人たち向けの前提知識で話します。今回もそんな感じでいいかなって思っていたのですが、当日どうも女性が結構登録しているらしいと聞いて、これは考えを改めねばと思いました。IT 系の勉強会では残念ながら女性は多くても数人です(女子向けは除く)。ということは、これは技術がわかっている人と、おそらく技術にはそんなに詳しくはないがマンガに詳しい人たちが混ざっている……となるわけです。

両方の人たちを満足させなければならないので、技術的な話とそうでない小ネタ(主に設定)を半々ぐらいのバランスで挟むことにしました。両方の人に満足していただけたのかどうかはわかりませんが、当日最初らへんのしゃべりで反応があった数人にターゲットを絞って、まあ彼・彼女らが満足してればよかろうというスタンスでしゃべっていて、最後までわりと満足そうな顔をしていたので良かったのだと思います。

2017-01-29
告知 

王様達のヴァイキング×SECCON スペシャルトークセッション

王様達のヴァイキングの技術監修役として SECCON 2016 東京大会でちょっとしゃべることになりました。2017年1月28日13:00-14:00に東京電機大学だそうで。

SECCON 2016 決勝大会

セキュリティに関してはどう考えても来場者の方がレベルが高いと思いますが、漫画の屋台骨を支える役にはなんとか立っていると思っています。

2017-01-16
告知 

コミットメッセージの書き方

ここ5年ほど pre commit review があるような環境(主に chromium とか)で働いてきたので、コミットメッセージの書き方を自分なりにまとめておきます。

コミットメッセージで伝えたいことはパッチのコンテキストである

コミットメッセージはコードレビュー依頼であるという態度で記述します(受け売り)。そのため、コードレビュー者がパッチのコンテキストを理解できるように記述するべきです。なにをやっているのか分からないパッチを渡されるより、これはこういう理由でこういう変更をやっているパッチだということを伝えてからパッチを見たほうが、パッチの理解も速いでしょう。レビュー者にパッチのコンテキストを理解してもらえれば、コードレビュー速度が上がったり、コードのミスが見つけてもらいやすくなるという利点があります。

コミットメッセージの基本的なフォーマット

コミットメッセージには一般的に使われる基本的なフォーマットがあり、それにそって記述します。

1行目

1行目はパッチのタイトルのようなものです。なるべく50文字以内で、何をしたのかや改良点を簡潔に書きます。git log --oneline ではここだけ出て来るので、何をやっているのかを簡潔に書きます。ぼくは tig を使って履歴を良く見ていますが、tig でも1行目が git log --oneline と同じように出ます。

Implement something to improve stability
Add something
Remove something

50文字を超えない程度なら、to improve stability のように、理由を入れることもあります。

個人的には Fix xxx とか Modify xxx とかはほとんど書きません。自明なので。もっと内容のあることを書きたいからです。

最初は大文字、ピリオドはなし、ということになっているようですので、(最近は)それを守っています。

あとぼくは基本的に英語で書きますが、日本人だけしかいないなら日本語でもいいと思います。OSS にしたいのなら、日本人としては残念ですが英語が標準語になってしまっているので、英語で書いてください。まともな高卒ぐらいの英語力があれば伝わるものは書けると思います。

2行目

2行目は空行です。

ツール類に1行目をタイトルだと認識してもらうため、必ず空行です。

3行目以降

ここからが本番です。まず、このパッチが解こうとしている問題が何なのかを述べるようにします。つまり、このパッチがなかったら、どういうまずいことが起こるのかをレビュー者に伝えます。

このパッチに対応するチケットに問題が詳細に書いてあっても、「このパッチで」解こうとしている問題を述べるようにします。レビュー者がチケットを丁寧に読んでくれると思ってはいけません。チケットに書かれている問題は少し複雑で、いくつかのパッチを積み重ねて解決できるものもあるでしょう。レビュー者には、その問題のどこを解こうとしているのかは(コードを読まなければ)わかりません。コミットメッセージはコードを読む前に読んでもらうもの、という前提なので、コードを読まないと理解できないようなことは原則的には書きません。

If parameter `id` is not provided, this function could raise an
Exception, and it's not handled at all.
This update() could take O(N^2) time in the worst case. N is around 10
in the usual case. However, N could be 100 at the worst case, and this
often happens. It is too slow.

基本的に 72 文字以内で改行することが良いことになっています。

問題がレビュー者に伝わったら、それを「どのように (how)」解こうとしているのかを述べます。

So, the existence of `id` must be checked in the controller.
So, I implement O(N log N) algorithm like merge sort.

付加情報

最後に、チケットへのリンクやバグ番号を入れておきます。chromium では BUG=123 の形式で書くようになっていますが、github なら #123 のように書きます。

BUG=123

書かなくて良いもの

3行目以降には、べつに「何を (what)」やっているかは詳細には書かなくていいです。それは1行目に完結にまとめてください。1行目に書く必要が無いような情報なら、書かなくていいです。コードを読む助けにはなりません。パッチを見ればわかります。「何をやっているか」はパッチを読めばわかりますが、「なぜやっているか」はパッチを見てもわかりません。ですので、「なぜ」を書いてください。

Add class A. Rename A to B.

例外

何事にも例外はつきものです。typo の fix とかは1行メッセージで済ませることもあります。

2017-01-15

rust で SIMD -- x86intrinsic を移植した話

これは rust advent calendar 2016 (2) の 1日目の記事です。

SIMD とは

SIMD (シムディー) とは、Single Instruction, Multiple Data の略で、1つの命令で(同じ種類の)演算を複数のデータに対して同時に行なうことを言います。

例えば、SSE2 には PADDW という命令があります。これはワード単位、すなわち、2byte 単位で加算を行なうという命令です。SSE では、16byte の幅を持つ xmm レジスタを用いて命令を発行することができます。この 16byte 幅のレジスタは、16x1byte, 8x2byte, 4x4byte, 2x8byte のように複数のデータをまとめたものとみなすことができます。PADDW 命令を xmm レジスタに対して発行すれば、2byte 単位の加算を一命令で 8 つ同時に行なうことができます。普通の CPU 命令は 1 つの命令に対して 1 つのデータしか演算を行わないので、単純には 8 倍速で加算が行えることになります。したがって、同じ演算を大量のデータに対して行なうときには、SIMD 命令を用いると高速に計算を行なうことができます。

rust で simd 演算

rust で SIMD 演算を行なうには、simd crate を使うのが今の所メジャーです。

一方、2016年11月現在、simd crate には AVX2 命令があまり実装されておらず、また SSE 命令にも実装されていないものがそこそこあります。筆者はちょうどこれらの命令が必要であったこと、および C/C++ において SIMD 命令を利用できる x86intrinsic 命令たちに慣れていたことから、rust で x86intrinsic と同様の関数群を持つ x86intrin crate を実装しました。現状 AVX2 まで、ごく一部の命令とMMX命令を除いて実装しています。一応私が必要な機能は全部揃ったので現状は満足しています。

x86intrin crate の使い方

x86intrin crate は、基本的に C/C++ での x86intrinsic から関数名、型名から先頭の _ を取り除いただけなので、C/C++ に慣れている人はすぐに使うことができると思います。ただし、nightly でしか動かないので、nightly を使ってください。

以下、C/C++ で x86intrinsic を使ったことがない人向けに説明します。

m128, m128d, m128i が xmm レジスタと同サイズ (16byte) のデータを表す型になります。それぞれ単精度浮動小数点数、倍精度浮動小数点数、整数を表すときに用います。単精度浮動小数点数は 4byte 、倍精度浮動小数点数は 8byte なので、xmm レジスタにはそれぞれ 4 つ、2 つのデータを同時に載せられます。整数は、1byte, 2byte, 4byte, 8byte のいずれかで、それぞれ 16, 8, 4, 2 個のデータを同時に載せることができます。

簡単な足し算

実際に簡単な足し算を計算してみます。今回、型はわざと明示しています。

extern crate x86intrin;

use x86intrin::*;

fn main() {
    // mm_setr_epi32(r0, r1, r2, r3) は、i32 を 4 つとって、m128i を作ります。
    // m128i の下位から r0, r1, r2, r3 が並びます。
    let a: m128i = mm_setr_epi32(1, 2, 3, 4);
    let b: m128i = mm_setr_epi32(4, 4, 4, 4);

    // 4x4byte を同時に足し算します。
    let c: m128i = mm_add_epi32(a, b);

    // ここは x86intrin の拡張で、as_i32x4().as_array() で、[i32; 4] な
    // 値を生成できます。println! とかには便利です。
    let vs: [i32; 4] = c.as_i32x4().as_array();
    println!("{} {} {} {}", vs[0], vs[1], vs[2], vs[3]);
}

これを実行すると、1 + 4, 2 + 4, 3 + 4, 4 + 4 が実行された結果である

と表示されます。

## アセンブラを見る

実際に SIMD 命令が使われているかアセンブラで確認してみましょう。

リリースビルドだと完全に定数畳み込みが行なわれて SIMD 命令が消えるので、次のように`#[inline(never)]` をつけてビルドしました。

rust extern crate x86intrin;

use x86intrin::*;

#[inline(never)] fn kotori(a: m128i, b: m128i) -> m128i { mm_add_epi32(a, b) }

fn main() { let a: m128i = mm_setr_epi32(1, 2, 3, 4); let b: m128i = mm_setr_epi32(4, 4, 4, 4); let c: m128i = kotori(a, b);

let vs: [i32; 4] = c.as_i32x4().as_array();
println!("{} {} {} {}", vs[0], vs[1], vs[2], vs[3]);

}


適当に関数を作って、あとは適当に `objdump -d` とかした後でその関数を見てあげると、`mm_add_epi32` に対応する `paddd` 命令が使われていることがわかります。

0000000100001260 <__ZN6intrin6kotori17hdacbdd83fa921175E>: 100001260: 55 push %rbp 100001261: 48 89 e5 mov %rsp,%rbp 100001264: 66 0f fe c1 paddd %xmm1,%xmm0 100001268: 5d pop %rbp 100001269: c3 retq 10000126a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)


なお、cargo でビルドするとき、デフォルトでは x64 の上では SSE2 命令までしか使えないので、次のように `RUSTFLAGS` を付加してください。`target-cpu=native` で自分の CPU が持っている命令が使えるようになります。

bash $ RUSTFLAGS=“-C target-cpu=native” cargo build –release


筆者は現在 Haswell という CPU を使っているので、AVX2 命令まで使えます。AVX2 まで使える場合、`mm_add_epi32` は、SSE2 の `paddd` ではなく AVX2 命令の `vpaddd` が代わりに使用されます。

0000000100001260 <__ZN6intrin6kotori17hdacbdd83fa921175E>: 100001260: 55 push %rbp 100001261: 48 89 e5 mov %rsp,%rbp 100001264: c5 f1 fe c0 vpaddd %xmm0,%xmm1,%xmm0 100001268: 5d pop %rbp 100001269: c3 retq 10000126a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)


# マンデルブローの実装

実際に x86intrin crate を用いてマンデルブロー集合を計算し、実際に高速になるか試してみます。

SIMD 演算を使わない naive 版、xmm レジスタを使った simd4 版、ymm レジスタ (32byte 幅) を使った simd8 版を用意しました。

長いのでソースは[こちらの gist]
(https://gist.github.com/mayah/fac2f92bb963c09166c19b2ad8b3dcbf) に。

手持ちの MacBook Pro Late 2013 (2.4 GHz Intel Core i5) での `RUSTFLAGS="-C target-cpu=native" cargo bench` の実行結果 (抜粋) がこちらです。なおこのマシンの CPU は Haswell です。

test mandel_naive … bench: 3,552,445 ns/iter (+/- 226,933) test mandel_simd4 … bench: 1,005,547 ns/iter (+/- 175,346) test mandel_simd8 … bench: 601,596 ns/iter (+/- 137,141) ```

simd4 版は 4 倍とまではいかないものの、3.5 倍ほど高速になっています。simd8 版も 6 倍ほど高速になっています。

4 倍や 8 倍にならなかった理由は、マンデルブロー集合は場所によって必要な計算回数が異なるので、同時に 4 点や 8 点計算する SIMD 版は、最も遅い点の部分に合わせて計算する必要があるため、というのが主な原因と考えていますが、ほかにも、通常命令と SSE, AVX 命令とでは IPC (Instructions Per Clock) が異なるなどの原因もあるでしょう。

x86intrin 実装の余談

以下は x86intrin crate を使いたいだけの人には余談です。

rust は LLVM の上に実装されています。LLVM のビットコードから x86 の命令へ変換するとき、LLVM 上の特定のビットコードの組み合わせを見ると対応する x86 命令を吐き出すという仕様になっています。そこで、一部の SIMD 命令を狙って吐き出すには、LLVM の気持ちになってあげる必要があります。

例えば、PANDN x, y という命令は、~x & y を計算するという命令ですが、これにそのまま対応するLLVMビットコード上の命令はありません。しかし、LLVM は、ones を全てのビットが 1 であるような値として (ones ^ x) & y に相当するLLVMビットコードを見つけると、PANDN 命令を出力するという実装になっています。これは LLVM の実装を知らないとわかりません。

また、SSE ファミリーの命令には、レジスタ内で値をコピーしたり順番を入れ替えたりする命令がありますが、ほとんどが rust が用意している simd_shuffle という platform-intrinsic で実装ができます。これも PANDN と同じで、LLVM が知っている simd_shuffle の引数を与えると対応する命令を吐き出すという形になっているため、clang に付属する emmintrin.h などのヘッダーを読んで simd_shuffle に対応する値を入れていきます。

そのほか、LLVM が用意している命令はバージョンアップとともにしばしば消え去り、より汎用的な命令で置き換えられている場合があります。例えば PALIGNR という命令を吐き出させるためには、一時は LLVM が用意している intrinsic (__builtin_ia32_palignr128 相当のもの) を呼び出せばよかったようで、手元の clang の header ではそうなっているようなのですが、気がついたら C/C++ 版は shuffle_vector (rust では simd_shuffle) を使う実装になっていました。このように、LLVM 側の変更を追わないと必要な実装ができないということが何度かありました。

安定化に向けて

先々週あたりから SIMD を安定版 rust で提供するためにどういう方向で実装していくかについて、長いスレッドで議論が交わされています。

https://internals.rust-lang.org/t/getting-explicit-simd-on-stable-rust/4380

まあ大方の予想通り、simd crate のような type safe な SIMD を提供するような意見が主流を占めていると(ざっと読んだ限りでは)思います。早く安定化してほしいですね。

2016-12-01

OpenBLASが速かった

ちょっと行列演算をしたかったので適当にコードを書き散らしていたのですが、速度が必要な演算であるために既成のライブラリを使うこととしました。今回は行列乗算ができれば良いのでBLASを生で使ってもそんなに問題ありません。BLASの中でも高速な実装であるOpenBLASを使い、適当に書いたコードと速度の比較をしてみます。

結論から言うと、OpenBLASの速さを舐めてました。まさか50倍の速度差がでるとは。

比較に用いたマシンは、MacBook Pro 2013 Late 13 inch (2.4 GHz Intel Core i5) です。

インストール

Macの場合はbrewで。LinuxでもOpenBLASのパッケージはたいていのディストリビューションにはあると思います。

$ brew install homebrew/science/openblas

Matrix クラス

1024 × 1024の大きさの実正方行列の掛け算をします。以下N = 1024とします。

const int N = 1024;

適当にMatrixクラスを定義します。精度はそこそこで良いので今回はfloatを使います。

class Matrix {
public:
    Matrix(int row_size, int col_size) :
        row_size_(row_size),
        col_size_(col_size),
        data_(new float[row_size * col_size]) {}

    float& operator()(int row, int col) { return data_[row * col_size_ + col]; }
    const float& operator()(int row, int col) const { return data_[row * col_size_ + col]; }

    float* data() { return data_.get(); }
    const float* data() const { return data_.get(); }

private:
    int row_size_;
    int col_size_;
    unique_ptr<float[]> data_;
};

operator()を定義していて、行列Ai行目j列にはA(i, j)でアクセスできるようにしておきます。

1024 × 1024 の行列 A, B を掛け算し、C = ABを計算するものとします。C++の変数としては小文字a, b, cを用いて次のように表すとします。

Matrix a(N, N);
Matrix b(N, N);
Matrix c(N, N);

ナイーブに掛け算をした場合

ナイーブに実装すると次のようになるでしょう。

for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        float s = 0;
        for (int k = 0; k < N; ++k) {
            s += a(i, k) * b(k, j);
        }
        c(i, j) = s;
    }
}

この場合、b(k, j)の部分がメモリを飛び飛びにアクセスすることになるので速度はでません。clang -O3で試すと、おおよそ6〜7秒程度の時間がかかります。

乗算順序を変更

i, j, kの順序でアクセスするのではなく、i, k, jの順でアクセスするとメモリアクセスが飛び飛びにならないのでいくらか速度が稼げます。 ただしc(i, j)は0で初期化しておく必要があります。

for (int i = 0; i < N; ++i) {
    for (int k = 0; k < N; ++k) {
        for (int j = 0; j < N; ++j) {
            c(i, j) += a(i, k) * b(k, j);
        }
    }
}

これでおよそ1.1〜1.2秒ぐらいです。演算回数としては10243なので1G回の演算があるわけですが、2.4GHzのCPUで1.2秒となると、まあちょっと遅いですねという気持ちになります。

OpenBLAS の場合

関数cblas_sgemmを使います。cblas_sgemmは、行列A, B, Cとスカラーα, βαAB + βCを計算します。計算結果はCに格納されます。単に掛け算ABを計算したければ、βを0とすれば良いでしょう。

cblas_sgemmの引数はちょっと見ただけではわかりづらいです。

行列の要素はメモリ上では行ごとに並んでいるので、CblasRowMajorを指定する必要があります。FORTRANなどではメモリ上は列ごとにならべるのが普通ですがC/C++では行ごとにならべるのが普通です。また、cblas_sgemmでは転置してから行列を掛け算することもできます。今回は転置などせずに掛け算するので、CblasNoTransを指定します。

cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans,
    N, N, N,
    1, a.data(), N,
    b.data(), N,
    0, c.data(), N);

これの計算時間はわずか0.03秒でした。

ちなみにEigenでも同じような計算をしてみたのですが、こちらは0.11秒程度でした。それでも速いですね。

2016-01-17

ぷよぷよ AI

実機で動作するぷよぷよAIというものをしばらく有志で作っておりました。プロジェクトはgithub.com/puyoaiで公開しています。

これに関連するイベントを今までいくつか開いています。

また、先日行なわれたゲームプログラミングワークショップ 2015 (GPW-15)というワークショップで招待講演としてぷよぷよAI 人類打倒に向けてというタイトルで発表しました。スライドはリンク先の slideshare にアップロードしてあります。

2015-11-10

王様達のヴァイキングの監修について

なぜこんな仕事を?

簡単に言うと、深見先生に頼まれたから、です。

もともと、競技プログラミングのマンガを描こうという話が2005年ぐらいからありました。しかし、詳細を詰めるのが難しく、一度ネームもできたものの掲載には至りませんでした(注: 私が描いたのではありません)。このときの色々な縁で深見先生とは親しくなりました(注: 競技プログラミングマンガと深見先生は直接は関係ありません)。深見先生に王様達のヴァイキングの話がきたときに、せっかくだから我々とやりたいということで話が回ってきたものです。

ただ、話が回ってきたときには6話ぐらいは話が固まっていて、また、もともとの監修は sotarok と ozarn だけに回っていました。今がそうでないとは言いませんが、最初の頃はもっと起業ものっぽい雰囲気を醸し出していたでしょう?

深見先生が協力として入ることになった後に、旧知の仲である我々にも回ってきました。そのときはちょっと画像を提供するぐらいの話でしたし、そのつもりでいました。また、もっと監修は人がいました。具体的には、YUHAのメンバーと、Gokuriのメンバー、などです。だから、そんなに負担にならないと考えました。ただ、徐々に監修は人を減らしていきました。これはそこまで仕事がなくなったというのが大きいのと、あまり多人数いても意見だけが出てまとまらないためです。人が減ったとはいえ、あまり負担は変わっていません。マンガを読んで育ってきたので、一作関われるというのも良い機会だな、と思って楽しんで協力しています。

何をやっているのか?

技術的詳細を考えることです。

基本的に、話はさだやす先生が作ります。それを受けて、事件などを深見先生が作ります。しかし、そこには技術的な詳細は書かれていません。そこで、例えば「ハッキングをする」と書かれてある部分の技術的な詳細を考え、仮のセリフをいくつか挟む形にまで落とし、その詳細を平易な日本語でさだやす先生、深見先生、および担当の山内さんに説明します。なるべく、話も読者に分かりやすい展開になるように僕は心がけています。テクニカルには別の手段を使ったほうが良い技術でも、今後の展開および、マンガとしての要請のために別の技術を敢えて用いることもあります。これは詳しい人からはツッコまれますが、それは覚悟の上です。また、マンガの上では詳細はかけません。かいても難しすぎるだけだからです。

ハッキングの技術的難易度を調整するのは難しいのですが、私が見ている分に関しては、最低でも「理論的にはできる」話にしてあります。ほとんどの場合、それを実際にやったことがある人を聞いたことがあるものを採用しています。Windows のバイナリパッチを作った話なんかは、実際にそういう人がいるという話を聞いたので、じゃあいいだろうということで通してあります。また、過去に似たようなハッキング事例があれば、それを参考に技術的詳細を詰めたりします。大体5割ぐらいの技術的詳細は僕が決めていると思いますが、週に数時間程度の時間でだいたいなんとかなっています。

2014-08-14