コーディング面接とSnakeゲームに唯一共通すること | POSTD

80年代か90年代に生まれた方ならおそらく、「Snake」というゲームのことをご存じでしょう。「ご存じ」とはつまり、Nokia 3310のちっぽけな画面上でたわいもない巨大ヘビを育てるのに膨大な時間を費やしていたのではないかということです。Nokiaの携帯電話について、皆さんは他にどんな特徴を覚えていますか？ バッテリーが長持ちしたことではないでしょうか。 Nokiaはとても”原始的な”携帯電話であったにもかかわらず、バッテリーを使い果たすことなくSnakeゲームで何時間も遊べたのは、どういう訳だったのでしょう？ 理由の大部分は、優れた強固なコンポーネントのおかげでした。しかし、貢献度はそれより低く、あまり語られることもありませんが、スライディングウィンドウと呼ばれる手法も長時間のプレイに役立っていたのです。 Snakeだけを扱った記事を1本書きたいのは山々ですが、実は本記事では後者の、魅

[mumumu-tan]

Sliding Window technique の解説。部分配列をずらしたものは、既存の部分配列を少し変えて再構成できるので、O(N^2) を O(N) に改善できる。

[vanbraam]

コーディング面接関係なく,とても実用的かつ面白い話だった

[proverb]

“スライディングウィンドウ”

[Eiichiro]

Basicでゲーム作ってた時にこのテクニック使ってたなぁ。描画が遅すぎ対応だったのだけど、理論で説明するとこうなるのか。

[tick2tack]

アルゴリズムのスライディングウィンドウについて。どういう場面で使われるかの事例が多いのがよい

[benridane111]

どちらもヘビーでしょう。

[wordi]

スライディングウィンドウアルゴリズム