Geekly Articles each Day

コーダーインタビューとSnakeゲームの共通点は何ですか？


80年代または90年代に生まれた場合、おそらくスネークについて聞いたことがあるでしょう。 つまり、ほとんどの場合、Nokia 3310で非常に多くの時間を費やし、小さな画面で巨大なヘビを育てていました。 Nokiaの携帯電話について他に覚えていることはありますか？

放電していないバッテリーですよね？ このような「プリミティブ」な電話は、バッテリーを消耗させずに「スネーク」を長時間プレイすることに耐えましたか？

短い（そして不完全な）答え： スライディングウィンドウ方式に関するものです。

Snakeについての記事全体を書きたいと思いますが、この投稿では、それほど壮観ではありませんが、それでも非常に重要な方法を検討し、次のような質問に答えます。


インタビューの準備をしている場合、興味のある記事を読んでいる場合、または新しいことを学びたい場合は、読み続けてください。 同時に、余分な部分を安全にスキップして、最も興味深いセクションに進むことができます。

NB： 「Snake」だけに関心がある場合（そして、私たちはあなたを完全に理解しています）、投稿の最後に行くことができます。


始めましょう。

アルゴリズムプログラミングの複雑さにもかかわらず、問題を解決するために必要な原則のかなり短いリストがあります。 これらの原則の1つは、スライディングウィンドウ方式です。


図1.スライディングウィンドウ

ウィンドウパラダイム


スライディングウィンドウ方式は、トリミングのより一般的な原理から生まれました。

フレーミングとは、システムの状態を取得し、「ウィンドウ」と呼ばれるその部分だけに視野を制限することです。 これにより、トリミングアルゴリズムと、ウィンドウから見える要素に適用されるアルゴリズムとの間に分離が作成され、両方のアルゴリズムが簡素化されます。

特殊なケースとは、配列や文字列などの一連のオブジェクトで構成される状態です。 ウィンドウを設定すると、サブシーケンスが表示されます。 これで、シーケンスに値がなくなったかのように、この限られた間隔に処理を適用できます。 間隔を制限することにより、タスク全体を小さくします。 次に、スライディングプロパティについて考えます。ウィンドウを1つ右に移動し、処理を適用できる別のサブシーケンスを取得します。

そして、ここから冒険が始まります。 アルゴリズムを各ウィンドウに個別に適用すると、結果としてブルートフォース戦術が得られます。

ただし、スライディングウィンドウメソッドの長所は、ウィンドウシフトプロセス自体を利用するようにアルゴリズムの構造を変更できることです。 そして、これらすべての目標は、より優れた高速なアルゴリズムを作成することです。

少なくとも理論的には、スライディングウィンドウに適用されるほとんどすべてのアルゴリズムの実行速度を上げることができます。 ウィンドウをシフトすると、2つの要素のみが変更されます。 最も古いものはドロップアウトし、最新のものはフレームに落ちます。


図2.要素シフト（赤：廃止、緑：到着）

ラフ検索で長さk単一ウィンドウを処理するためにkステップが必要で、シーケンスにnウィンドウがある場合、ラフステップでは作業を完了するためにn·kステップが必要になります。 ただし、各ステップで変化する要素は2つだけなので、 2nほぼ比例した合計実行時間を達成できます。

シーケンスの単純な通過にO(n)かかると言う場合、これは、シーケンス全体ではO(n)よりも高速なアルゴリズムはないことを意味します。 この分析は、スライディングウィンドウ法の正しい適用が、 O(n)で実行できる完全なシーケンスを処理するアルゴリズムの発明につながることを示しています。

言い換えれば、彼は、問題を解決するのに理想的なアルゴリズムを発明できると約束しています。

必要な紹介を終えたら、このアルゴリズムの一般的な概念を使用して解決できる3つのプログラミングの問題を検討し、実際のケースでの使用方法の具体例を示します。

プログラミングの問題1：移動平均


解決する必要がある問題：一連の数値の移動平均を計算するアルゴリズムを作成します。

与えられた系列a0, a1, … an-1およびパラメーターk, 0 < k <= n各要素が元のシーケンスのk連続した要素の平均値になるように、新しいシーケンスを生成する必要があります。


図3. Eq平均

コンテキスト：移動平均は、入力ストリームを平滑化するのに役立ちます。 数値がノイズの影響を受ける場合、生データを表示するのは困難です。 以下の2つの図からわかるように、スムージングにより、より有益なスキームを取得できます。


図4.移動平均は入力を滑らかにします

この問題は、スライディングウィンドウ方式を使用して効果的に解決できます。 これらのアルゴリズムのほとんどに共通する特徴がすぐに明らかになります。最初のk-1要素は出力を生成しません。 ウィンドウ全体を埋める場合にのみ、結果の最初の部分を取得できます。 後続のすべてのウィンドウは、それぞれ1つの結果を作成します。 したがって、スライディングウィンドウアルゴリズムを使用したn要素のシーケンスは、 n-k+1結果のシーケンスを作成します。

それでは実装に移りましょう。 ウィンドウの平均値は、すべての要素の合計をウィンドウの長さで割ったものです。


図5. Eq Sum

この定式化により、スライディングウィンドウ方式を使用する利点がすぐにわかります。 ウィンドウ値の合計は、その前のウィンドウの値の合計から計算できます。


図6. Eqの最適化

最初のウィンドウの合計を計算するにはkステップかかり、次のウィンドウごとに追加の操作が2つだけかかります。

以下は、この回答のC ++実装で、最初のk要素を渡して最初の出力を作成します。 他のすべての出力数は、最適化された合計式を使用して計算されます。

 double* moving_average(double* data, int n, int k) { assert(data != NULL); assert(n > 0); assert(0 < k && k <= n); double* result = new double[n — k + 1]; double sum = 0; for (int i = 0; i < k; i++) { sum += data[i]; } result[0] = sum / k; for (int i = k; i < n; i++) { sum = sum — data[i — k] + data[i]; result[i — k + 1] = sum / k; } return result; }

このアルゴリズムの主なポイントは、元のシーケンスの各要素が最大2回処理されることです。これにより、 O(n)合計時間複雑度が作成されます。

プログラミング問題2：最大合計のサブシーケンス


解決すべき問題：すべての可能なサブシーケンスの合計が最大のサブシーケンスを見つけるためのアルゴリズムを作成します。

入力に負の値が含まれる場合、これは実際の問題になる可能性があります。

ここでも、スライディングウィンドウメソッドを使用して、 O(n)ランタイムでソリューションを作成できます。 今回だけ、ウィンドウの長さは一定ではありません。 実際、タスク自体は最適なウィンドウを見つけることであるため、プロセスの中でウィンドウの長さが変化する場合があります。


図7.最大量、スライド式ウィンドウを使用したソリューション

アイデアは、一定量のウィンドウが既にある場合に何が起こるかを監視することです。 次に、次の値を追加します。 この値は、ウィンドウの合計に追加できます。 しかし、これは完全に新しい単位長のウィンドウと見なすことができます。 質問をしてください：どれがより多くの量を持っているでしょうか？ それが何であれ、新しいウィンドウとして保存し、同じ手順を繰り返して次の入力値に移動します。 上の図を見てください。これは、ウィンドウがシーケンスに沿って徐々にスライドする様子を示しています。

勝ちのオプションは常に、現在の入力要素で終わる最大量のサブシーケンスになります。 各ウィンドウは、その合計が負になるとすぐに破棄されます。これは、数値だけが前の最大ウィンドウとの組み合わせよりも優れている状況です。

最後のステップはあと1つだけです-合計最大値の決定です。 すべてのウィンドウは、シーケンスの終わりに向かって滑るので候補です。 シーケンスの完了後、最大量のウィンドウが最大量のサブシーケンスになります。

以下は、C ++でのアルゴリズムの簡単な実装です。 繰り返しますが、シーケンスの各要素は2回以下と見なされます。これは、関数O(n)の合計時間の複雑さです。

 std::tuple<int, int, int> max_sum_subsequence(int* data, int n) { assert(data != NULL); assert(n > 0); int bestStart = 0; int bestLength = 1; int maxSum = data[0]; int curStart = bestStart; int curLength = bestLength; int curSum = maxSum; for (int i = 1; i < n; i++) { if (curSum < 0) { curStart = i; curLength = 1; curSum = data[i]; } else { curLength += 1; curSum += data[i]; } if (curSum > maxSum) { bestStart = curStart; bestLength = curLength; maxSum = curSum; } } return std::tuple<int, int, int>(bestStart, bestLength, maxSum); }

プログラミング問題3：すべてのkサブシーケンスの最大値


解決すべき問題：長さn数値シーケンス内の長さkすべてのサブシーケンスの最大値を計算するアルゴリズムを作成します。 注：これは難しい作業です。

このアルゴリズムは画像処理で使用されます。ご想像のとおり、ランタイムO(n)アルゴリズムは他のすべてのアルゴリズムよりも重要です。


図8.高値

ウィンドウをスライドすると、出力に含まれる最大値が作成されます。 解決の難しい部分は、与えられたウィンドウの最大値を与える公式がないことです。 その結果、要素の1つを取得できます。

しかし、スライディングウィンドウ方式を使用してもメリットがないとは言えません。 これがアイデアです。上の図に示すように、4つの値を持つウィンドウがあるとします。

追加の値がフレームに含まれる場合、既存の値との関係を理解する必要があります。 まず、ウィンドウがスライドし続けると、この新しい値がドロップアウトする前に、以前のすべての値がドロップアウトします。 これは重要な結論です。 前の値が新しい値よりも小さい場合、新しい、より大きな値が常にそれを覆い隠すので、それが最大値になることはありません。


図9 最大滑空

これにより、次の図に示すように、すべての新しい値を認識せず、ウィンドウがスライドするときにウィンドウ内で検出されたより小さい値をすべて削除するというアイデアにつながります。 この操作の結果は異なります。

右に追加された各値がすべての小さな値を削除する場合、ウィンドウには元のウィンドウの増加しない不連続なサブシーケンスのみが含まれます。 もう1つの結果は、現在明らかになっていることです。左端のウィンドウ要素は、計算する必要がある最大値です。


図10.スクリーニングの最大値

もう1つ詳細を明らかにする必要があります。 ウィンドウをスライドすると、シーケンスの左端の値がドロップアウトします。 この値は、より大きな値で既に削除されている可能性があります。 または、右側に続くすべての値を生き残ることができます。 後者の場合、入力からの値はフレーム内の左端の値になりますが、今度はそれを削除します。

次の図は、ウィンドウの長さが4の7つの要素のシーケンスに適用されるプロセス全体を示しています。


図11.合計の最大値

これでアルゴリズムの説明が完了し、実装が開始されます。 通常の実装は、双方向キュー（デキュー）に基づいています。 デキューは、両端からのキューの追加と削除をサポートし、これらの操作を使用してアルゴリズムを実装します。

 void insert_maximum_candidate(int value, bounded_deque<int> &maximums) { while (!maximums.empty() && maximums.back() < value) maximums.pop_back(); maximums.push_back(value); } void remove_maximum_candidate(int value, bounded_deque<int> &maximums) { if (!maximums.empty() && maximums.front() == value) maximums.pop_front(); } int* range_maximums(int* data, int n, int k) { assert(data != NULL); assert(n > 0); assert(0 < k && k <= n); bounded_deque<int> maximums(k); for (int i = 0; i < k — 1; i++) insert_maximum_candidate(data[i], maximums); int* result = new int[n — k + 1]; for (int i = k — 1; i < n; i++) { insert_maximum_candidate(data[i], maximums); result[i — k + 1] = maximums.front(); remove_maximum_candidate(data[i — k + 1], maximums); } return result; }

このソリューションでは、 fixed_dequeと呼ばれるfixed_deque独自の実装を使用します。 std::dequeとは異なり、このクラスは固定長データ用のバッファを保持します。これにより、実行が少なくとも1桁速くなります。 内部では、リングバッファとして機能し、非常に効率的です。 場合によっては、 fixed_dequeクラスにはstd::dequeと同じパブリックインターフェイスがあり（唯一の違いは、コンストラクタがバッファサイズを想定していることです）、必要に応じてstd::deque置き換えることができます。 実行速度が大幅に低下する以外は、他の影響はありません。

前の例のように、この実装の時間の複雑さを分析できます。 入力シーケンスの各値は、キューイングと削除の対象になります。 つまり、1つの入力番号に対して最大2つの操作が実行され、アルゴリズムの合計時間の複雑度はO(n)です。 また、このアルゴリズムには追加のスペースO(k)が必要です。ここで、kはウィンドウの長さです。 （以前のアルゴリズムではO(1)スペースしか必要なかったことに注意してください。）

箱の外側を考える


スライディングウィンドウ法に基づく3つのアルゴリズムを検討しました。 約束したとおり、それらはそれぞれO(n)実行されます。 また、まったく異なる2つの領域で同じ方法がどのように適用されるかを示したいと思います。

まず、TCP / IPなどのパケットルーティングプロトコルでは、スライドウィンドウを使用して、インターネットプロトコル（IP）と伝送制御プロトコル（TCP）をネゴシエートします。 IPは、パケットが送信された順序と同じ順序で受信されることを保証できません。 同時に、TCPはこの保証を提供するだけです。 ここで、スライディングウィンドウは、TCP / IPプロトコルバンドルの成功の最も重要なコンポーネントの1つになります。

TCPレシーバーは、予想されるパケットのウィンドウを維持します。 パケットは不完全な（しかしより現実的な）IPに到着し、対応するウィンドウ位置を埋めるために必要な順序で到着しない場合があります。 ただし、左端のパケットが到着するとすぐに、TCPウィンドウは可能な限り右側に移動し、送信者にすべての隣接パケットの受信を確認し、それらを出口に送信します。 これは、IPネットワークへの後続パケットの送信を開始する可能性について送信者に通知します。


図12. TCP-IP

2番目の（そして最後の）例が何に当てられるかはすでに推測しています。

もちろん、 「蛇」 。 このゲームが数十年前に登場したとき、ほとんどはノキアの携帯電話でそれを知っていました。


図13.ヘビ

推測？ ヘビ自体はスライディングウィンドウです！ ヘビが移動すると、画面上に2つのブロックだけを描画するだけで十分です。尾が背景ブロックになり、ヘビの頭の前の前の背景が新しい頭になります。


図14.「スネーク」=スライディングウィンドウ

スライディングウィンドウメソッドを適用した結果、ゲームの各フレームには、ヘビの長さに関係なく、最大2つのプリミティブブロックがかかります。 これにより、バッテリーを不必要に消費することなく、プリミティブなハードウェアにゲームを実装できました。

まとめると


この記事では、スライディングウィンドウと呼ばれる一般的なアルゴリズムを分析しました。 この手法を使用して、データシーケンス処理アルゴリズムを最適化できることを学習しました。 アプリケーションの成功により、この手法はn個のオブジェクトのシーケンスに対してO(n)で実行されるアルゴリズムの作成を提供します。これは、アルゴリズムの最適な設計です。

問題解決の具体例として、数値シーケンスで機能する3つの異なるアルゴリズムを開発しました。 これらのアルゴリズムはすべて、現実の世界で一般的なデータと画像処理を処理するために使用されます。 これが、スライディングウィンドウ方式が今日まで生き残った理由を説明しており、アルゴリズムを作成する際に有用なツールであり続けています。 そのため、技術面接で彼のことをよく耳にするでしょう。

Source: https://habr.com/ru/post/J347378/

More articles:


All Articles