Home-theater-designers
一連の数字や文字に対して演算を実行することは、プログラミングの重要な側面です。スライディング ウィンドウ アルゴリズムは、これを行うための標準アルゴリズムの 1 つです。
今日のMUOビデオ スクロールしてコンテンツを続けてください
これは、複数のドメインに導入されているエレガントで多用途のソリューションです。文字列操作から配列走査、パフォーマンスの最適化まで、このアルゴリズムは役割を果たすことができます。
では、スライディング ウィンドウ アルゴリズムはどのように機能し、Go でどのように実装できるのでしょうか?
スライディング ウィンドウ アルゴリズムを理解する
がある 多くのトップアルゴリズム プログラマとして知っておくと役立つもので、スライディング ウィンドウもその 1 つです。このアルゴリズムは、データのサブセットを効率的に処理および分析するために、一連のデータにわたって動的ウィンドウを維持するという単純な概念を中心に展開しています。
このアルゴリズムは、配列、文字列、またはデータのシーケンスを含む計算問題を解決するときに適用できます。
スライディング ウィンドウ アルゴリズムの背後にある中心的な考え方は、固定サイズまたは可変サイズのウィンドウを定義し、それを入力データ内で移動させることです。これにより、パフォーマンスを妨げる可能性のある冗長な計算を行わずに、入力のさまざまなサブセットを探索できます。
これがどのように機能するかを視覚的に表したものが次のとおりです。
ウィンドウの境界は、特定の問題の要件に応じて調整される場合があります。
Go でのスライディング ウィンドウ アルゴリズムの実装
一般的なコーディングの問題を使用して、スライディング ウィンドウ アルゴリズムがどのように機能するかを学習できます。つまり、指定された長さの部分配列の最大合計を見つけることができます。
このサンプル問題の目的は、次のサイズの部分配列を見つけることです。 k その要素の合計が最大の値になります。解関数は、入力配列とそれを表す正の整数という 2 つのパラメーターを受け取ります。 k 。
サンプル配列を次のようにします 数字 、以下のコードが示すように:
AirPodsをAndroidに接続できますか
nums := []int{1, 5, 4, 8, 7, 1, 9}
そして、部分配列の長さを次のようにします k 、値が 3 の場合:
k := 3
次に、長さ k の部分配列の最大合計を求める関数を宣言できます。
func maximumSubarraySum(nums []int, k int) int {
// body
}
ウィンドウはターゲット要素のコピーを格納する配列でなければならないと考えているかもしれません。これはオプションではありますが、パフォーマンスは悪くなります。
代わりに、ウィンドウの境界を定義してウィンドウを追跡するだけです。たとえば、この場合、最初のウィンドウの開始インデックスは次のようになります。 0 そして終了インデックスは k-1 。ウィンドウをスライドさせる過程で、これらの境界を更新します。
この問題を解決するための最初のステップは、サイズ k の最初の部分配列の合計を取得することです。次のコードを関数に追加します。
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
上記のコードは、アルゴリズムに必要な変数を宣言し、配列内の最初のウィンドウの合計を求めます。その後初期化されます 最大金額 最初のウィンドウの合計を使用します。
次のステップは、 窓をスライドさせる を繰り返すことで 数字 インデックスからの配列 k 最後まで。ウィンドウをスライドさせる各ステップで:
- アップデート ウィンドウ合計 現在の要素を追加し、次の要素を減算します。 ウィンドウスタート 。
- アップデート 最大金額 の新しい値が ウィンドウ合計 それよりも大きいです。
次のコードはスライディング ウィンドウを実装します。に追加します 最大サブ配列合計 関数。
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
ループが完了すると、最大の合計が得られます。 最大金額 、関数の結果として返すことができます。
return maxSum
完成した関数は次のようになります。
func maximumSubarraySum(nums []int, k int) int {
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
return maxSum
}
次の値を使用して、アルゴリズムをテストする main 関数を定義できます。 数字 そして k 以前から:
誰がグーグルドキュメントにアクセスできるかを確認する方法
func main() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
この場合の出力は次のようになります 19 、これは最大のサブ配列 [4, 8, 7] の合計です。
他の言語であっても、同じ手法を同様の問題に適用できるようになりました。たとえば、 Java ハッシュ マップ 、 例えば。
最適なアルゴリズムにより効率的なアプリケーションが実現
このアルゴリズムは、問題解決に関して効率的なソリューションの力を証明しています。スライディング ウィンドウによりパフォーマンスが最大化され、不必要な計算が排除されます。
スライディング ウィンドウ アルゴリズムと Go でのその実装をしっかりと理解することで、アプリケーションを構築する際に現実世界のシナリオに取り組むことができるようになります。