【すらいでぃんぐうぃんどう】
スライディングウィンドウ とは？
最終更新:
💡 連続した範囲をずらし、使える計算結果を引き継ぐ
データ列の連続した範囲を「窓」として、位置や幅を変えながら処理する技法。固定幅の合計などでは、出入りする要素で状態を更新して計算を減らせる。窓を使えば必ず高速になるわけではなく、操作や条件に合った更新方法が必要。
📌 このページのポイント
- 固定幅または可変幅の連続した範囲を動かしながら処理する
- 合計なら、抜ける要素を引き、入る要素を足して更新できる
- N個の数の幅Kの合計は、毎回の足し直しでO(NK)、差分更新でO(N)になる
- TCPでも窓を使うが、合計の計算ではなく送信可能な範囲を管理する
ひよこ スライディングウィンドウって何をする技法なの？
ペンギン先生 データ列の連続した範囲を「窓」にして、ずらしながら処理するよ。たとえば連続する3個の数の合計を順に求める場合。窓の幅を固定する方法と、条件に合わせて広げたり縮めたりする方法があるんだ。
ひよこ 合計はどうやって引き継ぐの？
ペンギン先生 最初が2、5、1なら合計は8。窓を右へ1個ずらして5、1、8にすると、前の合計から抜ける2を引き、入る8を足して14になるよ。同じ範囲の計算を毎回やり直さず、出入りする要素で更新するんだ。
ひよこ どれくらい計算を減らせるの？
ペンギン先生 N個の数について幅Kの合計を毎回足し直すと、O((N−K＋1)K)で、ざっくりO(NK)だよ。最初の合計を作り、その後を差分更新すれば全体でO(N)になる。ただしKが3のような定数なら、足し直す方法もO(N)。窓を置くだけで常にO(N)になるわけではないんだ。
ひよこ 窓の幅を変えるのはどんなとき？
ペンギン先生 重複のない連続部分文字列を探す場合などだよ。右端を広げ、重複が出たら解消するまで左端を進める。何を記録し、いつ縮めればよいかを決めることが大切。条件が違えば同じ動かし方は使えないし、最大値なども合計と同じ引き算・足し算では更新できないよ。
ひよこ TCPのスライディングウィンドウも同じ？
ペンギン先生 範囲を動かす考え方は似ているけれど、目的が違うよ。TCPでは受信側が受け取れるデータの範囲を知らせ、送信側が受信確認や窓の情報に合わせて送信を進める。受信側の容量を超えないための流量制御で、実際の送信には輻輳制御なども関わるんだ。
まとめ：ざっくりこれだけ覚えればOK！
「スライディングウィンドウ」って出てきたら「窓をずらして効率よく処理するテクニック」と思えばだいたいOK！
📖 おまけ：英語の意味
「Sliding Window」 ＝ 滑動窓
💬 窓（Window）を滑らせる（Sliding）ように動かすからこの名前なんだよ