Codewarskata-「反復配列」
私は次のCodewarskataを解決しようとしています。
seq = [0、1、2、2]としてリストが与えられます。
まず、次のロジックを使用してリストに要素を追加する関数を作成する必要があります。
n = 3でseq [n] = 2の場合、新しいリストはseq = [0、1、2、2、3、3]になり
ます。n= 4でseq [n] = 3の場合、新しいリストは次のようになります。 be seq = [0、1、2、2、3、3、4、4、4]
n = 5の場合、seq [n] = 3の場合、新しいリストはseq = [0、1、2、2 、3、3、4、4、4、5、5、5]など。
次に、関数はリストのn番目の要素を返します。
リストのいくつかの要素：
[0、1、2、2、3、3、4、4、4、5、5、5、6、6、6、6、7、7、7、7、8、8 、8、8、9、9、9、9、9、10、10、10、10、10、11、11、11、11、11、12、12、12、12、12、12、13、13 、13、13、13、13、14、14、14、14、14、14、15、15、15、15、15、15、16、16、16、16、16、16、16、17、17 、17、17、17、17、17、18、18、18、18、18、18、18、19、19、19、19、19、19、19、20、20、20、20、20、20 、20、20、21、21、21、21、21、21、21、21]
Pythonの制約：
0 <= n <= 2 ^ 41
私のコードは、n = 2 ^ 41（2.2秒以内）を含むnの任意の値に対してシステムで正常に実行されます。しかし、Codewarsではタイムアウトになります。誰かが私のコードを最適化するのを手伝ってくれますか？前もって感謝します。
私のコード：
def find(n):
arr = [0, 1, 2, 2]
if n <= 3:
return arr[n]
else:
arr_sum = 5
for i in range(3, n+1):
arr_sum += i * arr[i]
if arr_sum >= n:
x = (arr_sum - n) // i
return len(arr) + arr[i] - (x+1)
else:
arr += [i] * arr[i]
回答
リストの作成には時間がかかります。 arr += [i] * arr[i]同じ値をi何度も繰り返すことに注意してください。これは、repeat(i, arr[i])代わりに保存するだけで大幅に圧縮できます。これは約6秒で成功し、12秒の制限をはるかに下回ります。
from itertools import chain, repeat
def find(n):
if n <= 3:
return [0, 1, 2, 2][n]
arr = [[2]]
arr_sum = 5
arr_len = 4
for i, arr_i in enumerate(chain.from_iterable(arr), 3):
arr_sum += i * arr_i
if arr_sum >= n:
x = (arr_sum - n) // i
return arr_len + arr_i - (x+1)
arr.append(repeat(i, arr_i))
arr_len += arr_i
このn > 3場合、すでに番号3から始めて、リストに2回追加していることに注意してください。したがって、シーケンスの開始[0, 1, 2, 2]、我々は唯一の必要な[2]Iで始まるので、arr = [[2]]（よりも短くなっている[repeat(2, 1)]、とchain気にしません）。
あるいは...arrあなたがそれを消費しているよりもはるかに速く伸びていることに注意してください。n = 2 41の場合、5,100万要素を超えるまで増加しますが、実際には最初の7万未満を読み取っています。したがって、その時点でリストを実際に拡張するのをやめることができます。これは約4.7秒で成功します。
def find(n):
arr = [0, 1, 2, 2]
if n <= 3:
return arr[n]
arr_sum = 5
arr_len = 4
for i in range(3, n+1):
arr_sum += i * arr[i]
if arr_sum >= n:
x = (arr_sum - n) // i
return arr_len + arr[i] - (x+1)
arr_len += arr[i]
if arr_len < 70_000:
arr += [i] * arr[i]
そして...上記の2つの改善を組み合わせることができます。つまり、それif arr_len < 70_000:をrepeat-versionに適用します。その後、約4.5秒で成功します。
n = 2 41のPCでのベンチマーク結果：
Your original: 1.795 seconds
My first one: 0.043 seconds (42 times faster)
My second one: 0.041 seconds (44 times faster)
The combination: 0.026 seconds (69 times faster)
ああ、スタイルコメント：あなたはこれを2回行います：
if ...:
return ...
else:
...
else残りのすべてのコードのとインデントは不要なので、避けたいと思います。私は上記のソリューションでそうしました。