Codewars kata- "반복적 인 시퀀스"
다음 Codewars kata 를 해결하려고합니다 .
목록은
seq = [0, 1, 2, 2]로 제공됩니다.
먼저 다음 논리를 사용하여 목록에 요소를 추가하는 함수를 작성해야합니다.
n = 3이고 seq [n] = 2이면 새 목록은 seq = [0, 1, 2, 2, 3, 3]이
됩니다. n = 4이고 seq [n] = 3이면 새 목록은 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]
파이썬 제약 :
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])대신 저장하면 훨씬 압축 될 수 있습니다 . 이는 12 초 제한보다 훨씬 낮은 약 6 초 만에 성공합니다.
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으로 시작하여 목록에 두 번 추가합니다. 따라서 순서의 시작 [0, 1, 2, 2]우리가 만하면 [2]내가 시작 그래서, arr = [[2]](보다 짧은있는 [repeat(2, 1)], 그리고 chain마음을하지 않습니다).
또는 ... arr당신이 그것을 소비하는 것보다 훨씬 더 빨리 확장하고 있다는 점에 유의 하십시오. n = 2 41의 경우 5 천 1 백만 개 이상의 요소로 성장하지만 실제로는 처음 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]
그리고 ... 위의 두 가지 개선 사항을 결합 할 수 있습니다. 즉, -version에 적용 할 if arr_len < 70_000:수 repeat있습니다. 그러면 약 4.5 초 만에 성공합니다.
내 PC에서 n = 2 41에 대한 벤치 마크 결과 :
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)
오 그리고 스타일 코멘트 : 당신은 이것을 두 번합니다 :
if ...:
return ...
else:
...
else모든 나머지 코드의 들여 쓰기는 불필요하고 나는 그것을 피할 것. 위의 솔루션에서 그렇게했습니다.