コードのパフォーマンスについて


コーディングテスト練習サイト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)`




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

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

* * *

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

あなたのコードの場合、

  * 最初の`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)と言うことになります。

* * *

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




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

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

* * *

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

あなたのコードの場合、

  * 最初の`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)と言うことになります。

* * *

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

