計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用..

計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用Webシステムは検索結果の表示件数を5/10/20件から選べるようになっててて，URLのパラメーターで「?n=20」とかやって送ってた。メニューからは三つの値しか選べないが手で書き換えれば100とか200とか選べる穴が空いてた。 で，よりによってメモリ使用量がO(n^2)になるコードを書いていやがった。n=500でOutOfMemoryError。リモートから面白いようにサービスを落とせた。 CSを知ってるやつなら，コードを書いた瞬間から「これnの上限チェック入れないとまずいな」とわかるんだよ。というか，普通にこのコードはまずいと考えてアルゴリズムをなおして，O(1)でDBレコード全件持ってきても落ちないコードにできてたはず。

[TakamoriTarou]

テストでこういうノリの奴で丸二つ付け足してたらシステムが落ちたので、これバグだろと言ったら「ハッキングは想定してないんで！！！」とか言われたこと思い出した。たぶんね、CS関係ないとおもうんだよ。

[t-tanaka]

書いた本人です。「自分が書いたコードのオーダーを意識し，不必要に大きくしない」というのは業務プログラマに必須の能力です。しかしCSを知らないと，そもそも「コードのオーダー」が何かを理解できません。

[honma200]

理解しやすく簡単な例を挙げたのに、「そんなの常識www」ブコメはどうかと思うぜ

[yhoriz]

計算複雑性理論の人ってむしろO(n^2)もO(1)も多項式時間だからヨシ！とか思ってそう（偏見）

[lacucaracha]

それくらいは私文卒の応用情報技術者のワイでも分かる（というか習った）んやが。コンピューターサイエンスってその程度のもんではないのでは。知らんけど。

[Guro]

複雑性を知らんでも、上限チェックは要るってわかるだろ。残念ながら説明のための事例として不適切。

[lainof]

「簡単な例」というコメントがあるけど、元増田が想定するプログラマはその程度の簡単なものしか扱わないのにCS必要なの？って疑問なんだと思うんだけど。

[turanukimaru]

物理学を知らなくても物理的な現象には遭遇する。例えば万有引力を知らなくても物が落ちることは知ってる。説明できるかはともかく。例がCSではないというのは「重力は物理学の話ではない」と言うのと同じだやめとけ

[unfallen_castle]

例えばSQLで不用意に交差結合すると結果セットが爆発して負荷で死ぬ、みたいな事案は経験則でも学べるけど、CSが分かっていれば経験則以前に類推出来るよね、というような話かなあ

[delphinus35]

これ CS 関係あるかなあ。テストもレビューも無いのが問題じゃ？

[zyzy]

これもそうだし、SQLの前提となる集合論の感覚への理解もそうだけど、ぱっと把握しやすいか、憶えるのに時間かかるかの差ではあるかな、と。事前に勉強してるかどうかの差でしかないといえばそう

[deep_one]

これは普通にやらかす奴が居そうだ。／コメントを見て。検索結果の表示数なんだから、普通は大きくしても落ちるほどメモリを食うはずがない。おそらく「一つ表示するたびに検索やり直す」とかになってるだろ。

[n314]

CSやったけど、普通にやらかすし、何ならwhereの条件が空でORMがdeleteで全部消しちゃったとかもある。そんでメモリ使用を改善したら、ブラウザのDL時間が超長くなってサーバーが詰まるとかも。例えが良くないような。

[bnckmnj]

ブコメみてるとやっぱ基礎ってよばれるものって「先人の失敗まとめから学ぶ厳選知識」であってあんま楽しいものではないから「成功したいのに失敗練習する意味ある？ｗ」って人間が定期的にわくんだなあ

[yuzuk45]

CSなくてもサーバ落ちるかもとは思うな

[uchya_x]

かつてとは比べ物にならないほどになった計算能力とメモリ空間だが、べき乗の暴力は桁の4つや5つくらいは簡単に破壊する力があるのです。

[yfukuda827]

なるほどわかりやすい。わたしもメモリ管理にうるさい現場で指導を受けたから、入力値にvalidation必須で、取得データ量を見て検索件数設定したりしてたけど、そういうのを授業でやっているよってことね！

[ch1248]

周りの反応、森を説明するのに中の木を例に上げたら、「木は森と関係あるの？そんなもんじゃないのでは。」と言われてる感じが……。

[takuver4]

みんなコンピュータサイエンスの定義というか範囲がバラバラで面白い。前の増田は文章もしっかりしてたし、このレベルは余裕で知っていたと思うな。

[xll]

“普通にこのコードはまずいと考えてアルゴリズムをなおして，O(1)でDBレコード全件持ってきても落ちないコードにできてたはず。” 無知で申し訳ないが、これはどのように組み立てたら実現出来るんです？

[strawberryhunter]

まあでも任意の数字を指定できるシステムは多いし、ハックする側としては便利。

[kiki-maru]

元増田さんのおっしゃりたいことが全く伝わっていないということがよくわかる例。

[spark7]

CSを学んだ・学んでないの境界線がブクマカ間でバラバラだからなんの議論にもなってない。せっかく元増田がそれなりのラインを示したのに。/ CS以前に国語力の問題が大きそう。

[oktnzm]

仕様が20までならn^2でも許容範囲ではあるだろう。パラメータにバリデーションかけるのが本筋に思う。あとnで書くコストと相談。／レコード全件のくだりはちょっと謎。レコード100万件ぐらいあったら落ちるのでは？

[cad-san]

『データ構造とアルゴリズム』は基礎的なCSだと思うのだけど、これをCS ではないかつCSを学ぶ必要はないという主張は、即ち「必要ないCSは必要ない」と言っているに過ぎずトートロジーなのでは。事前条件が未定義

[taguch1]

必要じゃないってんならそれでいいからアホなことで喧嘩すんな。意味があると思う人だけ勉強すればいいから、別に強制もしないから。

[aosiro]

CSなんて言葉は昨日初めて見たけど動きゃいいんだよ。クソコード書いたってプロジェクト抜ければあとは知らん。できるやつが直せや、それも仕事だろ。エンジニアの矜持なんてないよ

[yosio_ism]

仕事におけるコンピュータサイエンスの要否を語るのに前提をおいてないから、人によって想定してる学問的レベル感が合ってなくて議論になってないなあと思う。

[tokuniimihanai]

CSを学んでない人は「CSを学んだ状態で仕事をした経験」がないわけで、この件について語る資格を欠いているのは確か。「仮にCSを学んでいても仕事の役には立たなかったと思う」みたいな想像の話をされても困る

[queeuq]

CS学んでたらそれが0になるかっつーとそういうわけでもないだろうし説得力あんまない。小学校１年生の漢字書き取りテストに東大生を投入するような例え話。

[sirius_taka]

簡単な例が気に入らない人は競プロのアルゴリズム問題を解けばいくらでも難しい例に会えるけど

[programmablekinoko]

たかがページネーション、されどページネーションで、これが三段ジョインとかだったりそもそもSQLじゃなくて都度呼び出しとかだととんでもないことになる

[otation]

簡単な例より複雑な例が知りたい

[lnimroder]

CS知らないけどそのくらいの制限つけたりバリデーションやったりは普通にするからなあ

[kobito19]

"コンピューターサイエンスってその程度のもんではないのでは" 向こうにも書いたけどコンピュータサイエンスか否かの2択じゃなくてCSだったとしてもレベル1からレベル100まで様々あるのを理解せんとあかん。元質問者も

[tamanecoplus]

CS勉強した人でもやらかす時はやらかす。長年コードを書いてきたPGなら引き出しの数でそういうミスを防ぐイメージ

[ShionAmasato]

（計算複雑性理論を知らなくても）想定外の値が来たらまずいと勘付く人はバリデーションするから本筋ではないよな

[dhrname]

?n=-0.1

[degucho]

これ元増田が自説を補強するために書いたんじゃないの

[greenbow]

“選べるようになっててて”