53493


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

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

[FrogRiverOne coding task - Learn to Code - Codility  
上記のFrogRiverOneについて日本語で書かれた記事](http://codility-lessons-
jp.blogspot.com/2014/07/lesson-2-frogriverone.html)

書いたコード

python

[code]

    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
    
[/code]

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


CC BY-SA 4.0
2019-03-17T02:43:21.903
53490
2019-03-17T05:27:17.363
2019-03-17T04:46:46.050
question
python python3 アルゴリズム
コードのパフォーマンスについて


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

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

* * *

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

あなたのコードの場合、

  * 最初の`for i`でN回ループ

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

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

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

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

* * *

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

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

[code]

    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
    
[/code]

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

* * *

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

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

[code]

    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
    
[/code]

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

* * *

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


CC BY-SA 4.0
2019-03-17T05:22:10.950
53493
2019-03-17T05:27:17.363
2019-03-17T05:27:17.363
13972
13972
53490
answer


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

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

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

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

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

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

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

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

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


CC BY-SA 4.0
2019-03-17T05:22:35.723
53494
2019-03-17T05:22:35.723
217
53490
answer