Python でスライディングウィンドウを実装する方法

スライディングウィンドウは、項目の連続した範囲を保ちながら、リストや文字列の中を移動させる手法です。Pythonでは、次のウィンドウの答えを、内容をすべて再計算せずに直前のウィンドウから更新できる場合に役立ちます。以下では、固定サイズのウィンドウ、重複しない文字を扱う可変サイズのウィンドウ、合計が目標値を満たすウィンドウという、よく使われる3つの形を紹介します。

スライディングウィンドウ法とは？

ウィンドウとは、左端と右端の位置で定まる範囲です。長さを固定することも、アルゴリズムが項目を追加したり削除したりするのに合わせて変えることもできます。ウィンドウ内の要素は連続しているため、スライディングウィンドウは部分配列や部分文字列を扱う問題に適しています。間に抜けがある任意の選び方を、そのまま表す手法ではありません。

この手法を使うと、同じ計算の繰り返しを減らせることがあります。たとえば、あるウィンドウの合計を計算した後に1つ先へ移動する場合、出ていく値を引き、入ってくる値を足せば更新できます。この更新は定数時間で行えます。全体の計算量は個々のアルゴリズムや使うデータ構造によって異なるため、スライディングウィンドウを使えば必ず高速化したり、すべての問題が O(n) 時間になったりするわけではありません。

サイズ K の部分配列の最大合計を求めるスライディングウィンドウの実装

数値のリストと正のウィンドウサイズ k が与えられたら、まず先頭の k 個の値を合計します。次に、ウィンドウを1つずつ進め、範囲から出る値と新たに入る値を使って合計を更新します。これまでに得た合計の最大値を保持します。この例では、k が正でない場合やリストより大きい場合に None を返し、入力条件を明確にしています。

[2, 1, 5, 1, 3, 2] に対して k = 3 とすると、ウィンドウは [2, 1, 5]、[1, 5, 1]、[5, 1, 3]、[1, 3, 2] です。プログラムは最大の合計を出力します。リストの長さを n とすると、時間計算量は O(n)、追加の空間計算量は O(1) です。

def max_sum_subarray(values, k):
    if k <= 0 or k > len(values):
        return None

    window_sum = sum(values[:k])
    best_sum = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum

values = [2, 1, 5, 1, 3, 2]
k = 3
print(max_sum_subarray(values, k))

このサンプルコードは実行用に示しています。ここでは実行結果を主張していません。

重複しない最長部分文字列を求めるスライディングウィンドウ

この問題では、ウィンドウ内に重複する文字がないようにします。右端を文字列に沿って動かし、新しい文字を集合に追加します。その文字がすでに集合にある場合は、重複がなくなるまで左端を進め、範囲から出る文字を集合から削除します。条件を満たす状態に戻したら、最長の長さを更新します。

各端点は前方へ最大1回しか進まず、各文字も集合に最大1回追加され、最大1回削除されます。そのため、長さ n の文字列に対する時間計算量は O(n)、空間計算量は O(min(n, 文字種の数)) です。PythonはUnicodeコードポイント単位で反復します。基底文字と結合文字からなる文字のように、利用者が1文字と認識する書記素が複数のコードポイントを含む場合があります。

def longest_unique_substring_length(text):
    window_chars = set()
    left = 0
    best_length = 0

    for right, char in enumerate(text):
        while char in window_chars:
            window_chars.remove(text[left])
            left += 1
        window_chars.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

text = "abcabcbb"
print(longest_unique_substring_length(text))

このサンプルコードは実行用に示しています。ここでは実行結果を主張していません。

合計が目標値以上となる最短の部分配列を求めるスライディングウィンドウ

この方法では、合計が目標値以上になる連続した部分配列のうち、最も短いものを探します。すべての値が非負であることが前提です。現在の合計が目標値以上になったとき、左側の値を取り除いても合計が増えることはないため、ウィンドウを縮めて、より短い有効な範囲を見つけられます。負の値があるとこの考え方は成り立たず、別のアルゴリズムが必要です。

条件を満たす部分配列がない場合、関数は 0 を返します。値が非負で目標値が正なら、各位置は最大1回追加され、最大1回削除されるため、時間計算量は O(n)、追加の空間計算量は O(1) です。目標値が0以下の場合、要素を使わずに条件を満たせるので、このコードは長さ0の答えを返します。

def min_subarray_length(target, values):
    if target <= 0:
        return 0

    left = 0
    running_sum = 0
    shortest = len(values) + 1

    for right, value in enumerate(values):
        running_sum += value
        while running_sum >= target:
            shortest = min(shortest, right - left + 1)
            running_sum -= values[left]
            left += 1

    return 0 if shortest > len(values) else shortest

values = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_length(target, values))

このサンプルコードは実行用に示しています。ここでは実行結果を主張していません。

まとめ

スライディングウィンドウは、リストや文字列内の連続した範囲を考えるのに役立ちます。サイズが決まっている場合は固定ウィンドウを選び、重複しない文字や目標合計のような条件で範囲が決まる場合は端点を調整します。この手法を使う前に、ウィンドウの移動に合わせて保持する状態を更新できるか、またアルゴリズムの前提が入力に合っているかを確認してください。ここではPythonのよくある面接問題を取り上げましたが、ほかの制約がある場合は別の方法が適していることもあります。

よくある質問

1. スライディングウィンドウはどんなときに使いますか？ 部分配列や部分文字列などの連続範囲を扱い、左右どちらか、または両方の端点を動かしながら現在の結果を更新できる問題で使います。
2. すべてのスライディングウィンドウ・アルゴリズムは O(n) ですか？ いいえ。ここで示した例が線形時間なのは、端点の移動回数と各ステップの更新量が限られているためです。ほかのアルゴリズムでは、移動ごとにより多くの処理が必要な場合があります。
3. この最小合計ウィンドウは負の数にも使えますか？ このままでは使えません。ウィンドウを縮める規則は値が非負であることを前提としており、負の値があると項目を取り除いた後に合計が増えることがあります。
4. 部分配列と部分列の違いは何ですか？ 部分配列は連続しています。部分列は順序を保ったまま位置を飛ばせるため、ウィンドウではすべての部分列を列挙できません。