Codewars kata - "ลำดับซ้ำ"
ฉันพยายามที่จะแก้ปัญหาดังต่อไปนี้กะตะ Codewars
เราได้รับรายการเป็น
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, 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, 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 รวมถึง n = 2 ^ 41 (ภายใน 2.2 วินาที) แต่มันหมดเวลาใน 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 แล้วต่อท้ายสองครั้งในรายการ ดังนั้นลำดับเริ่มต้น[0, 1, 2, 2]
เราต้องการเท่านั้น[2]
ดังนั้นฉันจึงเริ่มต้นด้วยarr = [[2]]
(ซึ่งสั้นกว่า[repeat(2, 1)]
และchain
ไม่สนใจ)
อีกทางหนึ่ง ... โปรดทราบว่าคุณกำลังขยายarr
ได้เร็วกว่าที่คุณกำลังใช้งานอยู่มาก สำหรับ n = 2 41คุณเพิ่มเป็นมากกว่า 51 ล้านองค์ประกอบ แต่จริงๆแล้วคุณอ่านน้อยกว่า 70,000 รายการแรก ดังนั้นคุณสามารถหยุดขยายรายการ ณ จุดนั้นได้อย่างแท้จริง สิ่งนี้สำเร็จในเวลาประมาณ 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]
และ ... คุณสามารถรวมการปรับปรุงสองอย่างข้างต้นเข้าด้วยกันนั่นคือใช้สิ่งนั้นif arr_len < 70_000:
กับrepeat
-version จากนั้นจะประสบความสำเร็จในเวลาประมาณ 4.5 วินาที
ผลลัพธ์มาตรฐานบนพีซีของฉันสำหรับ 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
และเยื้องทุกรหัสที่เหลือไม่จำเป็นและผมจะหลีกเลี่ยงได้ ฉันได้ทำในวิธีแก้ปัญหาข้างต้นแล้ว