2022-11-30

anond:20221129085814

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

ある業務Webシステム検索結果の表示件数を5/10/20から選べるようになっててて,URLパラメーターで「?n=20」とかやって送ってた。メニューからは三つのしか選べないが手で書き換えれば100とか200とか選べる穴が空いてた。

で,よりによってメモリ使用量がO(n^2)になるコードを書いていやがった。n=500でOutOfMemoryError。リモートから面白いようにサービスを落とせた。

CSを知ってるやつなら,コードを書いた瞬間から「これnの上限チェック入れないとまずいな」とわかるんだよ。というか,普通にこのコードはまずいと考えてアルゴリズムをなおして,O(1)でDBレコード全件持ってきても落ちないコードにできてたはず。

  • という説明すらサッパリわからないよ…. orz

    • かぞえあげお姉さんの動画をみて、感覚をつかもう。 https://www.youtube.com/watch?v=Q4gTV4r0zRs

    • 検索ヒット1件につき10MBのメモリを食うAPIをメモリ4GBのインスタンスで動かしてて、そこに400件のリクエストが来たらどうなる?

      • あっ!…. (ボクにも掛け算はできたのだ)

        • これ掛け算で増えていくならまだ普通というか、許せるほうで 本当にヤバいパターンでは平気で冪乗とかそういうオーダーで増えていっちゃうのね   たとえば「10件の候補から任意の3...

  • やらかしてるのは採用した企業のほうじゃん。 何自己責任にしてるの?

  • anond:20221130083458 逆に聞きたいんだけど、元増田の文章を読んで、この内容を理解してないと思って書いた? 俺は元増田は明らかに理解してると思うから、もう一回元増田の文章読んで...

    • やはり国語力。国語力のないプログラマーはゴミ同然

    • いや,もと増田がランダウのO記法を知ってるのはわかってるよ。知ったうえで,そんなのはフレームワークや言語で隠蔽されているから知らなくてもいいと主張している。で,私は,い...

      • はい来ました後付けの言い訳。だからソフト屋は嫌いだっつうんだよ じゃあさ、n=50000000でOutOfMemoryErrorになったとするじゃん? 計算複雑性理論とかO(1)とか1ミリも関係ないよね? 要...

        • この増田はなんでこんな喧嘩腰なのか。うんこ出なかったのか?

          • 人権無視のメモリ2G環境とかに晒されているプログラマーは常にイライラしている

            • それってもはや虐待レベルじゃん.. (WindowsXPでも使ってるん?w)

          • ごめん関係ないことでちょっとイライラしてた うんこはちゃんと出てる 言うにしても、言い方ってあるよね とは言え主張を曲げる気はない……

          • 組み込み系なんだと思う 組み込み・リアルタイム人材はデフォルトがRTOSのように喧嘩腰だし、そういうインターフェイス仕様ってだけなので気にする必要ない

        • えーとこれを書いた増田だが、超恥ずかしい勘違いがあったのでt-tanakaさんに謝罪します O(1)はO(1)よね。メモリ消費量も計算時間も増えない。コンピューターサイエンス分かってないとこ...

          • あー,うん。そう。メモリはO(1)ね。ループでもメモリ使用量は一定って処理は珍しくないよ。CPUは,さすがにO(n)よりは減らないだろうが。 別のツリーでも,ちゃんとテストしろとか上...

        • 横だけど計算複雑性理論よりバックエンドのテストカバレッジだろってのは同意だわ 個人的にはカバーしてないこと自体が鯖落とした奴にお前が悪いって怒鳴っとけばいいだろ的思想に...

  • 似たような内容だけど、正規表現も爆発する入力が存在する。pcreみたいな計算理論における正規言語を超えたものだと、信頼できない入力を食わせるのはDoS攻撃できるのでよくない。一...

    • /^(x|x)*$/ がアウトで、 /^(x|y)*$/ がセーフなのよく分からない・・・

      • 正規表現をパースするコードを読んでみよう。それでわかると思うよ。  (てゆうか、Software Tools あたりで勉強しなかった?)

    • でね。それを聞いたコンピューターをよくわかってないお客様がね。「入力された正規表現を実行前に検証して爆発しないものだけを実行するようにしてください」とかいう要件をつけ...

  • コンピュータサイエンス増田爆誕

  • これを得意げに書いてると思うと興奮する

  • n = n > 20 ? 20 : n; コンピュータサイエンスわからなくても この1行入れるだけで良くね?

    • その一行を入れる発想、 それ自体がコンピュータサイエンスの賜物なんだよ。 つまり、君は、コンピュータサイエンスが分かっているということなのだ。

    • それ条件分岐要る? ビットマスクとかで簡単にできないの

      • できません

        • 分岐したら遅くなるじゃん、剰余とかマスクとかで分岐なしにしようよ

          • x86じゃあるまいし、今のアーキテクチャなら単純な演算のための分岐の時は投機実行とかやっててストールしないようにしてるんやろ知らんけど

          • 組み込み系の方ですか? ベアメタルとかの。

            • ARMも条件付き命令あるから、最大値へのクリップ処理程度ではほとんど遅くならないんとちゃうか ARM64は知らん

  • その程度のことに気づけばいいのか CS完全にマスターした!

  • そんなのCS以前の問題じゃね

  • CS で習う計算複雑性って実用からは少し離れた抽象的なもので、現実的には一兆年かかるが多項式アルゴリズムが存在するので云々〜みたいな、わりと天文学的な話がされてる。 計算量...

  • 一粒万倍だな。草生える。

  • 俺はとあるIT系の人だが、自分が面接をするときは計算量のオーダーについて話せない人はまず採用しないことを上申する。 入ってくる要素が高々数kBくらいで、せいぜい数十個くらいな...

  • 元増田だってオーダーの話してんだし業務に必要なら意識すんだろ CS知ってたら上限チェックするのかもしれないけど、実務なら5/10/20しか選べないならそれ以外の数字をはじくだろアホ...

    • いかにも、自己流でやってきたような感じだな。 開発標準とかある会社ならもう少しまともなこと言いそうだけど。

  • https://anond.hatelabo.jp/20221130083458 コンピュータサイエンスの知識がないならば サービスをダウンさせうるパフォーマンスのコードを書いてしまう → わかる パラメータがとりうる値を...

記事への反応(ブックマークコメント)

ログイン ユーザー登録
ようこそ ゲスト さん