Kata Codewars - “Trình tự lặp lại”

Aug 17 2020

Tôi đang cố giải bài kata sau Codewars .

Chúng tôi được cung cấp một danh sách dưới dạng
seq = [0, 1, 2, 2]

Chúng ta sẽ phải viết một hàm, trước tiên, sẽ thêm các phần tử trong danh sách bằng cách sử dụng logic sau.
nếu n = 3 và seq [n] = 2, danh sách mới sẽ là seq = [0, 1, 2, 2, 3, 3]
nếu n = 4 và seq [n] = 3, danh sách mới sẽ là seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
nếu n = 5 và là seq [n] = 3, danh sách mới sẽ là seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5], v.v.

Khi đó hàm sẽ trả về phần tử thứ n của danh sách.

Một số phần tử của danh sách:
[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, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17 , 17, 17, 17, 17, 17, 18, 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]

Ràng buộc đối với Python:
0 <= n <= 2 ^ 41

Mã của tôi chạy thành công trong hệ thống của tôi với bất kỳ giá trị nào của n, bao gồm n = 2 ^ 41 (trong vòng 2,2 giây). Nhưng nó đã hết thời trong Codewars. Bất cứ ai có thể giúp tôi trong việc tối ưu hóa mã của tôi? Cảm ơn trước.

Mã của tôi:

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]

Trả lời

2 superbrain Aug 18 2020 at 00:13

Việc xây dựng danh sách mất rất nhiều thời gian. Lưu ý rằng bạn arr += [i] * arr[i]lặp đi lặp lại cùng một giá trị i. Điều này có thể được nén nhiều bằng cách lưu trữ repeat(i, arr[i])thay thế. Điều này thành công trong khoảng 6 giây, dưới giới hạn 12 giây của chúng:

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

Lưu ý rằng trong n > 3trường hợp này, chúng ta đã bắt đầu với số 3, thêm nó hai lần vào danh sách. Do đó, [0, 1, 2, 2]chúng ta chỉ cần bắt đầu trình tự [2], vì vậy tôi bắt đầu với arr = [[2]](ngắn hơn [repeat(2, 1)]và chainkhông phiền).

Ngoài ra ... lưu ý rằng bạn đang mở rộng arrnhanh hơn nhiều so với việc bạn đang sử dụng nó. Đối với n = 2 ⁴¹ , bạn tăng nó lên hơn 51 triệu phần tử, nhưng thực tế bạn đang đọc ít hơn 70 nghìn phần tử đầu tiên. Vì vậy, bạn có thể ngừng thực sự mở rộng danh sách tại thời điểm đó. Điều này thành công trong khoảng 4,7 giây:

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]

Và ... bạn có thể kết hợp hai cải tiến trên, tức là áp dụng điều đó if arr_len < 70_000:cho repeat-version. Điều đó sau đó thành công trong khoảng 4,5 giây.

Kết quả điểm chuẩn trên PC của tôi cho n = 2 ⁴¹ :

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)

Ồ và một bình luận kiểu: Bạn làm điều này hai lần:

if ...:
    return ...
else:
    ...

Việc elsethụt lề và thụt lề của tất cả các mã còn lại là không cần thiết và tôi sẽ tránh nó. Tôi đã làm như vậy trong các giải pháp trên.