LeetCodeの問題集、718. Maximum Length of Repeated Subarrayがacceptされたので、備忘録として。
概要
2つの配列に共通する、一番長い「連続する」配列を探す問題。
例)
[1,2,3,4,5][1,6,3,4,5]の2つなら、[3,4,5]。
[1,3,4,5]ではない。
簡単のために、コード以外の場ではlen(nums1)をm、len(nums2)をn、m >= nとする。
コード
今回はpythonでの記述。2通りのコードを。
その①は、テストに通らなかったもの。その②がテストに通ったもの。
コードその①
def searcher(n1, n2, h, l = 0):
#「共通する配列の長さ」の探索についてはバイナリサーチを用いて計算コスト削減。
# 計算コスト：O(log(min(len(nums1),len(nums2)))) ... [1]
s = (h + l) / 2
#その長さの配列が共通するか、については全探索。
# 計算コスト：O(len(nums1)×len(nums2)) ... [2]
#走査数はi,jともに[配列の大きさ]-[調べたい共通配列の大きさ]+1になる。
for i in range(len(n1) - s + 1):
for j in range(len(n2) - s + 1):
if n2[j:j + s] == n1[i:i + s]:
if h == l:
return s #長さだけわかればいいので、見つかり次第打ち切り。
else:
return searcher(n1, n2, h, s + 1)
#答えがloに張り付いた場合とhi=loになるまで答えが出なかった場合の処理
if h == l or s - 1 < l:
return s - 1
else:
return searcher(n1, n2, s - 1, l)
#トータルで[1] × [2]の計算コストがかかる。
class Solution(object):
def findLength(self, nums1, nums2):
return searcher(nums1, nums2, min(len(nums1), len(nums2)))
コードその②
class Solution(object):
def findLength(self, nums1, nums2):
ans = 0
# 配列のゼロ埋め。ほぼ定型文。
# 下式の関係上ひとつ前の列だけ保持しておけばいいのでメモリ節約のため2列に。
tmparr = [[0] * (len(nums2) + 1) for i in range(2)]
#配列を後ろから攻める(理由は後述)。
for i in range(len(nums1) - 1, -1, -1):
for j in range(len(nums2) - 1, -1, -1):
# ここのif-elseに関しても後述。
if nums2[j] == nums1[i]: tmparr[1][j] = tmparr[0][j + 1] + 1
else: tmparr[1][j] = 0
# max値の更新。
ans = max([max(tmparr[1][:]), ans])
# メモ用配列の更新。
tmparr[0][:] = tmparr[1][:]
return(ans)
考え方
コードその①
1から$\min(m,n)$までひたすらnum1とnum2に共通する配列がないかを全探索する、という方法。動的計画法を知るまでこの方法しか浮かばなかったので、タイムアウトしそうと気乗りしないまま、プロトタイプに着手(コードその①の前身)。コード例にも書いた通り、全探索すると
$$
\sum_{k=1}^{n}(m-k+1)(n-k+1) \Rightarrow O(mn^2)
$$
という計算コストになる。案の定、タイムリミットではじかれる。そこで少しでも軽減するため、共通配列の長さの探索に対して覚えたてのバイナリサーチを適用。n=5~60ぐらいで理論上は10倍の速さになる($O(mn\log n)$)ので、遅いけれども何とか重たいテストケースをパスできるんじゃないか(そして答えを見よう！)と思ったのだが、こちらも撃沈。
というわけで、全探査計画、失敗。コードその②に続く。
コードその②
結局現状の努力を尽くしたコードその①がダメなので、より高速に動く方法をカンニング。幸い、一般会員でもleetcode公式の回答を見ることができたので、読む。
...動的計画法を使って...つまりdp[i][j]=...
この時点で「あ、知らんわ」となったので、まず 「動的計画法」 の勉強をすることに。
基礎的な説明に関しては下の備考のリンクが大変参考になったので、そちらへ。
で、今回の場合の考え方。「 num1[i]、num2[j]が互いに共通する配列の何文字目か 」をdp[i][j]として表現する。つまり全体にわたってdp[i][j]を求めて、max(dp)してやれば、最高で何文字連続で共通してるかがわかる、という仕組み。
次にdp[i][j]をどう置くかについて。num1[i]≠num2[j]の場合は、dp[i][j]=0で良いだろう。
一方、num1[i]=num2[j]である場合は、その隣のnum1[i+1]とnum2[j+1]を確認して、dp[i][j]を決める。num1[i+1]=num2[j+1]である場合は…(以下繰り返し)
つまり、2次元の場合分けがある漸化式のようなものである。上記を式にすると次の通り。
dp[i][j]=\left\{
\begin{array}{ll}
0 & (\text{num1}[i] \neq \text{num2}[j]) \\
dp[i+1][j+1]+1 & (\text{num1}[i] = \text{num2}[j])
\end{array}
\right.
これを解く際は、数Bのように一般項を求めて…というわけにはいかないので、ここは地道にステップの最初から上の式に当てはめ、m × nの表を順々に埋めていく。という作業が 動的計画法 の基本。コードその②ではn,mを降順にループさせ、dp[i][j]を埋めていっている。ただし、2×nの配列をうまいこと使ってメモリの節約をしている。
この動的計画法による計算コストは$O(mn)$であり、コードその①から更に$log(n)$分短くすることができる。
最後に、以下に簡単な導出プロセスを載せておく。
例)num1=[5,2,4,1,3]、num2=[1,2,4,1]とした場合の動きのイメージ
自分の結果
計算速度：上から数えて約20%のところ
メモリ使用量：上から数えて約20%のところ
選択した解法によって速さが全く異なるので、全体感としてはあまり意味をなさない気がするが、一応動的計画法のいるべきところに収まっているようなので一安心。
備考
動的計画法よりも早く動作するアルゴリズムに、「バイナリサーチを用いた ローリングハッシュ 」、というのも回答例にあり、その特徴から計算コストが$O((m+n)\log n)$まで削減できるらしい。これについてはまた別の機会で勉強することにする。
- 動的計画法の勉強に使ったサイト
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
うさぎでもわかるアルゴリズム 動的計画法