LoginSignup
0
0

More than 1 year has passed since last update.

@recuraki(Akira Kanai)

C++でDPする際の配列順序とvector or 単純配列に関する実験と考察 (AGC054-B - Greedy Divisionを題材として)

Last updated at Posted at 2021-06-28

主張は、「C++でアプローチが正しい考察をしても、実装のDPの変数宣言やvector,配列のをきちんとしないとTLEなりする」です。問題解説ではないです。

AGC-Bで私はdp[100][10000][100]のテーブルを作り、5e7回ほどのDP計算を行いました。ところが、私の解法の使用時間・メモリを見ると、とても長い時間と多くのメモリを使用しています。vectorの多次元配列でなく、通常の配列を使うべきでした。さて、いくつかの工夫をしていきます。

結果だけ知りたい

私のコードは、

REP(i, 100){
 REP(value, 5100){
  REP(cnt, i+1){
   dp[i][value][cnt]...

というループを回します。この時、dpの定義を変える、また、vectorか？配列か？で実行速度やメモリに大きく影響します。

参考:T/O 2sec

番号 方法 配列の順序 実行時間 メモリ リンク
orig オリジナル[110][10200][110] i, value,cnt 1213ms 1020664 KB コード
B1 vector[110][10200][110] i, value,cnt 1169 ms 1020656 KB コード
C1 dp[110][10100][110] i, value,cnt 764 ms 442352 KB コード
C2 dp[110][10100][110] cnt, value,i TLE - コード

主張は以下の通りです。

  • vectorを使う際に、.atは無視できる程度の重さ。origとB1を比べてください。at(i)か[i]かの違いです。
  • vectorでなくてよいときは配列の方がメモリも実行時間も有利。B1とC1を比べてください。vector<vector<int>>などの宣言とするか、int[][]と宣言するかの違いです。
  • 宣言の順番によってはTLEする。違いは配列のアクセスを[i][value][cnt]とするか、[cnt][value][i]とするかです。

最後の点がわかりにくいかと思います。。以下のコードを見てください。$20000 \times 20000$のテーブルを同じように計算していますが、[i][j]とするか[j][i]とするかで実行速度が50%くらい異なります。

#define N 20000
unsigned long long dp[N+1][N+1];
int main(){
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            dp[i+1][j+1] = dp[i][j] + i+j; //  2.35s user 0.50s system 99% cpu 2.851 total
            //dp[j+1][i+1] = dp[j][i] + i+j; //  3.46s user 0.45s system 99% cpu 3.913 total
        }
    }
}

コードの概要

今回の主役はdp部分の以下のコードです。このコードは無駄があり、すべての配列をアクセスしません。

  • [value]は10200確保しているが、5100を超える領域は使わない(=確保に無駄がある)
  • [cnt]も110確保しているが、すべて使われない。$i$に対して$i+1$なので、$1,2,3,4$のように階段状に使われる。
vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));  // つまりdp[110][10200][110]相当
    REP(i, n){ // max n = 100
        REP(value, 5100){
            REP(cnt, i + 1){ // i+1 = max i+1 = 101
                dp.at(i + 1).at(value).at(cnt) += dp.at(i).at(value).at(cnt);
                dp.at(i + 1).at(value).at(cnt) %= mod;
                if(value+dat[i] > 5100) continue;
                dp.at(i + 1).at(value + dat.at(i)).at(cnt + 1) += dp.at(i).at(value).at(cnt);
                dp.at(i + 1).at(value + dat.at(i)).at(cnt + 1) %= mod;
            }
        }
    }

工夫1: vectorの.at()を[]にする

私はC++を書く際に、不正なindex参照を防ぐためにdat[i]の代わりにdat.at(i)よく使います。ただし、atはindexのチェックを行うため、若干遅くなります。すべてのatを[]に変えます。

dp.at(i + 1).at(value).at(cnt) += dp.at(i).at(value).at(cnt); // これを-> 
dp[i + 1][value][cnt] += dp[i][value][cnt]; // こう

この先の比較ではすべて、atを使わないで[]で実験します

工夫2: vectorの[110][10200][110]を[110][110][10000]など順番を変える

配列の順序を変えます。

vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));
dp[i + 1][value][cnt] += dp[i][value][cnt];
 // これを -> こうする
vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(110, vector<ll>(10200, 0LL)));
dp[i + 1][cnt][value] += dp[i][cnt][value];

確保する数は一緒ですが、これは2つの改善(悪化)を見込めます

  • 連続したメモリ空間へのアクセスはキャッシュの観点から有利になる可能性があります。
  • vectorは構造体であるため、ヘッダを持ちます。[110][110]のvectorを持つと、vectorは約$10^4$個しか生成されませんが、[110][10200]のvectorを持つとvectorは$10^6$作られます。メモリの使用量で有利(不利)になります。

工夫3: vectorではなくてlong long [][][]にする

  • vectorはイテレータを使えたり、可変長であったりと便利ですが、その分、初期化・操作・メモリのオーバーヘッドが多いです。DP操作のように高度な操作が不要であれば配列で十分です。
vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));
 // これを -> こう
ll dp[110][10200][110];

結果:

// ループの順序の再確認
    REP(i, n){
        REP(value, 5100){
            REP(cnt, i + 1){
                dp[i + 1][value][cnt] += dp[i][value][cnt]; // ★個々の順番を適当に変える。この場合はi, value, cnt
                dp[value][cnt][i + 1] += dp[value][cnt][i]; // ★こうすると、value, cnt,, i
// ループの順番は変えません！
番号 方法 配列の順序 実行時間 メモリ リンク
orig オリジナル[110][10200][110] i, value,cnt 1213ms 1020664 KB コード
B1 vector[110][10200][110] i, value,cnt 1169 ms 1020656 KB コード
B1a vector[110][110][10200] i, cnt value 1530 ms 976836 KB コード
B2 vector[110][10200][110] cnt, value,i TLE - コード
B2a vector[110][110][10200] cnt, i value 1388 ms 976840 KB コード
B3 vector[10200][110][110] value, i, cnt 1205 ms 1011684 KB コード
B3a vector[10200][110][110] value, cnt, i TLE - コード
C1 dp[110][10100][110] i, value,cnt 764 ms 442352 KB コード
C1a dp[110][110][10100] i, cnt value 704 ms 229380 KB コード
C2 dp[110][10100][110] cnt, value,i TLE - コード
C2a dp[110][110][10100] cnt,i, value 698 ms 229408 KB コード
C3 dp[10100][110][110] value, i, cnt 854 ms 461980 KB コード
C3a dp[10100][110][110] value, cnt, i 1942 ms 466380 KB コード

以下のことが言えます。

  • vectorで.at()と[]のアクセスはあまり時間に影響しない。
  • vectorと配列では、明らかに配列が優位。vectorはアクセスのオーバヘッド、vector自身のヘッダのオーバーヘッドが大きい
  • 連続したアクセスを考慮した配列の用意が重要。非連続なアクセスのみが起こる定義はTLEにもなりうる。
  • メモリの使用量については後述します。

メモリの使用量に関する考察(未解決)

実験結果の配列側だけを注意します。メモリ使用量450MBと230MBくらいの数字が見えます。しかし、long longのバイト長は8なので、8 * 110 * 10200 * 110 / 1000000 = 大体950(MB)より、[10100][110][110]と定義しているのに対して、$450MB$ですら少なすぎます。

ところが、上記のコードでは、[10100]をvalue向けに確保しているものの、5100までしか使用していませんでした。このため、950MBに対して半分くらいなのはこれで説明が付きそうです。

では、$230MB$はどうなのでしょうか？これはcntの使用率によりそうです。cntへのアクセスは、REP(i,n)の中で、REP(cnt, i+1としており、各iに対して、100個用意してあるcntはi+1までしか使われません。つまり、1+2+...+100なので、約半分です。
さて、メモリ使用率が少ない組み合わせはiとcntのあとにvalueが来ます。上記の通り、iとcntには密接な関係があります。例えば、
- [i][cnt][value]だった場合、i=1ならその先のcnt: 2 - 100は使わずそのあとのvalueも使われません。このため、cntの半分が使われず1/4になる？
- [cnt][i][value]だった場合、cnt=1なら、i: 2 - 100の領域は使われず、そのあとのvalueも使われません。このため、cntの半分が使われず1/4になる？
- [value][i][cnt]だった場合、5000までのvalueはアクセスされます。この後、i, cntは合わせて8byte * 200個くらいなので先読みなどでアクセスされてしまうのか？
(未解決)

Appendix: llとvectorのメモリ確保

/*実行結果
vector
 dp[0][0][0] addr=0
 dp[0][0][1] addr=8
 dp[0][1][0] addr=32
 dp[0][1][1] addr=40
 dp[1][0][0] addr=128
 dp[1][0][1] addr=136
 dp[1][1][0] addr=160
 dp[1][1][1] addr=168
ull[]
 dp[0][0][0] addr=0
 dp[0][0][1] addr=8
 dp[0][1][0] addr=16
 dp[0][1][1] addr=24
 dp[1][0][0] addr=32
 dp[1][0][1] addr=40
 dp[1][1][0] addr=48
 dp[1][1][1] addr=56
 */
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int test1() {
    vector<vector<vector<unsigned long long>>> dp(2, vector<vector<unsigned long long>>(2, vector<unsigned long long>(2, 0LL)));
    unsigned long long *base = &dp[0][0][0];
    for(int i = 0; i < 2; ++ i){
        for(int j = 0; j < 2; ++ j){
            for(int k = 0; k < 2; ++ k){
                dp[i][j][k] = i+j+k;
                printf(" dp[%d][%d][%d] addr=%lld\n", i, j, k, ((unsigned long long)&dp[i][j][k]) - ((unsigned long long)base));
            }
        }
    }
    return 0;
}
int test2(){
    unsigned long long dp[2][2][2];
    unsigned long long *base = &dp[0][0][0];
    for(int i = 0; i < 2; ++ i){
        for(int j = 0; j < 2; ++ j){
            for(int k = 0; k < 2; ++ k){
                dp[i][j][k] = i+j+k;
                printf(" dp[%d][%d][%d] addr=%lld\n", i, j, k, ((unsigned long long)&dp[i][j][k]) - ((unsigned long long)base));
            }
        }
    }
    return 0;
}
main(){
    cout << "vector\n"; test1();
    cout << "ull[]\n"; test2();
}

自分のsuubmit

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// #include <atcoder/all>
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

#define FASTIO() cin.tie(0); ios::sync_with_stdio(false)
#define FASTIOpre() cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);

//////////////////////////////////////

ll mod = 998244353LL;

ll myfact(int n){
    ll x = 1;
    FOR(i, 1, n+1){
        x = (x * i) ;
        x %= mod;
    }
    return x;
}
ll dp[110][110][10100];

using namespace std;
int main() {
    FASTIOpre();
    ll n;
    cin >> n;
    vector<ll> dat(n);
    ll total = 0;
    ll x;
    REP(i, n){
        cin >> x;
        total += x;
        dat.at(i) = x;
    }
    if(total % 2 == 1){
        cout << 0 << "\n";
        return 0;
    }

    dp[0][0][0] = 1LL;
    REP(i, n){
        REP(value, 5100){
            REP(cnt, i + 1){
                dp[cnt][i + 1][value] += dp[cnt][i][value];
                dp[cnt][i + 1][value] %= mod;
                if(value+dat[i] > 5100) continue;
                dp[cnt + 1][i + 1][value + dat[i]] += dp[cnt][i][value];
                dp[cnt + 1][i + 1][value + dat[i]] %= mod;
            }
        }
    }

    ll res = 0;
    ll tmp = 0;

    FOR(i, 0, n){
        if(dp[i][n][total / 2] != 0){
            tmp =  ((myfact(i) * myfact(n-i)) % mod) * dp[i][n][total / 2];
            res += tmp;
            res %= mod;
        }
    }
    cout << res % mod<< "\n";


}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0