えびちゃんの日記

えびちゃん（競プロ）の日記です。

bitset 高速化が定数倍高速化という風潮に対するお気持ち表明

「bitset で 64 倍高速化できます」「64 は定数なのでオーダーは変わりません」のような説明は、競プロ界隈でたびたび見かけます。

AGC の解説 とかも。

「定数倍高速化を軽視する風潮に対するお気持ち表明」や「競プロのような入力に上限がある場合でもオーダーを信仰する風潮に対するお気持ち表明」などは、一旦おいておきます。

今回のメインは、「長さ \(n\) の bit 列の bitwise AND/OR や shift にかかる時間は \(\Theta(n)\) か？」（あるいは、そう仮定するのは妥当か？）という話です。

tl; dr

word RAM の下で、\(\Omega(\log(n))\) 倍の高速化と言えそうです。

補足

オーダー記法に慣れていない人が以下で怯えないように、さくっとまとめておきます。

  • \(\Theta(f(n))\)：ちょうど \(f(n)\) のオーダー。
    • 競プロ界隈で言うところの \(O(f(n))\) に近そう。
  • \(O(f(n))\)：高々 \(f(n)\) のオーダー。
    • \(O(n^3)\) と書いたとき、実際には \(\Theta(n^2)\) かもしれない。
  • \(\Omega(f(n))\)：少なくとも \(f(n)\) のオーダー。
  • \(o(f(n))\)：\(f(n)\) より真に小さいオーダー。
  • \(\omega(f(n))\)：\(f(n)\) より真に大きいオーダー。

小文字の方は今回は使いません。

導入

次のような問題を考えてみます。

\(0\) または \(1\) からなる長さ \(n\) の列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられます。これが回文か判定してください。

  1. for \(i \in \{0, 1, \dots, n-1\}\) do
    1. if \(a_i \ne a_{n-i-1}\) then
      1. return no
  2. return yes

愚直には、このようなアルゴリズムが考えられるわけですが、これの計算量はどうなるでしょう？ 何の仮定も無しに \(O(n)\) 時間（+ worst \(\Theta(n)\) 時間）だと言い切っていいでしょうか？ \(i\) のインクリメントや \(n-i-1\) の計算、\(a\) へのアクセスが \(O(1)\) 時間でできるものと仮定しているはずです（もっと言えば、1 bit の等価判定を \(O(1)\) 時間と仮定しているはずです。さすがにこれくらいは仮定したいですが）。

読者の中には、「\(a\) を順方向と逆方向にシーケンシャルアクセスするだけでいいからそれらの仮定はいらないだろう」と言う人もおられるかもしれない*1ので、別の例も出します。

\(0\) 以上 \(2^n\) 未満からなる長さ \(n\) の整数列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられます。その後、「与えられた \(i\) と \(j\) に対して \(a_i+a_j\) の値はなんですか？」という形式の \(m\) 個の質問に答えてください。

これは \(O(n+m)\) 時間と言えてほしいですが、何の仮定も無しには言えません。 そもそも各整数をどういう形式で表すのかについても触れていません。 「ひとつの整数を表すのに \(2^n -1\) 個の連続する bit を用い、そのうち（連続するとは限らない）\(x\) 個の bit が \(1\) で残りが \(0\) のとき、\(x\) を表すとする」などと言われては大変扱いにくいので、もう少しマシなものを要求したいです。 コンピュータで扱いにくいものの話をしてもしょうがないので、2 進法で表すのがいいかなとなります*2。

また、整数 \(i\) を用いて \(a_i\) に \(O(1)\) 時間でアクセスできることが要求されます。 \(a\) の長さは \(n\) であることから、\(\log(n)\) bits 程度の整数は \(O(1)\) 時間で扱えないとお話にならないことがわかります。 \(a_i+a_j\) の計算もしなきゃなので、\(\log(n)\) bits 程度の加算も \(O(1)\) 時間でしたいです。

word RAM の話

こうした要望に合った計算モデルとして、word RAM というのがあります*3。次のような仮定です。

  • \(U=2^u\) 個の word からなる配列をメモリと呼ぶ。
    • 入力はこのメモリに収まる必要がある。
  • word をポインタとして扱える。
    • word を添字として用いてメモリ（の全範囲）にアクセスできるということ。
  • 長さが \(O(1)\) の連続する word に対する読み書き、四則演算 (+, -, *, /, %)、ビット演算 (&, |, ^, !, <<, >>), 比較演算 (==, <, etc.) は \(O(1)\) 時間でできる。
    • ! はビット反転。C とかで言うところの ~。

word によってメモリにアクセスできることから、word は最低でも \(u\) bit 必要です。 word の bit 長を \(w\) とすると \(w\ge u\) です。

これらから、連続する \(u\) bit に対する各種演算が \(O(1)\) 時間でできることが従います。 ただし、「メモリから飛び飛びの \(u\) 個の bit を集めてきて、結合してひとつの整数と見なし、それらを用いた演算を行う」ということは \(O(1)\) 時間でできるとは言っていないことに注意してください。

本題

さて、元々の話に戻ります。

長さ \(n\) の bit 列に対するビット演算の計算量は？

連続する \(n\) 個の bit 列、すなわち \(n/w\) word に対する演算となります。 \(w\) は最低でも \(\log(n/w)\) bit 必要なことから \(w \ge \log(n/w)\)、すなわち \(w\cdot 2^w \ge n\) となります。

式変形がんばるよ \(w\cdot 2^w = n\) の形の式を解くのは初等的にはつらいです。Lambert の \(W\) 関数 というのがあります。 一般には複素数で定義されますが、ここでは実数についてのみ考えます。 \[ ye^y = x \implies y = \begin{cases} W_0(x), & \text{if }x \ge 0; \\ W_{-1}(x), & \text{if } -1/e\le x\lt 0. \end{cases} \] ここでは \(x\ge 0\) のみ気にするので、\(W_0\) のみ考えます。 \[ \begin{aligned} w\cdot 2^w &\ge n \\ w\cdot 2^{w\cdot\log_2(e)\cdot\log_e(2)} &\ge n \\ w\cdot e^{w\cdot\log_e(2)} &\ge n \\ w\cdot\log_e(2)\cdot e^{w\cdot\log_e(2)} &\ge n\log_e(2) \\ w\cdot\log_e(2) &\ge W_0(n\log_e(2)) \\ w &\ge W_0(n\log_e(2))\cdot\log_2(e). \end{aligned} \]

また、\(W\) 関数について、以下のことが知られています*4。 \[ x\ge e \implies \ln(x)-\ln(\ln(x)) \le W_0(x). \] これらから、\(w\in \Omega(\log(n/\log(n)))\) が言えそうです。 がんばりおわり。

不等式を示すだけなら、\(W\) を使わなくてもできるかもです。

（追記）

まず、\(\log(n)\ge\log(n/\log(n))\) はいいとして、 \[ \begin{aligned} \log(n/\log(n)) &= \log(n) - \log(\log(n)) \\ &\ge \log(n) - \log(\sqrt{n}) \\ &= \log(\sqrt{n}) \\ &= \frac{1}{2}\log(n) \end{aligned} \] なので、\(\log(n/\log(n)) = \Theta(\log(n))\) でした。

やっぱり \(W\) を使わずにできましたね。

結局、\(w\in\Omega(\log(n))\) が言えたので、\(n/w\in O(n/\log(n))\) となります。というわけで、bitset 高速化は \(\Omega(\log(n))\) 倍の改善と言えそうです。

おまけ

別のモデルの話

たとえば、もっとやばい計算モデルを仮定して、「任意のサイズの整数の四則演算は \(O(1)\) でできます」というのがある程度の妥当性をもって言えれば、bitset 高速化は \(n\) をひとつぶん落としたと主張できそうです。

word RAM の元々の論文*6では、

これこれの論文では長さ \(n\) の整数配列 \(a\) のソートを \(O(n)\) 時間で達成したと述べているが、\(n^2 \log(\max a)\) の長さ（ビット？）の除算を \(O(1)\) 時間でできると仮定した上でのアルゴリズムであり、やばいだろ

といった旨のことが書かれていました。

（追記）上の式では \(w\) の下限にしか触れていないので、別に \(w=n\) のようにワードサイズがやばいモデルを仮定することもできそうです。が、ちょっと乱暴だと思います。また、メモリを無駄に使うことで「\(w\) がもっと必要でしょう」と主張することもできそうですが、無駄に使ったメモリのぶんの時間のせいで損をしそうです。

（追記）別にメモリを無駄に使わずとも「\(w\) がめちゃ大きいモデルです」というのを仮定するの自体は許される気がします。現実的にはそれが妥当ではなさそうなので word RAM を考えていそうではありますが。

www.cs.cmu.edu

今回の内容に関連する講義資料です。word RAM 以外にも、Turing machine や論理回路を用いた場合に計算量はどうなるか？といったことが書かれています。

許容する演算の話

word RAM においては word size の四則演算を \(O(1)\) と言っていますが、乗算や除算はこれに含めないとする立場もあるようです。 これは、特定の条件を満たす回路によって加算は実現できるが乗算は実現できないという事情によるようです。 n bit の乗算が M(n) 時間でできれば、Newton 法によって n bit の除算も O(M(n)) 時間でできるので、乗算を仮定するなら除算も仮定されそうです。 ここ嘘で、\(M(n)\in O(1)\) なので、\(O(\log(w))\) 時間とかになっちゃいます。無視してください。

また、立っている最上位 bit の位置は、乗算を許せば次の手法で \(O(1)\) 時間で得られます。

rsk0315.hatenablog.com

これにより、立っている最下位 bit が n & -n で得られることと合わせて、立っている最下位 bit の位置も \(O(1)\) 時間で得られます。

word RAM 上のアルゴリズムの話

こういう記事があります。

qiita.com

まとめ

\(O(n/w)\) などの \(w\) は定数ではなくて、入力サイズ \(n\) に依っていると見なす立場もあるよ、という話でした。

マシンが入力に依ることに納得がいかない人は、「大きいサイズの問題を、メモリの少ない昔の PC で解くのは不可能」みたいなことを考えてみるといいかもしれません？ 大きなメモリをちゃんと扱うことができるマシンであれば、それに伴っていくらか大きい値も扱えるようになる、といったような気持ちに近い気がします。

補足

「実際にはキャッシュとかの関係できっちり 64 倍高速化されるとは限らないから 定数 倍高速化ではない」とかそういう類の主張ではないです。

おわり

log は定数学派の人にとっては bitset 高速化は定数倍高速化ということがわかりました。いかがでしたか？

*1:「インクリメントはならし定数時間なので〜」とか思った人もいるかも？

*2:当然、文脈によってはコンピュータに縛られる必要はありませんが、ここでは一応競プロに近い文脈なので。

*3:入力に応じてサイズが変わるの自体は transdichotomous model と呼ばれるもので、単位時間でできる特定の演算を決めたものが word RAM かもしれません。

*4:Hoorfar, A., & Hassani, M. (2008). Inequalities on the Lambert W function and hyperpower function. J. Inequal. Pure and Appl. Math, 9(2), 5-9.

*5:このあたり、記法が怪しいので困りました。

*6:Fredman, Michael L., and Dan E. Willard. "Surpassing the information theoretic bound with fusion trees." Journal of computer and system sciences 47.3 (1993): 424-436.