0

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

(参考)MaxProductOfThreeについて日本語で書かれた記事

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

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

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

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
2
  • 2
    「コーディングテストで答えるのにどちらがふさわしい?」という部分については、客観的な回答が難しく、このサイト向きの質問内容ではなさそうです。会社ごとに方針が異なるわけですし。どのような質問がこのサイト向きかについてはこちらのヘルプをご覧ください。
    – nekketsuuu
    Commented 2019年3月17日 13:56
  • 「実際に書いた」のコードはO(N**2)ではないですか? O(N**3)と判定されたのは、単純に総当たりで3要素の積を計算するコードではありませんか?
    – OOPer
    Commented 2019年3月17日 14:58

2 件の回答 2

2

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

ムーアの法則を信じるのであればコンピューターの計算速度は指数的に増加していくわけですが、それでも多項式の次数レベルの時間計算量の差は大事です。現実的には目の前の問題をすぐ解いて欲しいわけで、コンピューターの計算速度が充分大きくなってくれるのを待つのでは現状まだ間に合いません。

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

def repeat(n):
    for i in range(n):
        pass

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

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

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

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

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

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

1
  • ご回答いただきましてありがとうございます。
    – user32568
    Commented 2019年3月19日 3:18
0

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

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])

リザルト

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

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

1
  • ご回答いただきましてありがとうございます。
    – user32568
    Commented 2019年3月19日 3:18

この質問に回答するには、ログインする必要があります。