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

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


https://atcoder.jp/contests/agc054/tasks/agc054_b

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

# 結果だけ知りたい
私のコードは、

```C++
REP(i, 100){
 REP(value, 5100){
  REP(cnt, i+1){
   dp[i][value][cnt]...
```
というループを回します。この時、dpの定義を変える、また、vectorか？配列か？で実行速度やメモリに大きく影響します。

<font color=red>参考:T/O 2sec</font>

|番号|方法|配列の順序|実行時間|メモリ|リンク|
|-|-|-|-|-|-|
|orig|オリジナル[110][10200][110] |i, value,cnt|1213ms |1020664 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23832131)|
|B1|vector[110][10200][110] |i, value,cnt|1169 ms|1020656 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23846550)|
|C1|dp[110][10100][110] |i, value,cnt|764 ms|442352 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23847101)|
|C2|dp[110][10100][110] |cnt, value,i|TLE|-|[コード](https://atcoder.jp/contests/agc054/submissions/23849343)|

主張は以下の通りです。

- 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%くらい異なります。

```C++
#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
        }
    }
}
```


# コードの概要
https://atcoder.jp/contests/agc054/submissions/23831985

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

- [value]は`10200`確保しているが、`5100`を超える領域は使わない(=確保に無駄がある)
- [cnt]も`110`確保しているが、すべて使われない。$i$に対して$i+1$なので、$1,2,3,4$のように階段状に使われる。

```C++
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を[]に変えます。

```C++
dp.at(i + 1).at(value).at(cnt) += dp.at(i).at(value).at(cnt); // これを-> 
dp[i + 1][value][cnt] += dp[i][value][cnt]; // こう
```
<b><font color="red">この先の比較ではすべて、atを使わないで[]で実験します</font></b>

# 工夫2: vectorの[110][10200][110]を[110][110][10000]など順番を変える
配列の順序を変えます。

```C++
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操作のように高度な操作が不要であれば配列で十分です。

```C++
vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));
 // これを -> こう
ll dp[110][10200][110];
```

# 結果:

```C++
// ループの順序の再確認
    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|[コード](https://atcoder.jp/contests/agc054/submissions/23832131)|
|B1|vector[110][10200][110] |i, value,cnt|1169 ms|1020656 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23846550)|
|B1a|vector[110][110][10200] |i, cnt value|1530 ms|976836 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23846627)|
|B2|vector[110][10200][110] |cnt, value,i|TLE|-|[コード](https://atcoder.jp/contests/agc054/submissions/23849193)|
|B2a|vector[110][110][10200] |cnt, i value|1388 ms|976840 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23849259)|
|B3|vector[10200][110][110]| value, i, cnt|1205 ms|1011684 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23846681)|
|B3a|vector[10200][110][110] |value, cnt, i|TLE|-|[コード](https://atcoder.jp/contests/agc054/submissions/23849293)|
|C1|dp[110][10100][110] |i, value,cnt|764 ms|442352 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23847101)|
|C1a|dp[110][110][10100] |i, cnt value|704 ms|229380 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23847191)|
|C2|dp[110][10100][110] |cnt, value,i|TLE|-|[コード](https://atcoder.jp/contests/agc054/submissions/23849343)|
|C2a|dp[110][110][10100] |cnt,i, value|698 ms|229408 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23849368)|
|C3|dp[10100][110][110] |value, i, cnt|854 ms|461980 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23847221)|
|C3a|dp[10100][110][110] |value, cnt, i|1942 ms|466380 KB|[コード](https://atcoder.jp/contests/agc054/submissions/23849392)|

以下のことが言えます。

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

# メモリの使用量に関する考察<font color=red>(未解決)</font>
実験結果の配列側だけを注意します。メモリ使用量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個`くらいなので先読みなどでアクセスされてしまうのか？
<font color=red>(未解決)</font>

# Appendix: llとvectorのメモリ確保

```C++
/*実行結果
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

```C++
#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";


}
```