Skip to main content
無意味な改行削除
ソース リンク
OOPer
  • 1.9万
  • 2
  • 16
  • 33

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

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

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

ソース リンク
OOPer
  • 1.9万
  • 2
  • 16
  • 33

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

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


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

あなたのコードの場合、

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


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