Twitter上に流れてて、面白そうなので自分もやってみました。
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!|paizaオンラインハッカソンVol.1
新人女子の書いたコードを直すだけの簡単なお仕事です!
20代帰国子女、某有名国立大卒で、現在プログラマーをやっています。ECサイトのプログラムを開発していますが、コードがやけに長いし、効率が悪いような気がしています。センパイ助けてください!
もちろん、言語はC#。
サイト上には0.03秒といった驚異的な結果が載っていますが、そこら辺は気にせず自分の感じたとおりに新人女子を助けてみました。
まずは素直に実装
仕様に書いてあることを何も考えずに実装してみました。
大きな方針としては以下の様に考えました
- 入力された商品のリストを作成
- キャンペーン価格のリストを作成
- 商品リストから2商品の組み合わせリストを作成
- キャンペーン価格毎に組み合わせリストからキャンペーン価格以下の最大値 を取得
結果はというと・・・
テストケース1:success 1.1秒
テストケース2:invalid 1.32秒
テストケース3:invalid
まぁ、遅いかもしれないけど動くやろーと思っていたのですが、テストケース2でランタイムエラーが発生してました(´ω`)
情報としてはこれだけなので、なんのエラーが起きてるのかよくわからない状態。 とりあえず、テストデータの量を増やしてみようと商品の件数を最大の200,000件にしてテストしてみました。
すると、組み合わせリストを作成する箇所で System.OutOfMemoryException が発生していました。
ちゃんと考えて無駄を無くすそう
冷静に考えると、単純に20万件の商品の組み合わせを作成しようとすると、約20万×10万通り(計算式は下であってるはず)になるわけで、そりゃメモリも足りなくなるでしょうよと・・・
その中には重複している数字もあって無駄だよねってことで無駄を省きにかかりました。
商品リスト
まずは商品リストから無駄を省きます。
商品リストに追加する同一価格の商品は2つまでにする
組み合わせる際、同じ合計額にならないようにするためです。2つまでとしているのは、「値段が同じ商品でも構わないという」条件を満たすためです。2つの異なる商品(値段は同じでも構わないが必ず二つ) を購入し、
999,990より大きい価格の商品は登録しない
キャンペーンの金額は1,000,000で、商品の最低価格は10なので、999,990より大きい価格の商品はどの商品と組み合わせてもキャンペーン金額を上回ってしまいます。p_i (10 ≦ p_i ≦ 1000000) ※ 商品の価格
m_j (10 ≦ m_j ≦ 1000000) ※ キャンペーン設定金額
キャンペーン価格のリスト
商品リストから不要なデータが多少減っていますが、ここでもっと無駄を削ります。
最初は全パターンのリストを作成し、それを使って各キャンペーン金額に応じた価格を抽出していましたが、Test case 2でタイムオーバーになるのでちょっと方向転換し、キャンペーン金額毎にリストを作成することにしました。
- 商品リストをキャンペーン価格未満のものに絞る(リストxとyを作成する)
- リストxの1商品につき、リストyの商品との組み合わせでキャンペーン価格に最も近い値を結果リストに格納する
- 商品の合計値がキャンペーン価格とイコールになった場合はそれ以降の処理を行わない
そんな感じでいじった結果・・・
結果は出るようになった
結果は出るようになりました。
処理速度を見ると自分が凡人であることを思い知らされますね。最速の0.03秒とかってどんな魔法使ったの?って感じです*1。
でもいいんです。「自分の能力に納期を設けない」*2考えで行きたいと思うし、自分が幸せだと感じる選択をしたいと思うので、変に落ち込んだりせずに楽しくやっていきます。
それにしても、レベルの違いはあれど、考えるのって楽しいですね。こんな楽しい事があるんだよって、受験のための勉強しかしてなかった高校時代の自分に教えてあげたい。それは無理なので、息子ちゃんに少しでも伝えれたらいいかなと思います。
おまけ
ソース晒しておきます。正直、あーだこーだいじった後なので酷いです。これを元にソースを全部消して1から作り直すのが良いのでしょうけど、面倒なので…
高速化を目指すなら、LINQ使わない方が良いんだろうなぁと思います。でも、LINQだと集合が扱いやすいのが私にも分かりました。