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
#173862 No.456 Millions of Submits! - yukicoder
(3) C++17のpar
そもそもCEするので提出すらしていません。
要するに
並列化コンテストじゃないコンテストで並列化するのはやめましょう。