Implicit Treapの実装

Joeさんの実装で、pushdown中でpushupが必要な理由がわからなくてずっと悩んでいた。この実装ではpushdown→子に降りる→…→戻ってくる→pushupというふうに常にセットで呼んでいるし、accの値は子には影響しないのだから、pushupでaccを更新するのは戻ってきたタイミングだけで十分に見える……のだが、自分の実装(Common Lisp)でpushdown中のpushupを消すと正しく動かない。 しかし、ようやく解決した。結論から言えば、

1. Joeさんの実装では（たぶん）pushdown中のpushupはいらない。とりあえずAOJ DSL_2_HとAOJ 1508では確認済み。
2. 手元で正しく動かなかったのは、自分の実装がバグっていたから。

結果は平凡だが、遅延更新Treap（merge/splitベース）の実装のポイントがわかったのが収穫だった。

• すべての操作は、acc、lazy、value等が全体として整合的になっているTreapを返さなくてはならない。これは当然。
• それに加えて merge/splitの返すTreapの根(top)は評価済みでなくてはならない。 つまり、根に限ってはlazyやrevが解消されてaccが正しい値になっている必要がある。merge/split以外の操作についても、常にこれを守ったほうが余計なことに気を配らずに済むと思う。
• また、merge/split自身は根が未評価のTreapを正しく扱えなければならない。

という感じか。

上の原則が守られていれば、update中のt2->acc = Modifier::op(t2->acc, x, cnt(t2));はいらないはず。（mergeはlazyが0でない根を適切に処理するので。これも確認済み。）

そのうち報告するかもしれない。でも別にバグではないので……

とりあえず、自分の実装はこれ。区間更新区間取得と１点更新区間取得があるのだが、本当は１つにまとめられるはずだ。抽象化はもう少し使ってみてからにしたい。

Treapの効率

http://www.cepis.org/upgrade/files/full-2004-V.pdf
Dominique A. Heger. A Disquisition on The Performance Behaviour of Binary Search Tree Data Structures. UPGRADE, 5(5):67-75, 2004.

「Treapは遅いけど実装が容易」という話をいろいろなところで読んだのでそういうものかと思っていたが、この報告だとむしろいちばん速いように見える。

でも、赤黒木より速いならなぜ各種言語の標準ライブラリで使われないのかという話にもなるし、どう考えればいいのかわからない。乱択アルゴリズムは基本的に避けられがち、とかなんだろうか。

単方向リストによるキューと0-1 BFS

今さら気づいたのだが、単方向リストによるキューはpop-back（後ろから取り出す操作）ができないだけで、ほかの３種類の操作（push-front, push-back, pop-front）はすべて可能である。そして0-1 BFSはこの３つの操作があれば実行できるので、真の両端キューを用意する必要はないのだった。

気づいたので器物損壊！高橋君を解き直した。

AGC 026 C - String Coloring

• 問題
• 提出

最初、簡単のためにハッシュのキーに（文字の）リストを使ったらまったく間に合わなかった。経験上、リストは一般に言われるほど遅くないので（計算量的に不適切でなければ）頑張って避ける必要はないというスタンスでやっているのだが、ハッシュ値を求める場合は確かに差が出そうな気がする……

あるいは１回ごとにリストを作り直すのも問題なのかなー。ツリーを作る感じでコンシングを減らしていくとどうなるんだろう。→やってみたが多少ましになるだけで焼け石に水だった。ここまで遅いとどこかでオーダーが増えている可能性もある。（→増えていたらしい）

https://github.com/sbcl/sbcl/blob/894477d6a8ec1c6ad9d43069d819d9fb895bf664/src/code/target-sxhash.lisp
ハッシュテーブル周りのコードを読んでみると、SBCLのsxhash、sb-int:psxhashは細かく最適化する感じではなさそうだった。例えばbase-stringや(simple-array (unsigned-byte 8) (*))をワードごとに処理していくみたいなことはやってないように見える。あとでsb-ext:define-hash-table-testを使って高速化してみるかも。→やってみたらだいぶ速くなった。実践で役立つかはわからないが、いちおうこういう手段があるということで。以下は長さ40（=5ワード）のsimple-base-stringに特化したハッシュ関数を定義する例。

(declaim (inline simple-base-string40=))
(defun simple-base-string40= (s1 s2)
  (declare ((simple-base-string 40) s1 s2))
  (string= s1 s2))

(declaim (inline sxhash-sbs40))
(defun sxhash-sbs40 (string)
  "Based on SB-IMPL::%SXHASH-SUBSTRING"
  (declare ((simple-base-string 40) string))
  (macrolet ((set-result (form)
               `(setf result (ldb (byte 64 0) ,form))))
    (let ((result 0))
      (declare ((unsigned-byte 64) result))
      (dotimes (i 5) ; Unrolling made little difference.
        (set-result (+ result (sb-kernel:%vector-raw-bits string i)))
        (set-result (+ result (ash result 10)))
        (set-result (logxor result (ash result -6))))
      (set-result (+ result (ash result 3)))
      (set-result (logxor result (ash result -11)))
      (set-result (logxor result (ash result 15)))
      (logand result most-positive-fixnum))))

(sb-ext:define-hash-table-test simple-base-string40= sxhash-sbs40)

ARC 008 D - タコヤキオイシクナール

• 問題
• AC

とりあえずTreapに区間和を載せて解いた。なんとなくややこしそうという先入観があったが、遅延更新がいらないので自明な変更で済んだ。

最初の投稿で1sec以上かかって平衡二分木は遅いなあと思っていたが、ボトルネックはパース部分だったらしく、応急処置的にparse-double-floatを書いたら350msにおさまった。これならぜんぜん問題ない。

以下、Treapに関するメモ。

• 簡単のために、あらゆるクエリに対して既存のキーをdeleteしてからinsertしているが、Treap中にキーがあればその値を更新し、無ければ挿入するという操作を作ったほうが良いかもしれない。（ensure-keyとか？） ただ、優先度は勝手に決められないので、走査を一度で済ませることはできない気がする。findして同じキーが見つかったら更新、見つからなかったら根に戻ってinsertするみたいな感じになりそう。
• この問題のように数値等以外の空間を対象にする場合は、演算のたびにコンシングが発生することになる。更新先のプレースを与えて結果をそこに保存する感じにすれば回避できそうだが、見通しが悪くなるのであまりやりたくはない。あるいは、オペレータを可変長変数にして(op A (op B C))を(op A B C)に変えればコンシングが半分程度になる計算だが、それもやりたくない。仕組みは今のままで、必要ならopにコンパイラマクロを定義して(op A (op B C))を捕捉するくらいが落としどころか。
• もう少しTreapを使ったら、抽象的な実装を用意するかもしれない。現時点では次の2×2=4パターン（あるいは6パターン）あれば十分に見える。
  • explicit key, implicit key
  • 一点更新区間取得、区間更新区間取得、（機能なし）

ABC 121 D - XOR World

• 問題
• AC

各桁の$1$の数を数えれば${\mathcal O}(\log n)$で解ける。この際、$g(x) = f(0, x)$が求まれば$f(x, y) = g(y) \oplus g(x-1)$と書けるので、各桁ごとの偶奇の判定がだいぶ簡単になる。

任意の$n \in 2{\mathbb N}$について$n \oplus (n+1) = 1$となるのはまったく頭になかった。なるほど……

ARC 033 C - データ構造

• 問題
• 提出

とりあえず平方分割、平衡二分木(Treap)、BITで通した。平衡二分木はいちばん遅いが、リッチな構造で使い方が自明なので考察がいらない。逆にBIT上の二分探索はもっとも速いが、この操作を当然視できるためにはもう少し慣れが必要だと思った。