[Rust] HashMapがBTreeMapより速いと思い込んでいた。

@e869120 さんがTwitterで投稿されている「競プロ典型90問」に参加しています。
先週末の[問題023 Avoid War](https://atcoder.jp/contests/typical90/tasks/typical90_w)でTLEから抜け出せずかなり苦労した[^2]のですが、ACに至った最後の一手が意外だったので。

## 通らなかったコード

解説を読んで下記のコードまでたどりついたものの、AtCoderのジャッジに投げるとTLEが一つ出てしまいます。[^1]

[^1]: 実はこのバージョンでも、24x24 のテストケースを適当に作ってAtCoderのコードテストに投げると7.8秒くらいで間に合います。検索回数が多いと思われる、全部白マスの場合でも。ジャッジはどんなテストケースなんでしょう？

```Rust
use proconio::{fastout, input, marker::*};
use std::cmp::*;
use std::collections::*;

const MOD: i64 = 1000000007;

#[fastout()]
fn main() {
  input! {
      H:usize,W:usize,c:[Chars;H]
  }
  let W2 = 1 << W;
  let mut block = vec![vec![false; W]; H];
  //let mut black = vec![0; H];
  for h in 0..H {
    for w in 0..W {
      block[h][w] = c[h][w] == '.';
      //black[h] *= 2;
      //black[h] += if c[h][w] == '#' { 1 } else { 0 };
    }
  }
  // 前のW+1マス分前を見て、dpする。そのままだとMLE
  // 24マスのうち、可能な並びは高々121393通り。
  let mut possible_base = Vec::with_capacity(130000);
  for s in 0..W2 {
    let mut flag = true;
    for j in 0..W {
      if s & (3 << j) == (3 << j) {
        flag = false;
      }
    }
    if flag {
      possible_base.push(s);
    }
  }
  // pos = possibleがi+1桁以上になるindex
  let mut pos = vec![0; W + 1];
  for i in 0..W {
    pos[i] = match possible_base.binary_search(&(1 << i)) {
      Ok(k) => k,
      Err(k) => k,
    };
  }
  pos[W] = possible_base.len();
  // W+1マス分を並べると2段になる。下の段と上の段をつなげることで、ありえるパターン数を網羅する。
  // wの値(何列目か)によって、可能なマスは異なる。
  let mut possible = vec![Vec::with_capacity(170000); W];
  let mut possible_inverse = vec![HashMap::with_capacity(170000); W];
  for w in 0..W {
    // i 桁以内を上位bit,W-i+1桁以内を下位bitとして、合成。
    let low_num = if w == 0 { 1 } else { W - w + 1 };
    let up_num = if w == 0 { W } else { w };
    for j in 0..pos[up_num] {
      let upper = possible_base[j] << low_num;
      for k in 0..pos[low_num] {
        let lower = possible_base[k];
        let s = upper | lower;
        if s & 1 != 0 && s & (1 << W) != 0 {
          continue;
        }
        if W > 1 && w != 1 && s & 1 != 0 && s & (1 << (W - 1)) != 0 {
          continue;
        }
        if w != 0 && s & 2 != 0 && s & (1 << W) != 0 {
          continue;
        }
        possible_inverse[w].insert(s, possible[w].len());
        possible[w].push(s);
      }
    }
  }

  let maxpossible = possible.iter().fold(0, |a, v| max(a, v.len()));
  let mut dp = vec![vec![0; maxpossible]; W * H + 1];
  dp[0][0] = 1;
  // 最初の1段目
  for h in 0..H {
    for w in 0..W {
      let mut nh = h;
      let mut nw = w + 1;
      if nw == W {
        nh = h + 1;
        nw = 0;
      }
      let mut id = h * W + w;
      let mut nid = nh * W + nw;
      for j in 0..possible[w].len() {
        let s = possible[w][j];
        // そのまま移動させた場合、次のマスの状態は？
        let s2 = s >> 1;
        let s2index = *possible_inverse[nw].get(&s2).unwrap();
        dp[nid][s2index] += dp[id][j];
        dp[nid][s2index] %= MOD;
        let mut flag = true;
        if block[h][w]
          && !(s & 1 != 0 && h >= 1 && w >= 1)
          && !(s & 2 != 0 && h >= 1)
          && !(s & 4 != 0 && h >= 1 && w < W - 1)
          && !(s & (1 << W) != 0 && w >= 1)
        {
          let s3 = s2 | (1 << W);
          if let Some(&s3index) = possible_inverse[nw].get(&s3) {
            dp[nid][s3index] += dp[id][j];
            dp[nid][s3index] %= MOD;
          }
        }
      }
    }
  }
  let mut ans = 0;
  for i in 0..possible[0].len() {
    ans += dp[H * W][i];
    ans %= MOD;
  }
  println!("{}", ans);
}
```

## 通したコード
で、本題です。
試行錯誤しているうちに、ダメ元で HashMapをBTreeMapに変えて提出したところ、ACしてしまいました。時間ギリギリ切りでしたが。

```Rust
  let mut possible_inverse = vec![HashMap::with_capacity(170000); W];    // before
```

```Rust
  let mut possible_inverse = vec![BTreeMap::new()); W];                  // after
```

BTreeMapは$O(log(N))$でHashMapは$O(1)$のため、HashMapのほうが早いものと思い込んでいたのですが、定数時間であってもそれ自体結構かかるということなんでしょうね。よく考えると$log_2 170000 < 18$ ですし、基本的にBTreeMapのほうが高速なのかもしれません。
もっとずっと深くなればBTreeMapのほうが遅くなるんでしょうか？　ちょっと気になります。


[^2]: ちなみに[解説](https://mobile.twitter.com/e869120/status/1386138990361726978)の1,2,4は自力で思いついていたんですが、3の発想に至らず諦めました。それだと$O(HW・fib(W)^2)=O(HW・1.62^{2W})$ はにはなるんですが、TLEになるのは意外と一個だけでした。