Codewars kata - "Tekrarlayan Sıra"

Question

Aşağıdaki Codewars kata'yı çözmeye çalışıyorum .

Sıra = [0, 1, 2, 2] şeklinde bir liste verdik

Öncelikle, aşağıdaki mantığı kullanarak listeye elemanlar ekleyecek bir fonksiyon yazmamız gerekecek.
n = 3 ve sıra [n] = 2 ise, yeni liste sıra = [0, 1, 2, 2, 3, 3]
olacaktır , eğer n = 4 ve sıra [n] = 3 ise, yeni liste seq = [0, 1, 2, 2, 3, 3, 4, 4, 4] olmak
n = 5 ve seq [n] = 3 ise, yeni liste sıra = [0, 1, 2, 2 olacaktır , 3, 3, 4, 4, 4, 5, 5, 5] vb.

Daha sonra işlev, listenin n'inci öğesini döndürecektir.

Listenin bazı öğeleri:
[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 için Kısıtlama:
0 <= n <= 2 ^ 41

Kodum, n = 2 ^ 41 (2.2s içinde) dahil olmak üzere herhangi bir n değeri için sistemimde başarıyla çalışıyor. Ama Codewars'ta zaman aşımına uğradı. Kodumu optimize etmeme yardım eden var mı? Şimdiden teşekkürler.

Kodum:

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]

Answer 1

Listeyi oluşturmak çok zaman alır. arr += [i] * arr[i]Aynı değeri idefalarca tekrarladığınızı unutmayın . Bu, repeat(i, arr[i])bunun yerine saklanarak çok sıkıştırılabilir . Bu, 12 saniye sınırının çok altında, yaklaşık 6 saniyede başarılı olur:

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

Bu n > 3durumda, 3 rakamı ile başladığımızı ve listeye iki kez eklediğimizi unutmayın. Böylece dizinin başlangıcına [0, 1, 2, 2]sadece ihtiyacımız var [2], bu yüzden ile başlıyorum arr = [[2]](ki bundan daha kısa [repeat(2, 1)]ve chainumursamıyor).

---

Alternatif olarak ... arrtükettiğinizden çok daha hızlı yaydığınızı unutmayın . N = 2 ^{41 için} , bunu 51 milyondan fazla elemana yükseltirsiniz, ancak aslında ilk 70 binden daha azını okuyorsunuz. Böylece bu noktada listeyi gerçekten genişletmeyi bırakabilirsiniz. Bu yaklaşık 4,7 saniyede başarılı olur:

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]

---

Ve ... yani iki iyileştirmeler üzerinde birleştirmek olduğunu uygulayabilirsiniz if arr_len < 70_000:için repeat-version. Bu daha sonra yaklaşık 4,5 saniyede başarılı olur.

Bilgisayarımdaki n = 2 ⁴¹ için karşılaştırma sonuçları :

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)

---

Oh ve bir stil yorumu: Bunu iki kez yaparsınız:

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

elseVe kalan tüm kod girinti gereksizdir ve bunu önleyeceğini. Bunu yukarıdaki çözümlerde yaptım.