リストをハッシュテーブルのキーにする時は衝突に注意

SBCLのハッシュテーブルについて。

リストをハッシュテーブルのキーにしてequal（もしくはequalp）で比較する時、非常に遅くなることがある:

(defun test1 (size)
  (declare (optimize (speed 3))
           (fixnum size))
  (let ((table (make-hash-table :test 'equal)))
    (dotimes (x size)
      (setf (gethash (list 0 0 0 0 x) table) t))))

(time (test1 20000))
;; Evaluation took:
;;   7.287 seconds of real time
;;   7.296875 seconds of total run time (7.296875 user, 0.000000 system)
;;   100.14% CPU
;;   18,175,364,371 processor cycles
;;   3,686,448 bytes consed

高々20000個のキーの登録に7秒かかるのは明らかにおかしい。この現象はテスト関数をequalpにしても変わらないのだが、次のように些細な変更をするだけで普通の処理時間になる:

(defun test2 (size)
 (declare (optimize (speed 3))
          (fixnum size))
 (let ((table (make-hash-table :test 'equal)))
   (dotimes (x size)
     (setf (gethash (list 0 0 0 x 0) table) t))))

(time (test2 20000))
;; Evaluation took:
;;   0.006 seconds of real time
;;   0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;;   0.00% CPU
;;   14,992,420 processor cycles
;;   3,622,624 bytes consed

test2は(list 0 0 0 0 x)の部分を(list 0 0 0 x 0)に変えただけである。

こうなる原因は、SBCLのsxhashがリストを一定の深さまでしか走査しないことにある。この深さはsb-impl::+max-hash-depthoid+として定められていて、4になっている。

CL-USER> (sxhash '(0 0 0 0 0))
75491649990944584
CL-USER> (sxhash '(0 0 0 0 1))
75491649990944584
CL-USER> (sxhash '(0 0 0 1 0))
2843277705398422980

つまり、上のように(0 0 0 0 ...)というリストは以降のセルに関係なく同じハッシュ値になるので、test1ではすべてのハッシュ値が等しくなっている。キーが全部衝突すると既存のキーとマッチングする処理が${\mathcal O}(N)$になるので、test1は${\mathcal O}(N^2)$ということになる。¹

---

回避策はいろいろありそう。とりあえず、equalpで配列や構造体を使えばこの問題は起こらない。あくまでリストを使いたければ、適当なハッシュ関数を与えればよい:

(defun list-sxhash (x &optional (depthoid 100))
  (declare (optimize (speed 3))
           (fixnum depthoid))
  ;; sxhashの該当部分をそのまま使っている
  (typecase x
    (null (sxhash x))
    (cons (if (plusp depthoid)
              (sb-int:mix (list-sxhash (car x) (1- depthoid))
                          (list-sxhash (cdr x) (1- depthoid)))
              261835505))
    (t (sxhash x))))

(defun test3 (size)
  (declare (optimize (speed 3))
           (fixnum size))
  (let ((table (make-hash-table :test 'equal
                                :hash-function #'list-sxhash)))
    (dotimes (x size)
      (setf (gethash (list 0 0 0 0 x) table) t))
    table))

(time (test3 20000))
;; Evaluation took:
;;   0.012 seconds of real time
;;   0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;;   0.00% CPU
;;   31,158,036 processor cycles
;;   3,676,928 bytes consed

sb-int:psxhash（equalp用のハッシュ関数）には深さが指定できるので、:testをequalpをにしてこれを:hash-functionに与えるのが一番簡単かと思ったのだが、psxhashに与える深さは+max-hash-depthoid+以下でなければならないようで、この方法は不可能だった。なぜそんな制限があるのかはよくわからない。

---

以前に気づいた現象だったが、自分の記事を見返していてやっぱり何かおかしいなと思って調べたら、意外と単純な話だった。

+max-hash-depthoid+がかなり小さい値になっている理由は特に書かれていないけど、キーに循環構造がある場合は+max-hash-depthoid+いっぱいまで走査することになるのであまり大きくはできないだろうなという理解。

追記: ハッシュテーブルの挙動メモ

sb-int:psxhashによるベクタのハッシュ値の計算、つまりテスト関数がequalpの時の処理では、次の型が特別にディスパッチされているので、この中のどれかなら少し速い:

• simple-base-string
• (simple-array character (*))
• simple-vector
• (simple-array (unsigned-byte 8) (*))
• (simple-array fixnum (*))

ただし、(unsigned-byte 8)をワード毎にまとめて計算とかは基本的にやっていない。それをやるのはたぶんsimple-bit-vectorに対するsxhashだけ。

また、ハッシュテーブルに最後に登録・アクセスしたキーは特別に保持され、gethashを呼ぶたびにeqで比較される。つまり、例えばキーの存在判定をして無ければ登録する、みたいな処理をする時、2回gethashを呼んだらキーが2回走査されて遅いかもという心配はあまりしなくてよい。

---

g000001さんによると、どの処理系でもだいたい事情は同じらしい。

---

1. SBCL 1.5.4までのコードだと、${\mathcal O}(N)$かかるのはこの部分。1.5.5～1.5.6でハッシュテーブルの実装が大きく変わって、ちゃんと読んでいないけどおそらくだいたい同じ。 ↩︎

AGC 026 B - rng_10s

• 問題
• AC

とりあえず自明ケースを除いておく:

• $A < B$ならNo
• $B>D$ならNo
• 上記以外で$B \le C$ならYes

それ以外の場合では、Noになるのは在庫の数$X$が区間$(C, B)$に入ってしまう場合、つまり1回の購入量$B$より小さく補充の閾値$C$よりは大きい状態が発生してしまうケースである。これは$X$が$\mod B$で$C+1, C+2, ..., B-1$のいずれかと合同になる、と言い換えられる。

シミュレーションしながら考えてみる:

• 最初の在庫$A$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとNo。
• $A \equiv 0, 1, ..., C \mod B$の場合は$D$個の補充に成功する。$A+D$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとやはりNo。
• $A+D \equiv 0, 1, ..., C \mod B$の場合はさらに$D$個の補充に成功する。$A+2D$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとやはりNo。
• …

というわけで、非負整数$x$が存在して$A+Dx$が$C+1, C+2, ..., B-1$のいずれかと合同の場合$(*)$はNo、それ以外はYesとわかる。

これで解けたと思ったのだが、そこから先のやり方がよくわかっていないことに気づいて考えこんでしまった……

合同方程式を解く方法に立ち戻る。$A+Dx \equiv d \mod B$を解くことは$Dx+By = d-A$を解くことと同じで、後者が可解であることは$d-A$が$\gcd(B, D)$の倍数であることと同値である。¹ したがって、条件$(*)$は$C+1-A, C+2-A, ..., B-1-A$の中に$\gcd(B,D)$の倍数が含まれる、と言い換えられる。これなら実装可能な判定方法になっている。つまり、$\gcd(B,D)$の倍数で$C+1-A$以上であるような最小のもの²を求めてそれが$B-A$未満ならNo、そうでなければYesである。

---

1. $x$が非負という条件は考える必要がない。整数解があれば必ず$x$が非負整数の解もあるため。 ↩︎

2. $y$以上の$x$の倍数で最小のものは、式としては$x \cdot \lceil y/x \rceil$と書ける。 ↩︎

UTPC 2012 H - 区間スケジューリングクエリ

• 問題
• AC

$R[k][t] :=$ 時刻$t$以降に最短で仕事を$2^k$個こなすときの終了時刻

というテーブルを作っておけば、クエリ$(QL, QR)$に対する答えは${\mathcal O}(\log N)$で求まる:

result := 0
for k from 16 downto 0
    if R[k][QL] <= QR
        result += 2^k
        QL := R[k][QL]
return result

ただし、このままでは時刻の範囲が大きすぎるので$IL_i, IR_i, QL_i, QR_i$に現れる時刻をまとめて座標圧縮しておく。

また、$R[0][t]$を初期化するために、時刻$t$以降に最初にこなすべき仕事（の終了時刻）を求めてなくてはならないが、$(IL_i, IR_i)$を終了時刻の昇順でソートしておいて順に処理していけばよい。

---

$R[k][x] :=$ 仕事$x$を終えた後に最短で仕事を$2^k$個こなすときの最後の仕事

という感じで仕事ベースでテーブルを作っておけば座標圧縮しなくても良いらしい。なるほど……

yukicoder No.885 アマリクエリ

• 問題
• AC (sparse table)
• AC (平衡二分木)

$A_i := A_i \% X_1, A_i := A_i \% X_2, ...$とmodを取っていくとき、値が変化するのは$A_i \ge X_k$であるような$k$についてだけである。また値が変化するときは必ず半分以下になるので、変化する回数は初期値について高々$\log_2 A_i$である。そこで、各$A_i$について、$X_{k_0} \le A_i$であるような最小の$k_0 \in [1, Q]$を求めて$A_i := A_i \% X_{k_0}$とし、$X_{k_1} \le A_i$であるよな最小の$k_1 \in [k_0, Q]$を求めて$A_i := A_i \% X_{k_1}$とし……を繰り返して、各クエリで総和がどれだけ減るかを記録する。この操作は例えばSparse Table上の二分探索でできる。

$A := \max_i A_i$とするとき、計算量は${\mathcal O}(N(\log A \log Q + \log N))$。

---

コンテスト中は上の方針でやったのだが、よく考えると、順序付き集合に$A$全体を入れておいてクエリごとにシミュレーションすれば十分だった。

先読みできる設定だとまずそれを利用したくなるけど、良し悪しありそう。

AGC 022 B - GCD Sequence

• 問題
• AC

$x$と$S \setminus \{x\}$が互いに素でないという条件から偶数の集合$\{2, 4, 6, ...\}$を思い浮かべてみるが、そのままでは$S$の最大公約数が$1$にならないし、また、$30000$までの偶数は$15000$個しかないので数も足りていない。そこで、$3$を加えて$S$の最大公約数を$1$にした上で、$3$の倍数を適当に加えて条件を満たすようにできないか考えてみる。^[1]

既に特別である集合$S$に、特別性を壊さないように整数を追加することを考える。まず、$S\setminus \{2\}$の総和が$2$で割り切れるようにするために、$S$の中の奇数は常に偶数個を保つべきなので、$3$の倍数で奇数であるものは2個ずつ加えたい:

$(1) \qquad \{3, 9\}, \{15, 21\}, \{27, 33\}, ...$

また、$S\setminus\{3\}$の総和が$3$で割り切れるようにするために、追加する数は常に$3$の倍数を保ちたい。偶数のうち$3$の倍数であるもの、つまり$6$の倍数は1個ずつ加えることが可能である:

$(2)\qquad 6, 12, 18, ...$

偶数のうち$3$の倍数でないもの、つまり$3$を法として$1$または$2$と合同であるものは、ペアで追加すれば$3$の倍数になる:

$(3) \qquad \{2, 4\}, \{8, 10\}, \{14, 16\}, ...$

$(1), (2), (3)$で$20000$個の整数を網羅しているので、あとは$S := \{3, 9\} \cup \{2,4\}$をベースにして$N$に達するまで任意に加えればよい。$N=3$の場合だけ扱えていないが、サンプルにある出力をそのまま使って対応できる。

---

1. 競技としては、$30000$以下の$2$か$3$の倍数である整数がちょうど$20000$個であることからメタ読みもできそう。 ↩︎

AISing Programming Contest 2019 D - Nearest Card Game

• 問題
• AC

シミュレーションしてみると（時系列を無視すれば）

1. 高橋君が上から何枚か取って
2. 残りを青木君が上から同じ枚数取って
3. さらに残りを二人で上から交互に取る

という仕組みになっていることがわかる。

高橋君が手順1で上から$l$枚、つまり区間$[N-l, N)$を取るとし、青木君が手順2で区間$[N-2l, N-l)$を取るとして、与えられたルールに従うための$l$の条件を考える。

まず、青木君が取るもっとも大きい数は$A_{N-l-1}$である。したがって、青木君が最初に決めた数を$x$とするとき、$x- \max(A_{N-l-1}-x, 0)$以上の数が書かれたカードはすべて青木君が取っていなければならないことになる。ここで、

$f(y) :=$ $y$以上の数が書かれたもっとも左のカードのインデックス

とする。（ $f(y)$は二分探索で求まる。） $f$を使って上の条件を表すと、青木君は少なくとも区間$[f(x- \max(A_{N-l-1}-x, 0)), N-l)$を取らなければならず、これは、青木君が手順2で取るカードの枚数が$(N-l)-f(x- \max(A_{N-l-1}-x, 0))$以上であることを意味する。この数を$g(l, x)$で表すとき、$g(l, x)$は$l$以下でなければならない。したがって、ルールに従った取り方では、$g(l, x) \le l$であるような最大の$l =: l_{\max}$が、手順1, 2で実際に取った枚数になる。$g(l, x)$は$l$について単調増加なので$l_{\max}$はやはり二分探索で求まる。

$l_{\max}$が求まったら、高橋君の点数は区間$[N-l_{\max}, N)$の総和と$[0, N-2l_{\max})$をひとつおきに取った和（$0$から始まるか$1$から始まるかは偶奇による）の合計になるため、どちらも累積和を計算しておけば${\mathcal O}(1)$で求まる。