53516


オンラインでコーディングテスト練習ができるCodilityのMaxProductOfThreeという問題のコードですが、テストケースが全て正解でもDetected
time complexityが`O(N**3)`だったので、テストスコアが44%/100%と表示されました。

[（参考）MaxProductOfThreeについて日本語で書かれた記事](http://codility-lessons-
jp.blogspot.com/2014/07/lesson-4-maxproductofthree.html)

参考記事で書かれている`O(N)`のコードはわかりにくいと感じてしまうのですが、実際にJobHuntingなどで課されるコーディングテストではコードの可読性とtime
complexityのどちらを優先させるべきなのでしょうか。

また、近年ではPCのスペックやクラウドのメモリなども増えましたが、それでもやはりできるだけtime
complexityを考えてコードを書くエンジニアの方が良いのでしょうか。

実際に書いた`O(N**3)`のコード

[code]

    def solution(A):
        for i in range(0, len(A)-1):
            for j in range(len(A)-1, i, -1):
                if A[j] < A[j-1]:
                    A[j-1], A[j] = A[j], A[j-1]
    
    
        check1 = A[len(A)-1] * A[len(A)-2] * A[len(A)-3]
        check2 = A[len(A)-1] * A[0] * A[1]
    
        print(A)
    
        if check1 > check2:
            return check1
        else:
            return check2
    
[/code]


CC BY-SA 4.0
2019-03-17T13:35:10.227
53499
2019-03-18T15:25:01.830
question
python python3 アルゴリズム
コーディングテストにおけるコードのTIMEOUT ERRORについて


部分的な回答：時間計算量を考えることは重要です。

[ムーアの法則](https://ja.wikipedia.org/wiki/%E3%83%A0%E3%83%BC%E3%82%A2%E3%81%AE%E6%B3%95%E5%89%87)を信じるのであればコンピューターの計算速度は指数的に増加していくわけですが、それでも多項式の次数レベルの時間計算量の差は大事です。現実的には目の前の問題をすぐ解いて欲しいわけで、コンピューターの計算速度が充分大きくなってくれるのを待つのでは現状まだ間に合いません。

特に問題となってくるのは、入力の数が多い場合です。手元の Python 環境(※)で試してみたところ、次の単純な O(N) のループでは、`N = 10
** 8` のとき実行におおよそ 1 秒かかりました。

[code]

    def repeat(n):
        for i in range(n):
            pass
    
[/code]

(※) 手元の環境：Core i7-8700, Python 3.7, Jupyter Notebook

このことから概算するに、同じ環境で同じ `N = 10 ** 8` を処理するとき、時間計算量によって次のように実行時間が変わってきます。

[code]

    O(N)   1 秒
    O(N²)  10⁸ 秒 ≒ 1000 日 ≒ 3 年
    O(N³)  10¹⁶ 秒 ≒ 3 億年
    
[/code]

数年待てば「実行に 1 秒かかる `N`
の数」が増え、上記の実行時間はもっと小さくなるはずですが、まだそれを待っていられるほどの増加率では無いという話です。

プログラムを書く際、すべての箇所で時間計算量を厳密に意識すべきとまでは言いませんが、それでもクリティカルな箇所において高速化はできるべきです ([参考:
When to
optimize](https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize))。もし高速化することでコードの可読性が落ちるのであれば、コメントやドキュメントの出番です。

なお、今考えてるのは時間計算量なのでメモリ量の増加は関係ありません。それは空間計算量やメモリの使い方の問題です。


CC BY-SA 4.0
2019-03-18T06:43:31.507
53516
2019-03-18T07:04:46.127
2019-03-18T07:04:46.127
19110
19110
53499
answer


「わかりにくい」と感じたのはCだからではないですか？Pythonであればもっと単純に書くことができますし、(どうしてこれで正解になるのかは別として)
**何をしているのか** がわかりにくくもありません。

[code]

    def solution(A):
        max_nums = [-1001, -1001, -1001]
        min_nums = [1001, 1001]
        for num in A:
            for nums, reverse in ((max_nums, True), (min_nums, False)):
                nums.append(num)
                nums.sort(reverse=reverse)
                nums.pop()
    
        return max(
            max_nums[0] * max_nums[1] * max_nums[2],
            max_nums[0] * min_nums[0] * min_nums[1])
    
[/code]

[リザルト](https://app.codility.com/demo/results/trainingRDXH89-7EQ/)

※ 私の計算だとO(N)のはずなんですが、なぜか、O(N*log(N))と判断されています。ちょっとそこはわかりません。

より良いアルゴリズムを選択すると可読性が極端に落ちると言うことはまれにしかないと思います。そう感じるのは、Pythonのような可読性が良い言語を使っていないか、可読性を無視して書いているからではないでしょうか。こういうコーディングテスト、特に競技プログラミングの解説やそこにある正解サンプル等は可読性を無視して取りあえず正解になるものをあげているというのも少なくないため、さも一般論のようにそう結論づけること自体が早急だと思います。


CC BY-SA 4.0
2019-03-18T15:25:01.830
53532
2019-03-18T15:25:01.830
7347
53499
answer