[アルゴリズム]
ダブリング(Doubling?)で検索しても、なかなか英語ではいい資料が出てこない。だったのですが、sataniC++様のブログ記事がかなり参考になりました。
- 蟻本でダブリングの章を読んでみたのですが、なぜそうなっているかの説明が不足しておりいまいちでした
コードの説明
上に示したコードは、次のような流れに沿って処理を行っています。
各要素について、すぐ次の要素next[0]を調べる
各要素について、next[0]を使ってnext[1]を求め、そのnext[1]を使ってnext[2]を求め、…としてnext全体を調べ上げる
上で求めたnextを使って実際にp番目の要素のQ個次の要素を求める
- 疑似コードをRuby化
- ただしこれだとNが全体の要素より小さい場合にしか対応できない
|
+
|
疑似コード１
|
|
|
# coding: utf-8
N = 6 # 全体の要素数
LOG_N = Math.log2(N).floor # log2(N)
# next_obj[k][i]で、i番目の要素の「2^k個次の要素」を指す
# (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、
# next_obj[k][i]が指し示す要素番号を-1とします)
next_obj = Array.new(LOG_N+1).map{Array.new(N, 0)}
# next_obj[0]を計算
for i in 0...N
next_obj[0][i] = (iの次の要素)
end
# nextを計算
for k in 0...LOG_N
for i in i...N
if next_obj[k][i] == -1
# 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありません
next_obj[k+1][i] = -1
else
# 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素です
next_obj[k+1][i] = next_obj[k][next_obj[k][i]]
end
end
end
# ----ここまで準備----
# p番目の要素の「Q個次の要素」を求めることを考えます
k = LOG_N -1
until k >= 0
# pがすでに存在しない要素を指していたら、
# それ以降で存在する要素を指すことはないためループを抜けます
break if p == -1
if ((Q >> k) & 1)
# Qを二進展開した際、k番目のビットが立っていたら、
# pの位置を2^kだけ次にずらします
p = next_obj[k][p]
end
k-=1
end
|
|
+
|
疑似コード２
|
|
|
# ビット表記で見たとき最も左の位置で1が立つもの（1-indexed)
def msb(x)
x.to_s(2).size - 1
end
# ビット表記で見たとき最も右の位置で1が立つもの（1-indexed)
def lsb(x)
msb(x & -x)
end
N = 600 # 全体の要素数（仮）
LOG_N = msb(Q)+1 # ビットの最大桁数
# next_obj[k][i]で、i番目の要素の「2^k個次の要素」を指す
# (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、
# next_obj[k][i]が指し示す要素番号を-1とします)
next_obj = Array.new(LOG_N+1).map{Array.new(N, 0)}
# next_obj[0]を計算
for i in 0...N
next_obj[0][i] = (iの次の要素)
end
# nextを計算
for k in 0...LOG_N
for i in i...N
if next_obj[k][i] == -1
# 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありません
next_obj[k+1][i] = -1
else
# 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素です
next_obj[k+1][i] = next_obj[k][next_obj[k][i]]
end
end
end
# ----ここまで準備----
# p番目の要素の「Q個次の要素」を求めることを考えます
# Q個次の数値を２進数化して逆転させたもの
QBIT = Q.to_s(2).reverse
# Rubyのfor文は逆にわかりにくい
(1..LOGN).to_a.reverse_each do |k|
# Qを二進展開した際、k番目のビットが立っていたら、pの位置を2^kだけ次にずらします
pidx = next_obj[k-1][pidx] if 1 == QBIT[k-1].to_i
end
|