0

コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題で、書いたコードのパフォーマンスが悪かったのですが、どのように改善すれば良いのでしょうか。

パフォーマンスの良いコードの書き方がよくわかっていないので、学べるサイトや教材などももしおすすめのものがあれば教えていただきたいです。

FrogRiverOne coding task - Learn to Code - Codility
上記のFrogRiverOneについて日本語で書かれた記事

書いたコード

python

def solution(X, A):
    result = 0
    tmp = 0
    #iは配列番号
    for i in range(0, len(A)):
        #jは1からXまでの数
        for j in range(1, X+1):
            #そもそもjが要素にない場合
            if j not in A:
                result = -1
                return result
                break

            #もし配列番号iの要素がjならtmpにその要素番号を格納
            elif A[i] == j:
                if tmp < A.index(j):
                    tmp = A.index(j)
    result = tmp
    return result

パフォーマンス結果
Detected time complexity:O(N ** 2)

4
  • 前のご質問でもありましたが、コードのインデントが正しく反映されていないようです。ご自身の質問は編集できるはずですので、前のご質問を含めて修正していただけるようお願いします。
    – OOPer
    Commented 2019年3月17日 3:40
  • 1
    Lesson 4のreading materialのPDFにほとんど答が書いてあるようなものだと思いますが、読まれましたか?
    – orangecat
    Commented 2019年3月17日 3:44
  • @Nao さん、コードの貼り付け方ですが、まずはコードをそのままコピー&ペーストし、その後ソースコードを範囲選択してエディタ上部の {} を押すと勝手に整形してくれます。どうぞお試しください :)
    – nekketsuuu
    Commented 2019年3月17日 3:45
  • @nekketsuuu コードを貼るまえに{}を押していました。失礼しました。
    – user32568
    Commented 2019年3月17日 4:47

2 件の回答 2

1

パフォーマンスの良いコードの書き方がよくわかっていないので、学べるサイトや教材などももしおすすめのものがあれば教えていただきたいです。

コードのパフォーマンスの上げ方は問題領域によって様々です。「このサイトや教材を読めば、いつでもパフォーマンスの良いコードが書ける」と言ったものはありません。特に今回のような問題の場合、「どういった処理にどの程度のコストがかかるのかを把握しておく」「無駄なことをしていないか」などを常にチェックする癖を付けるしかないでしょう。


で、そのようなチェックをする場合に、「多重ループ」は要注意のポイントです。「本当にループでないと処理できないのか」「(特に内側のループ内で)時間のかかる処理を行っていないか」などを見直してみてください。

あなたのコードの場合、

  • 最初のfor iでN回ループ

  • その内側のfor jでX回ループ

  • さらにその中で使われているin演算やindexメソッドはO(N)のコストがかかる

と言うことで、全体としてはO(N * X * N)の時間コストがかかる処理になっています。

このうち「位置 1 から X 全てに葉が落ちているかチェック」するのだけで、O(X * N)の処理を行っています。「位置 1 から X 全てに葉が落ちているかチェック」するのは本当にそんな複雑な処理でしょうか?


あなたのコードで、その部分が複雑になってしまうのは、「ある時刻でどの位置に葉が落ちているか」を覚えておく変数を用意していないからでしょう。空間計算量(要はメモリ使用量)は問われていないのですから、「ある時刻でどの位置に葉が落ちているか」を覚えるようなリストを用意してしまうと良いでしょう。

私はPython使いではないので、あまり綺麗なコードは書けないですが、例えばこんな感じ:

def solution(X, A):
    # 場所ごとに葉が落ちたかどうかを覚えておくリスト
    fallenAt = [False] * (X+1)
    #iはAのインデックス(=時間)
    for i in range(0, len(A)):
        # 落ちてきた葉の場所
        j = A[i]
        # その場所に葉があることを覚えておく
        fallenAt[j] = True
        # 全部の場所が葉で埋まったのなら終了
        if all(fallenAt[1:X+1]):
            return i
    # Aを全部なめても全ての場所が埋まらない
    return -1

このコードの中でall関数は、引数の要素数Xに対してO(X)の時間コストがかかる処理なので、全体としては、O(N * X)となります。


さらに突き詰めると、そもそも「位置 1 から X 全てに葉が落ちているかチェック」する場合、X箇所のうち何箇所に葉が落ちているかの数さえわかれば、毎回「ある時刻でどの位置に葉が落ちているか」を全部の位置について調べる必要はないはずです。(ただ、「まだ葉が落ちていない場所に落ちた」か「すでに葉が落ちている場所にまた落ちた」かを区別する必要はあるので、「ある時刻でどの位置に葉が落ちているか」を表すリストは必要になります。)

コードに直すと例えば、こんな感じ:

def solution(X, A):
    # 場所ごとに葉が落ちたかどうかを覚えておくリスト
    fallenAt = [False] * (X+1)
    # 葉で埋まっている場所の数
    numFallen = 0
    #iはAのインデックス(=時間)
    for i in range(0, len(A)):
        # 落ちてきた葉の場所
        j = A[i]
        # その葉が、まだ葉が落ちていなかった場所に落ちたか
        if not fallenAt[j]:
            # その場所に葉があることを覚えておく
            fallenAt[j] = True
            # 新たに葉で埋まった場所の数をカウント
            numFallen += 1
        # 全部埋まったのなら終了
        if numFallen == X:
            return i
    # Aを全部なめても全ての場所が埋まらない
    return -1

あなたがリンク先にあげているページのコードはこの方針で書かれています。ループの内側には何かの要素数に比例して処理時間が増えるような処理は書かれていないので、全体でもO(N)と言うことになります。


他にもっとうまいやり方もあるかも知れませんが、考え方は参考にしていただけると思います。

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

「FrogRiverOne」という問題の内容が理解できていないのだと思います。
ちゃんと理解できていれば、もっと素直なコードが書けたでしょうから。

「日本語で書かれた記事」から推測すると
『川岸に蛙が居ます。
川には、岸にある樹から葉っぱが落ちてきます。
川の流れはとても穏やかなので、落ちた葉っぱはほとんど動きません。
こちらの岸から向こう岸まで、葉っぱが連なって落ちたら、蛙は葉っぱを伝って向こう岸まで渡ることができます。
川の幅は、葉っぱX枚分です。
葉っぱは1秒に1枚落ちてきますが、その落ちる場所はいろいろです。
配列Aは葉っぱの落ちる場所を示していて、開始からt秒後に落ちる葉っぱの位置(岸から何枚分離れているか)はAのt番目にあります。

蛙が渡れるようになるのは、開始から何秒後かを答えなさい』
という感じでしょう。

「日本語で書かれた記事」にコードが示されていますが、その構成は以下のようになっています
あ:準備)葉っぱがある(そこの落ちた事がある)かどうかを記録する配列B(大きさは、川幅分の葉っぱの枚数)を用意して、時間(t)は0にする。
い:毎秒行う処理)配列Aの内容(葉っぱの落ちる位置)を順に見ていって、その位置に葉っぱが落ちた事が無ければ(配列Bのその位置の値が0なら)、配列Bのその位置の値を1にして(葉っぱがあることを記録)、向こう岸までの使える葉っぱの数(cnt)を+1する。(葉っぱの落ちる場所が向こう岸の先(Xより大きい)なら無視(なにもしない))
時間(t)を+1する。
う:完了の判断)使える葉っぱの数がXに等しくなったら、向こう岸まで葉っぱが連なって渡れるようになった訳だから、その時のtを答えて、終わり。
使える葉っぱの数がXと等しくないなら、足りない葉っぱがあるので、"い"に戻る。

このプログラムでは、"い"の部分が何度か繰り返し実行されますが、繰り返しのループは1つだけなので、高々1次(配列Aの長さ程度)の繰り返しにしかなりません。

質問に書かれたコードは、配列Aの繰り返しループ(外側のループ)の中に、別のループ(何を意図したものか判りませんでした)があるので、2次("配列Aの長さ" * X)の繰り返しとなります。("Detected time complexity:O(N ** 2)" 時間複雑度がNの二乗というのは、そういう意味です)

この問題はO(N)の複雑性しかありません。それに対してO(N**2)のコードを回答をしたら「パフォーマンスが悪い」と評価とされますよね。

パフォーマンスを上げるには、”無駄なことをしない”ことを徹底する。
それしかありません。

この操作は必要なのか? を問い続けると、パフォーマンスの良いコードが書けるようになると思います。

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

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