オンラインジャッジでの並列実行

シリーズ：掃き出し法について	URL
問題：十文字に反転して色を揃えて！(最短手数の最大化)	https://codeiq.jp/q/2972
single/OpenMP	https://qiita.com/cielavenir/items/2fa1f1149132de579a46
std::async	https://qiita.com/cielavenir/items/61b329936ef6508a5938
番外編：オンラインジャッジで並列実行は使えるか？	https://qiita.com/cielavenir/items/ade2b7c0b5a63b2687f0
問題：裏表ちわーわ(解の存在判定)	http://yukicoder.me/problems/no/460 https://www.codeeval.com/public_sc/191/
解説	https://qiita.com/cielavenir/items/c6b15ff4e28fb5f492ec

2記事に渡って、OpenMPとC++11標準での並列実行について扱った。

• さて、C++11標準の並列実行があるならば、オンラインジャッジで使ってみたくなる。
• しかし、ideone(CodeIQ)、paiza.io、Codeforcesでは通用するが、AtCoder(のコードテスト)やyukicoderでは通用しなかった。
• これは、Linuxではasync機能は-lpthreadオプションに依存するためである。コンパイルオプションをこちらから変更することはできず、また、libpthread.soはdlopen()できるものではないらしいので、どうすることもできない。

標準でできる言語

• Go言語のgoroutineおよびD言語のstd.parallelismは、コンパイルオプションによらずいつでも行うことができる並列化方法である。
• しかし、ベンチマークを取ったところ、GoやDはC++の2〜3倍ほど遅いので、オンラインジャッジのCPUが良くて4コアと思われることを考えると、C++をやめる理由にはならなそうである。

フィズバズ・エクストリーム問題のナイーブ解	MacBookAir Core i7 2x2cores
C (OpenMP)	22.8s (CPU 83.8s)
C++ (async)	26.6s (CPU 83.6s)
Go	30.3s (CPU 95.7s)
D	104.4s (CPU 196.7s)

Dはかなり厳しいが、Goは奮闘している。

Goでの答案を、ABC033D 三角形の分類で試したくなるもの。
実際に試したところ、残念ながらTLEに終わったが、1.5倍ほど高速化されていることが明らかになった。

• single https://abc033.contest.atcoder.jp/submissions/910523
• parallel https://abc033.contest.atcoder.jp/submissions/910521
  • コードテストのcat /proc/cpuinfo|grep processorによると、コア数は2であるようだ。

問題によるが、最終手段として使ってみるのもありかも、しれない。