2

Codechef の初心者向けの問題である Enormous Input Testを解決しようとしています。私のコード

a,b = [ int(i) for i in raw_input().split()]
print [input()%b==0 for i in range(a)].count(True)

タイムアウトします。基本的な for ループを使用する別のソリューションは、うまく機能しているようです。

リスト内包表記は、基本的な for - ループよりも速いと思います。では、なぜ前者は遅いのでしょうか? また、この場合にジェネレーターを使用すると、使用されるメモリが削減され、計算がより高速に実行されます。

4

1 に答える 1

5

forリストの理解が基本的なループよりも速いと思うのはなぜですか? (ヒント: どちらも同じ基本命令を使用して実装されています。)

コードは次のような方法で実行されます。

a, b = ...
temp = []
for i in range(a):
    temp.append(int(raw_input()) % b == 0)
print temp.count(True)

ご覧のとおり、メモリ内に大きなリストを作成し、それを反復処理して 2 番目のリストを作成し、次に 2 番目のリストを反復処理してカウントを作成します。リストを作成する必要はありません。

a, b = ...
count = 0
for i in xrange(a):
    if int(raw_input()) % b == 0:
        count += 1
print count

一部のコンパイラはハイロモーフィズムを最適化して中間リストを削除できますが、これが可能な Python 実装を私は知りません。そのため、手動で最適化するのに行き詰まっています。

注:input何をしているのかを理解していない限り、Python 2.x では使用しないでください。使用するコードを変更しました。int(raw_input())これは安全ですが、input()危険です。

于 2012-06-11T04:42:47.657 に答える