はむこの勉強記録

http://bit.ly/2ktf20t の写し

yukicoderで並列計算プログラム書いても無駄だよって話 - Millions of Submits! TLE解

概要

yukicoderで並列計算して定数倍高速化できないかなあ、と思って実際にやってみたけど時間計測がCPU timeなのでダメでした。yukicoderのC++コンパイルは並列計算ライブラリをリンクするオプションが無いから、闇魔法を使ってごにょごにょしたのに、悲しい。

#173906 No.456 Millions of Submits! - yukicoder

何をしたか

Millions of Submits!は100万個の独立なクエリを処理する問題です。なので、並列処理がよく効くかな、と思って実装しようとしました。

No.456 Millions of Submits! - yukicoder

C++で並列計算するためには、(1) pthread (2) C++11以上のstd::thread (3) C++17のpar指示したreductionのどれかがお手頃です。

(1) pthread

結論、(1)でゴリ押しました。

そもそもyukicoderのC++コンパイルは並列計算ライブラリをリンクするオプションをつけていません。従って、pthreadもC++のthreadも何も動きません。どうしましょうか?

解決策として、具体的には、C++11から__stdcallなどを使って動的ライブラリを叩く黒魔術を駆使して、yukicoderのジャッジサーバのlibpthreadを直叩きしました。 結果、実装して並列化はできましたが、TLEしました。これは測定が実時間ではなくCPU時間であることが理由です。

#173906 No.456 Millions of Submits! - yukicoder

(2) C++11以上のstd::thread

pthreadをリンクしていない状態では、何故かCEではなく、pthreadを使おうとした時にREするという謎仕様により、REしました。

この後、bits/stdc++.hのpthread系の関数をdefineで全部自前関数に置き換えようとしましたが、無理そうなので諦めました。

#173861 No.456 Millions of Submits! - yukicoder

ちなみにC++17以上だとそもそもCEします。

#173862 No.456 Millions of Submits! - yukicoder

(3) C++17のpar

そもそもCEするので提出すらしていません。

要するに

並列化コンテストじゃないコンテストで並列化するのはやめましょう。