ネストした vector の順序と性能

概要

今朝 (2023.04.25 …もう昨日だ…) のあさかつで Picking Goods という問題が出ました．もとは ABC175-E です．

vector を3重にネストさせて解いたのですが，このようなときに，添字を並べる順序によって結構性能に差が出ます．でも，どの順序で添字を並べれば良いのか，よくわかりません．測定してみたのですが，やはりよくわかりませんでした，という報告です．

Picking Goods の問題概要

$R$行$C$列に並んだマス目に$K$個のアイテムがある． $i$番目のアイテムは $(r_i, c_i)$ にあり，価値 $v_i$ を持つ．マス $(1, 1)$ から，マス $(R, C)$ まで，右か下に移動していく．マスにあるアイテムを拾っても拾わなくても良い．同一行で拾えるアイテムは3個以下．拾うアイテムの価値の最大値を求めよ．

主な制約:

$1 \leq R, C \leq 3000$
$1 \leq K \leq 2\times 10^5$
$1 \leq v_i \leq 10^9$

解法概要

$dp(r, c, k) :=$ マス $(r, c)$ に入ってきたときに，すでにその行で $k$ 個拾っている場合の，拾ったアイテムの価値合計の最大値

おおむね次のような感じで解ける:

  ll ans = 0;
  REP(r, R) REP(c, C) REP(k, 4) {
    ll v = そのマスにあるアイテムの価値;
    ll w = dp[r][c][k]
    if (r + 1 < R) {
      chmax(dp[r + 1][c][0], w);
      if (k < 3) chmax(dp[r + 1][c][0], w + v); }
    if (c + 1 < C) {
      chmax(dp[r][c + 1][k], w);
      if (k < 3) chmax(dp[r][c + 1][k + 1], w + v); }
    if (r + 1 == R and c + 1 == C) {
      chmax(ans, w)
      if (k < 3) chmax(ans, w + v); }}

vector のネスト順と性能

上のコードでは，dp は，次の順序で定義する想定になっています． (RやCは3000くらいでした)

vector dp(R, vector(C, vector(4, 0LL)));

これをたとえば

vector dp(C, vector(4, vector(R, 0LL)));

に変えても正しいコードです．R, C, 4 の順序は全部で $3! = 6$ 通りあり得ますので，そのうちどれにするのが性能的に有利か? というのが知りたいことです．

ここで気になるのは，vector の定義の順だけでなく，ループの順序も関係しそうだ，ということです．上のコードで

REP(r, R) REP(c, C) REP(k, 4)

となっているところを，たとえば

REP(c, C) REP(r, R) REP(k, 4)

などと変えることを考えると，ループ順で 6 通り，vector の順序で 6 通りの合わせて 36 通りで，どれが良いのか，という問題になります．以下では，ベクトルの順序を RCK, CKR などと，ループの順序を rck, crk などと書くことにします．

この Picking Goods の問題では (たいていの問題でも(?))， vector の順序は 6 種類のどれをとっても正しい値になりますが，ループ順の方はそうではありません．rck, rkc, crk は正しい値になりますが， ckr, krc, kcr では正しくありません．しかし，(この問題に限らない) 性能の観点から，(この問題については) 正しくない順序も合わせて測定してみました．

結果

R=3000, C=3000 で各5回測定して，平均を出しています．

* rck (正しい)
RCK 443.84
RKC 185.02
CRK 1074.77
CKR 1175.56
KRC 282.28
KCR 538.78

* rkc (正しい)
RCK 455.33
RKC 168.84
CRK 2350.77
CKR 2412.47
KRC 265.45
KCR 1149.02

* crk (正しい)
RCK 710.31
RKC 674.53
CRK 418.03
CKR 165.88
KRC 556.53
KCR 215.19

* ckr (正しくない)
RCK 2187.65
RKC 2367.59
CRK 470.11
CKR 178.29
KRC 1166.15
KCR 202.46

* krc (正しくない)
RCK 538.14
RKC 188.89
CRK 2716.52
CKR 2419.14
KRC 213.24
KCR 1159.28

* kcr (正しくない)
RCK 2331.38
RKC 2501.15
CRK 538.46
CKR 189.43
KRC 1177.99
KCR 210.80

以下のようなことが見てとれます．

(正しいループ順に限っても) vector の順序によって，性能に大きな差が生じる (10倍以上違う)
vector の順を決めても，ループ順が変われば速度は異なる．
良く言われる，「小さいものを先にした方が良い」ということは，いつでも必ず成り立つとまでは言えない．(rkc - KCR などを参照)
R と C を入れ換えると大きく結果が違う例もある．この問題の場合，行と列が対称ではなく，(特にKとの関係での) アクセスのされ方が異なることが効いているのであろうか．
(この一つの例から一般化するのは非常に危険だが) ループ順と vector 順を揃えておく (rck - RCK や kcr - KCR など) と (必ずしも最良の結果が得られるとは言えないものの) 最悪の結果は避けられているように見える

いくつか補足．

$v_i$ も，2次元のベクトルに保存することになると思いますが，そうすると，この順序も関係しそうです．ここでは，その影響を避けるために，v_i は入力として与えず，10000 個くらいの点に適当に値を与えています．(具体的には次で計算される v を使っています．) この変更によって，実際に問題を解く場合より，かなり速度が速くなっています．

    ll v = 0;
    if ((r & 0x1f) == 1 and (c & 0x1f) == 1) v = (r >> 5) + (c >> 5);

この測定結果は，私のローカル環境に依存するところも大きいと思います． AtCoder で測定してみたわけではありません．環境は， Ubuntu (Window ホストの Virtual Box) 20.04 上の GCC 9.4.0 です． -std=gnu++17 -O2 でコンパイルしています．

概要#

Picking Goods の問題概要#

解法概要#

vector のネスト順と性能#

結果#

概要

Picking Goods の問題概要

解法概要

vector のネスト順と性能

結果