No Such Blog or Diary

succinct data structure というものを初めて知った．使用する空間量が情報理論的下限（つまりはエントロピー？）に近く且つ幾つかのクエリ処理が高速に行えるデータ構造であると．分類としては，適当なデータを表現するビット量の情報理論的下限をZとしてやると，Z + O(1) ビットで表現できる構造は implicit data structure で，Z + o(Z) ビットで表現できる（つまり係数も一致して漸近的に下限に至る）なら succinct で，O(Z) ビットで表現できる（つまり下限の定数倍程度）なら compact というと．

例としては，{0, 1, ..., n-1} の部分集合の表現（つまりは長さ n のビットベクタ）に対して rank と select というクエリをO(1)で行うギミックを付けた構造があると．rank(x) は x ビット目までの 1（ないし 0）の数を返すクエリで，select (y) は rank(x) = y なる最小の x を返すクエリ．rank を O(1) で計算するために o(n) なサイズのテーブル３つをうまく用意してやると．大きな１つのテーブルですべての答えを用意しようとすると n lg n になってしまう（引数の数がn通りでそれぞれの答えが lg n だから）ので，とりあえず (lg n)^2 毎に区切ったブロックの先頭だけの rank テーブルを作って（これで n / ((lg n)^2) * lg n = n / lg n ビットのテーブル），次に残りのブロック内の先頭からの rank の差分をどうにかしましょうとか考えるのね．残りの部分をどうするかだけど，とりあえず愚直に全部のインデックスに対してブロック先頭からの差分を保持すると O(n) 以上かかるのでダメで，一方，存在しうるブロックの全パタンを網羅しておこうとしてもブロックサイズが大きすぎてこちらも O(n) 以上かかる．しょうが無いのでもう一段ブロック化を導入してあげて，この小ブロックのサイズを lg n / 2 にしてあげると，この小ブロックに関して全パタン網羅しても o(n) で済むし小ブロックの先頭の rank （の大ブロックの先頭からの rank の差分）を全部保持しても o(n) で済みますよと．これにて一件落着．クエリ時には３つのテーブルを引いて足しあわせりゃいい．select はめんどいらしい．

まあ，再帰の段数を固定して適度なサイズ以下の問題は定数で答えが返るという状態を作っておけということなのか？　計算の一部を適当なサイズのデータに変えて取っておこうよというかよく使う部分計算はテーブルに取っておこうよというか．

それはさておき，rank/select で具体的に何が出来るのかがよく分からん．あとは一般にどんなクエリなら効率をデータ構造に押し付けられるんだ？　どの程度自動化できるんだ？　よく分からん（論文読め）．

変な姿勢でディスプレイ眺めてたせいなのか……　とりあえず行動不能．

働けるとこに感謝して一日中働く日だと教えられた気がする．

例え元のプログラムが正しかろうとコンパイラが間違っていれば出てくるものもやっぱ間違っているわけで……　例えば，車とかに入りまくっているチップの設計に使われるようなHDLのコンパイラはどの程度正しいと証明されているのだろうか？　コンパイラのバグ踏んだー！とか言って事故るのはゴメンなのだけど．

拡張が多すぎて探すのも面倒．

全部有効にして欲しい気もするけれどそれはそれで問題を発生させるんだよね……　こんな言語設計でいいのか？

レジで合計439円と出た　→　財布には992円（100円玉9枚，10円玉9枚，1円玉2枚）が入っていた　→　440円を出そうとしたが硬貨を1枚を取り違えて 530円を置いた　→　10円を置いた　→　この時点でレジのババァ様に硬貨が回収されてレジに入れられる　→　返って来たのは1円玉1枚と「439円をぴったり支払いお釣りがなかった」というレシートのみ

……

とりあえず100円盗られた形なわけだが，自分の記憶以外に証拠がない状況になってしまってから文句を言っても始まらないし後ろも列ができていたのでそのまま退散．まあ，ババァ様も合計金額が539円だと勘違いしたのかも知れないし受取額をレジ入力するのが面倒だったから正しくないレシートを発行したのかも知れない．硬貨を数えた上でレジの金額表示をちらっと確認はしてたけど．

教訓：まぎらわしい金額で支払いをしないこと．