usakdsteen

ゆうさくですてぃーん

TCMM速度試す(ループ回数見るだけ)

MM97にて.NETが糞遅い疑惑があったのでPracticeの適当な問題使ってお試す

C++/Java/C#/VB.NET/Python それぞれお試すが、どれもあまりよく知らないいプログラミング言語なのでダメコードジェネレーションかもだが…

 

(本記事は個人的メモであり、十分な検証を行うようなものでもない)

 

追記(2019-04-12):

 この記事書いたときは.NETのジャッジが壊れていただけっぽくて

現在はJavaなどとほぼ同等に動く

 

 

 

Pracitceと本番鯖が同じスペックなのかは分からんが

TCMMの本番鯖スペックはこれ(閲覧は要ログインらしい)

https://apps.topcoder.com/wiki/display/tc/Processing+server+specifications+(AWS)

gcc4.8/java7/VS2010(C#/VB.NET)/Python2.6 ということらしい

gccはsse系やmmx?のcpuの拡張命令(?)を使えるらしい、64bitマシンぽさげ

 

使用する問題

使用する問題はMM26のPermute、入力・出力・スコア計算が色々と楽そうなので選んだナリ…

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=11148&pm=8426

0~N-1の順列pを生成して返す問題で

コストの配列wが渡されるので次のスコア計算の結果が最大になるように順列pを生成する

double calc_score(int n, vector<double> w, vector<int> p) {
    double score = 0.0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
             score += w[p[i] * n + p[j]];

        }

    }
     score /= n * sqrt(n * log(n) - n) / 100;
     return score;
}

コスト wはn*nのテーブルを1次元配列にしたもので

標準分散(?)の乱数で各値が生成されてて(0を中央値として正負の値があって、絶対値も1以上の値がいっぱいある)

w[a,a] は常に0で、w[a,b]とw[b,a]は別々に生成されるから異なる値、という感じ??

nは100~1000 (サンプルケースは100未満もあるけど)

んで、実行時間の制限は最大30秒

(なお、公式テスターなどは無い…)

 

やること

Test Examplesでコードを提出してループ回数を標準エラーに吐かせて調べる

 

今回は単純に貪欲法で山登り法で書いた

順列の2個を交換してスコアが上がるなら交換しそうでないなら交換しない、2個の組み合わせ総当りで、これを可能な限り何度も繰り返す、と

 

んで、

  • 時間取得を用いてギリギリの29.8秒使ったときのループ回数、
  • その結果を元にループ回数を指定し時間取得処理を抜いたときの実行時間
  • その実行時間を元に(最大ケースで)29.8秒ギリギリのループ回数を探る(これは時間取得処理が重かった場合に限るが…)

 これを各言語で試す、と

(ループ回数はLoopCountじゃなくCycleとかIterationとか言ったりするの?知らんけど)

そんでもって最大ケースのループ回数の言語ごとの違い を見てみる、と

 

Python

Pythonのコードはほとんど書いたことないので、微妙かもだが

 まず時間取得あり

https://gist.github.com/neetsdkasu/00f81c079e01e5f7da1fefad2a8ee127

0) N=3, Score=74.998, Time=29824ms, Loop=88541

1) N=5, Score=72.050, Time=29822ms, Loop=88632

2) N=10, Score=55.439, Time=29823ms, Loop=86996

3) N=20, Score=43.049 Time=29823ms, Loop=88131

4) N=50, Score=37.379, Time=29822ms, Loop=81839

5) N=159, Score=37.379, Time=29823ms, Loop=81839

6) N=992, Score=5.9239, Time=29823ms, Loop=51965

7) N=290, Score=30.266, Time=29823ms, Loop=77619

8) N=352, Score=26.400, Time=29824ms, Loop=75037

9) N=1000, Score=2.9590, Time=29823ms, Loop=52949

 という結果に、平均すると77,354回のループになる

ひとまず時間切れしなさそうな50,000回ループで試してみる

https://gist.github.com/neetsdkasu/2f270f940505042eb21a7a0f1ca97b8c

0) N=3, Score=74.998, Time=70ms, Loop=50000
1) N=5, Score=72.050, Time=83ms, Loop=50000
2) N=10, Score=55.439, Time=107ms, Loop=50000
3) N=20, Score=41.470, Time=164ms, Loop=50000
4) N=50, Score=43.049 Time=332ms, Loop=50000
5) N=159, Score=36.837, Time=950ms, Loop=50000
6) N=992, Score=5.8198, Time=10779ms, Loop=50000
7) N=290, Score=26.743, Time=1791ms, Loop=50000
8) N=352, Score=22.580, Time=2332ms, Loop=50000
9) N=1000, Score=2.7565, Time=10651ms, Loop=50000

時間取得処理やばかった(まぁ1ループごとに時間取得してたから当たり前だが)

N=1000で10秒強だから30秒制限なら3倍弱くらいはループできそう?

 ひとまず無難に140,000回ループで試してみる

https://gist.github.com/neetsdkasu/dc4c9d90e487557747db22ec3c7f9051

0) N=3, Score=74.998, Time=156ms, Loop=140000
1) N=5, Score=72.050, Time=185ms, Loop=140000
2) N=10, Score=55.439, Time=261ms, Loop=140000
3) N=20, Score=41.470, Time=421ms, Loop=140000
4) N=50, Score=43.049 Time=887ms, Loop=140000
5) N=159, Score=37.379, Time=2635ms, Loop=140000
6) N=992, Score=10.982, Time=28396ms, Loop=140000
7) N=290, Score=34.164, Time=4872ms, Loop=140000
8) N=352, Score=32.890, Time=7067ms, Loop=140000
9) N=1000, Score=8.7286, Time=28001ms, Loop=140000

結構ギリギリぽい(?)

つか、流石に最初のコードの時間関数の呼び出し方悪いので1,024回ループごとに呼び出すよう変えてみる…

https://gist.github.com/neetsdkasu/e591781410ddf7bbc9bff7e5cd4afd00

0) N=3, Score=74.998, Time=29824ms, Loop=23204864
1) N=5, Score=72.050, Time=29824ms, Loop=19769344
2) N=10, Score=55.439, Time=29824ms, Loop=14669824
3) N=20, Score=41.470, Time=29825ms, Loop=8942592
4) N=50, Score=43.049 Time=29824ms, Loop=4523008
5) N=159, Score=37.379, Time=29824ms, Loop=1586176
6) N=992, Score=11.512, Time=29833ms, Loop=149504
7) N=290, Score=36.120, Time=29828ms, Loop=874496
8) N=352, Score=36.350, Time=29844ms, Loop=712704
9) N=1000, Score=9.3283, Time=29935ms, Loop=148480

普通に十分なループ回数が出たわ(時間ヤバいのあるし、テストケース次第で死ぬかも)

結論としては呼び出し方を工夫すれば時間取得処理は使えなくもなさそう

Pythonの最大ケースのループ回数は148,480

そのコードをFullSubmissionに投じたスコアは2706.25

 

VB.NET

ここずっとTCでは使い続けてるVB.NETを見てみる

 ということで、まず時間取得ありを…

https://gist.github.com/neetsdkasu/87279eb55178c6718cdd22c0c40335ab

0) N=3, Score=74.998, Time=29826ms, Loop=3190893940
1) N=5, Score=72.050, Time=29811ms, Loop=1163473137
2) N=10, Score=54.439, Time=29811ms, Loop=755313899
3) N=20, Score=41.470, Time=29813ms, Loop=429764686
4) N=50, Score=43.049 Time=29826ms, Loop=412164009
5) N=159, Score=37.379, Time=29829ms, Loop=59440853
6) N=992, Score=33.270, Time=29811ms, Loop=2472969
7) N=290, Score=36.120, Time=29811ms, Loop=24825300
8) N=352, Score=36.350, Time=29826ms, Loop=43160071
9) N=1000, Score=31.703, Time=29829ms, Loop=2355791

Pythonの10倍以上のループ回数出たのだが…(第0ケースでループカウンタがIntegerでオーバーフローしたのでLongに変えたし)

Nの大きさに応じてループ回数も変動しているから、時間取得処理は大したコストはなさそう?

ひとまず時間取得処理を抜いて2,300,000回ループのコードを投げて最大ケースの時間を見てみる

https://gist.github.com/neetsdkasu/0c244bca7192e79dc5b56f44b86535f9

0) N=3, Score=74.998, Time=62ms, Loop=2300000
1) N=5, Score=72.050, Time=46ms, Loop=2300000
2) N=10, Score=55.439, Time=46ms, Loop=2300000
3) N=20, Score=41.470, Time=156ms, Loop=2300000
4) N=50, Score=43.049 Time=171ms, Loop=2300000
5) N=159, Score=37.379, Time=1185ms, Loop=2300000
6) N=992, Score=32.994, Time=28440ms, Loop=2300000
7) N=290, Score=36.120, Time=2620ms, Loop=2300000
8) N=352, Score=36.350, Time=1544ms, Loop=2300000
9) N=1000, Score=31.645, Time=29531ms, Loop=2300000

最大ケースからも察するに時間取得のコストは低そう

時間取得コスト低そうだが念のためループ8,192回ごとの時間取得コードに直して試してみる

https://gist.github.com/neetsdkasu/5fda5d5c8ae13dbf8b7d5ff162d87fa7

0) N=3, Score=74.998, Time=29827ms, Loop=1754275840
1) N=5, Score=72.050, Time=29811ms, Loop=2984288256
2) N=10, Score=55.439, Time=29812ms, Loop=833634304
3) N=20, Score=41.470, Time=29827ms, Loop=454721536
4) N=50, Score=43.049 Time=29811ms, Loop=419487744
5) N=159, Score=37.379, Time=29827ms, Loop=61087744
6) N=992, Score=33.274, Time=29874ms, Loop=2506752
7) N=290, Score=36.120, Time=29827ms, Loop=25411584
8) N=352, Score=36.350, Time=29811ms, Loop=43507712
9) N=1000, Score=31.734, Time=29843ms, Loop=2375680

うーん、微増感はあるけど、Nの大きいケースで実行時間も微増なのが、微増なの誤差の可能性も。

時間取得は比較的ローコストで呼び出し気にする必要は無さそう

VB.NETは最大ケースのループ回数は2,375,680

 そのコードをFullSubmissionに投じたスコアは3471.81

 

追記(2019-04-12):

現在は十分なループ回数出る模様

0) N=3, Score=74.998, Time=29810ms, Loop=3705946112
1) N=5, Score=72.050, Time=29804ms, Loop=2864545792
2) N=10, Score=55.439, Time=29812ms, Loop=1777934336
3) N=20, Score=41.469, Time=29826ms, Loop=996352000
4) N=50, Score=43.048, Time=29814ms, Loop=414998528
5) N=159, Score=37.378, Time=29810ms, Loop=134504448
6) N=992, Score=34.032, Time=29816ms, Loop=5382144
7) N=290, Score=36.120, Time=29826ms, Loop=57212928
8) N=352, Score=36.350, Time=29826ms, Loop=44032000
9) N=1000, Score=32.320, Time=29812ms, Loop=5210112

 

f

C#

VB.NETとはコンパイルのされ方(最適化?)が違いそうな気がするがそんなに速度に変わりはないと予想

C#はほとんど書いたことない、Pythonよりも使用頻度が低い

まずは毎ループ時間取得処理するやつ

https://gist.github.com/neetsdkasu/d47c1a96b5f9000f6724637588403352

0) N=3, Score=74.998, Time=29811ms, Loop=4152293946
1) N=5, Score=72.050, Time=29812ms, Loop=1570299944
2) N=10, Score=54.439, Time=29811ms, Loop=973667521
3) N=20, Score=41.470, Time=29827ms, Loop=540840776
4) N=50, Score=43.049 Time=29811ms, Loop=508331710
5) N=159, Score=37.379, Time=29811ms, Loop=73057603
6) N=992, Score=33.275, Time=29811ms, Loop=2511412
7) N=290, Score=36.120, Time=29812ms, Loop=31080464
8) N=352, Score=36.350, Time=29811ms, Loop=53427298
9) N=1000, Score=31.832, Time=29827ms, Loop=2449204

ループ回数は VB.NETより少し多い感じになった

(当たり前だが)こちらもVB.NETと同様に時間取得のコストが低そう

まぁ念のため一応は時間取得なしで2,400,000回ループのコードも試す

https://gist.github.com/neetsdkasu/ed06dc75de77c2a0a5efd5230c5a7a1f

0) N=3, Score=74.998, Time=46ms, Loop=2400000
1) N=5, Score=72.050, Time=31ms, Loop=2400000
2) N=10, Score=55.439, Time=31ms, Loop=2400000
3) N=20, Score=41.470, Time=124ms, Loop=2400000
4) N=50, Score=43.049 Time=140ms, Loop=2400000
5) N=159, Score=37.379, Time=936ms, Loop=2400000
6) N=992, Score=33.131, Time=28579ms, Loop=2400000
7) N=290, Score=36.120, Time=2386ms, Loop=2400000
8) N=352, Score=36.350, Time=1310ms, Loop=2400000
9) N=1000, Score=31.762, Time=29374ms, Loop=2400000

VB.NETよりは少し高速らしい(2,300,000回のVB.NETより時間少し短い)

VB.NET同様に時間取得コストが低いらしいことを感じる結果

こちらもVB.NET同様にループ8,192回ごとの時間取得コードに直して試してみる

https://gist.github.com/neetsdkasu/33d648b9841d6de3948d9563695ef411

0) N=3, Score=74.998, Time=29811ms, Loop=2751905792
1) N=5, Score=72.050, Time=29811ms, Loop=4374724608
2) N=10, Score=55.439, Time=29811ms, Loop=1107861504
3) N=20, Score=41.470, Time=29827ms, Loop=580902912
4) N=50, Score=43.049 Time=29811ms, Loop=522706944
5) N=159, Score=37.379, Time=29827ms, Loop=75120640
6) N=992, Score=33.275, Time=29967ms, Loop=2498560
7) N=290, Score=36.120, Time=29811ms, Loop=31531008
8) N=352, Score=36.350, Time=29811ms, Loop=53878784
9) N=1000, Score=31.926, Time=29843ms, Loop=2506752

少しだけループ回数増えたけど、実行時間がやばいとこがあるので微妙…

収穫としては同じ.NET FrameworkなのにC#VB.NETより少し速いことが分かった

C#の最大ケースのループ回数は2,506,752

 そのコードをFullSubmissionに投じたスコアは3472.17

 

追記(2019-04-12):

ジャッジが直って速度十分

0) N=3, Score=74.998, Time=29810ms, Loop=6089621504
1) N=5, Score=72.050, Time=29803ms, Loop=4327096320
2) N=10, Score=55.439, Time=29813ms, Loop=2427166720
3) N=20, Score=41.469, Time=29810ms, Loop=1273331712
4) N=50, Score=43.048, Time=29812ms, Loop=517480448
5) N=159, Score=37.378, Time=29810ms, Loop=165462016
6) N=992, Score=34.032, Time=29806ms, Loop=5464064
7) N=290, Score=36.120, Time=29810ms, Loop=70885376
8) N=352, Score=36.350, Time=29826ms, Loop=54640640
9) N=1000, Score=32.326, Time=29803ms, Loop=5308416

 

 

 

Java

今はTCで使うことないが我が人生で二番目か三番目くらいに使っているはずなのがJava

(ちなみに、同じく二番目か三番目くらいのもう一つはJavaScript、一番目はおそらくVB6)

仮想マシンである JVM上で動くわけだがJITコンパイル次第では高速になるのだろうか?

C#VB.NETと同程度だと予想してるけど、どうなんだろう?

ひとまず毎ループ時間取得処理するやつ投げる

https://gist.github.com/neetsdkasu/087407544de6d36ec6a692abaadbc5f7

0) N=3, Score=74.998, Time=29806ms, Loop=35615703
1) N=5, Score=72.050, Time=29806ms, Loop=33983875
2) N=10, Score=55.439, Time=29806ms, Loop=35042518
3) N=20, Score=41.470, Time=29806ms, Loop=34597308
4) N=50, Score=43.049 Time=29806ms, Loop=33531726
5) N=159, Score=37.379, Time=29805ms, Loop=29504071
6) N=992, Score=34.009, Time=29807ms, Loop=4720155
7) N=290, Score=36.120, Time=29806ms, Loop=23456236
8) N=352, Score=36.350, Time=29806ms, Loop=20991632
9) N=1000, Score=32.313, Time=29807ms, Loop=4697661

は?何これ?.NET Framework捨てるは!?

 Nの大きいケース、明らかにVB.NETC#よりループ回数多いぞ

逆にNの小さいケースではループ回数が少ない

察するに時間取得処理が重いのだと予想される

なので時間取得処理抜いて4,600,00ループのコードを試す

https://gist.github.com/neetsdkasu/025be43ab776d506428ffa0504aa2e18

0) N=3, Score=74.998, Time=49ms, Loop=4600000
1) N=5, Score=72.050, Time=69ms, Loop=4600000
2) N=10, Score=55.439, Time=96ms, Loop=4600000
3) N=20, Score=41.470, Time=138ms, Loop=4600000
4) N=50, Score=43.049 Time=252ms, Loop=4600000
5) N=159, Score=37.379, Time=675ms, Loop=4600000
6) N=992, Score=34.001, Time=23080ms, Loop=4600000
7) N=290, Score=36.120, Time=1626ms, Loop=4600000
8) N=352, Score=36.350, Time=2137ms, Loop=4600000
9) N=1000, Score=32.133, Time=23305ms, Loop=4600000

 多少余裕があるように見える、時間取得処理はやはり重かったようだ

概算だと最大ケースでは5,800,000ループ行けそうな気がするので試す

https://gist.github.com/neetsdkasu/a9b0161139c1ac2a3dcc153afb6f7656

0) N=3, Score=74.998, Time=57ms, Loop=5800000
1) N=5, Score=72.050, Time=73ms, Loop=5800000
2) N=10, Score=55.439, Time=112ms, Loop=5800000
3) N=20, Score=41.470, Time=154ms, Loop=5800000
4) N=50, Score=43.049 Time=305ms, Loop=5800000
5) N=159, Score=37.379, Time=875ms, Loop=5800000
6) N=992, Score=34.035, Time=29284ms, Loop=5800000
7) N=290, Score=36.120, Time=2135ms, Loop=5800000
8) N=352, Score=36.350, Time=2681ms, Loop=5800000
9) N=1000, Score=32.330, Time=29932ms, Loop=5800000

時間ギリギリだった…フルサブミットしたらやばそう…

他と同様にこちらでもループ8,192回ごとの時間取得コードに直して試してみる

https://gist.github.com/neetsdkasu/8c4a41726f675e6e4c76eef672ce5411

0) N=3, Score=74.998, Time=29805ms, Loop=5006229504
1) N=5, Score=72.050, Time=29806ms, Loop=3115286528
2) N=10, Score=55.439, Time=29806ms, Loop=2148990976
3) N=20, Score=41.470, Time=29805ms, Loop=1511194624
4) N=50, Score=43.049 Time=29805ms, Loop=620257280
5) N=159, Score=37.379, Time=29807ms, Loop=195919872
6) N=992, Score=34.035, Time=29853ms, Loop=6094848
7) N=290, Score=36.120, Time=29809ms, Loop=79470592
8) N=352, Score=36.350, Time=29807ms, Loop=59940864
9) N=1000, Score=32.330, Time=29847ms, Loop=5775360

十分なループ回数出た…たまたまかもしれんが時間にもゆとりあるし…

最後のコードが最適解とみなして、Javaの最大ケースのループ回数は5,775,360

 そのコードをFullSubmissionに投じたスコアは3475.93

 

C++

さて、いよいよ最強最速のC++

最速だって分かってるから調べる必要もないかもしれんが

 まず毎ループ時間取得で調べてみるが

 

時間取得には Approaching Marathon Match Task, Pt. 1 -  で紹介されている アセンブルのrdtsc命令を使うやり方で行う

(その記事でstd::chrono::system_clock::now()はTC鯖では使えないと書いてある。またrdtsc命令はLinuxcygwinで使えると書いてある。ローカルではVisualStudioのC++で動かしてるのでstd::chrono::system_clock::now()を使ってる)

https://gist.github.com/neetsdkasu/ea9ddeab1af92a741a445437d5a53b0c

0) N=3, Score=74.998, Time=29803ms, Loop=2384677712
1) N=5, Score=72.050, Time=29874ms, Loop=2241754659
2) N=10, Score=55.439, Time=29802ms, Loop=1851000585
3) N=20, Score=41.470, Time=29802ms, Loop=1258444726
4) N=50, Score=43.049 Time=29803ms, Loop=618405799
5) N=159, Score=37.379, Time=29875ms, Loop=195470988
6) N=992, Score=34.035, Time=29817ms, Loop=6051491
7) N=290, Score=36.120, Time=29804ms, Loop=85707160
8) N=352, Score=36.350, Time=29806ms, Loop=64810491
9) N=1000, Score=32.332, Time=29816ms, Loop=5889738

うん?C++のくせにJavaと同等か少し速い程度の結果に…これは謎(むしろJVMがすごいのか?)

一応、時間取得なしの5,800,000回ループのコードでも試す

https://gist.github.com/neetsdkasu/b36fd722a039a6bd6ca08cc5fd8b5508

0) N=3, Score=74.998, Time=30ms, Loop=5800000
1) N=5, Score=72.050, Time=40ms, Loop=5800000
2) N=10, Score=55.439, Time=63ms, Loop=5800000
3) N=20, Score=41.470, Time=107ms, Loop=5800000
4) N=50, Score=43.049 Time=249ms, Loop=5800000
5) N=159, Score=37.379, Time=803ms, Loop=5800000
6) N=992, Score=34.035, Time=28975ms, Loop=5800000
7) N=290, Score=36.120, Time=1942ms, Loop=5800000
8) N=352, Score=36.350, Time=2583ms, Loop=5800000
9) N=1000, Score=32.330, Time=29766ms, Loop=5800000 

ギリギリになった…さすがアセンブル命令での時間取得コストはほぼ無しということか?

最後にループ8,192回ごとの時間取得コードに直して試してみる

https://gist.github.com/neetsdkasu/08273c9043ff197e40649a13402f880f

0) N=3, Score=74.998, Time=29803ms, Loop=6328467456
1) N=5, Score=72.050, Time=29802ms, Loop=4693753856
2) N=10, Score=55.439, Time=29801ms, Loop=2919841792
3) N=20, Score=41.470, Time=29874ms, Loop=1653735424
4) N=50, Score=43.049 Time=29874ms, Loop=718413824
5) N=159, Score=37.379, Time=29805ms, Loop=214761472
6) N=992, Score=34.035, Time=29865ms, Loop=6029312
7) N=290, Score=36.120, Time=29804ms, Loop=89014272
8) N=352, Score=36.350, Time=29806ms, Loop=67715072
9) N=1000, Score=32.330, Time=29894ms, Loop=5758976

謎めいているがNの大きいケースだけ悪化し、それ以外は少し高速化した…マジ謎…

最初のコードとどちらを採るのがよいのか全く分からんが

Nの最大ケースにだけ注目して最初のコードを良しとし、C++のループ回数は5,889,738

 そのコードをFullSubmissionに投じたスコアは3475.93

 

まとめ

                     ExamplesのN=1000の         FullSubmissonの

言語             ループ回数      スコア            スコア

Python             148,480         9.3283           2706.25

VB.NET        2,375,680       31.734             3471.81

C#                 2,506,752       31.926             3472.17

Java              5,775,360       32.330             3475.93

C++               5,889,738       32.332             3475.93

 

 結論

VB.NETっていうか.NET言語はTC鯖上では思いのほか糞だったっぽい

 そして、意外にも(今回のやり方においては)JavaC++はそんなに差が無く、どちらも.NET言語よりはるかに高速だった

 

追記(2019-04-12):

ジャッジ修正によりVB.NETC#も速度十分になった

                      ExamplesのN=1000の         FullSubmissonの

言語             ループ回数      スコア            スコア

VB.NET        5,210,112     32.320             -

C#                5,308,416        32.326             -

 

補足など

1024回ごとや8192回ごとに時間取得するコード書いたけど

1024や8192の数字に何の根拠もないのであしからず

1024回や8192回に達するまでにタイムオーバーする危険もあるのであまり推奨されるやり方ではなかもしれない

また if ((lp & 8191) == 0) { } などとビット論理積で回数判定しているのも深く考えるのが面倒臭くて適当にそうしただけで、根拠はない

次のように適当な変数用いてやってもよかったのかもしれない

long long interval = 3000; // 例えば3000回ごとに時間取得のループ脱出判定

long long next_check = interval;

for (;;) {

  if (lp > next_check) {

     ...

      next_check += interval;

  }

  lp++;

  ...

}