Codewars kata - "ลำดับซ้ำ"

Aug 17 2020

ฉันพยายามที่จะแก้ปัญหาดังต่อไปนี้กะตะ 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]

คำตอบ

2 superbrain Aug 18 2020 at 00:13

การสร้างรายการต้องใช้เวลามาก สังเกตว่าคุณ 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และเยื้องทุกรหัสที่เหลือไม่จำเป็นและผมจะหลีกเลี่ยงได้ ฉันได้ทำในวิธีแก้ปัญหาข้างต้นแล้ว