最中限読み切りプログラム高速化

std::listはpush_backもpop_frontもO(1)なんだっけ?カードを1枚ずつ使いながら探索するところで、まず[1, 2, 3]から1を使って後続の処理に[2, 3]を渡して、、、探索が終わったらまた[1, 2, 3]に戻して、次は2を使って[1, 3]を渡して、、、という処理をする。今はこれを要素を1個取り除いたvectorを作ることで実現しているけども、このコピーのコストが今削減できるコストの中では一番大きいと思われる。で、std::listのpop_front, push_backのコストがO(1)なら、[1, 2, 3]をpopして処理した後、push_backしちゃえばいいな、と思った。[2, 3, 1]になるので次の処理もpop_frontでいいし、必ずリスト全体をまわるので処理が終わった時点では元の形に戻っている。

当初listを使わなかったのは、ここに気づいていなかったので「破壊的に変更したらイテレータ壊れるよな」「毎回頭からたどるコストと1回コピーするコストとどっちが高いだろう」とその辺りが不安だったからなんだけど。

        • -

確認用コード

void recur(list<int>& xs, int depth){
  BEGIN(depth);
  for(int head_value = xs.front();;){
    int x = xs.front();
    xs.pop_front();
    if(depth > 1){
      DP(x);
      recur(xs, depth - 1);
    }else{
      DP(x);
    }
    xs.push_back(x);
    if(xs.front() == head_value) break;
  }
  END(depth);
}

int main(){
  list<int> values;
  values.push_back(1);
  values.push_back(2);
  values.push_back(3);
  values.push_back(4);
  recur(values, 3);
}

結果

BEGIN depth: 3
  x: 1
  BEGIN depth: 2
    x: 2
    BEGIN depth: 1
      x: 3
      x: 4
    END depth: 1
    x: 3
    BEGIN depth: 1
      x: 4
      x: 2
    END depth: 1
    x: 4
    BEGIN depth: 1
      x: 2
      x: 3
    END depth: 1
  END depth: 2
  x: 2
  BEGIN depth: 2
    x: 3
    BEGIN depth: 1
      x: 4
      x: 1

(中略。要するに(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 3, 2), 
 (1, 4, 2), (1, 4, 3), (2, 3, 4), (2, 3, 1),...
と全パターンだってことがいいたい。辞書順じゃないからわかりにくいけど。

    END depth: 1
  END depth: 2
END depth: 3

うんうん、期待通り。DP, BEGIN, ENDはCodeReposの/lang/cplusplus/debugprintに入れてあるデバッグ出力用マクロ。

        • -

id:methaneさんに指摘されたので確認。意外だったのだけど、今回の適用対象に関してはdequeの方がlistより10〜20倍速かった。listは削除したものを追加する際にまたmallocしてしまうんだろうか。っていうかやるんだろうなぁ。

Dancing Links - Wikipedia, the free encyclopediaとか使えば速いんだけど、面倒なのでstd::listを使えばほぼそれに近いかなぁと期待したんだけど、ちがった。オーダーは1であっても、Dancing Linksはmallocが必要ないところが大きな違いなんだろうか。

うーん、どっちみち全面的に書き換える必要があるわけだからDancing Linksにするかな。。