Codewars kata - »Repetitive Sequence«

Question

Próbuję rozwiązać następujące kata Codewars .

Otrzymujemy listę w postaci
seq = [0, 1, 2, 2]

Będziemy musieli napisać funkcję, która najpierw doda elementy do listy, korzystając z następującej logiki.
jeśli n = 3 i jako seq [n] = 2, nowa lista będzie seq = [0, 1, 2, 2, 3, 3]
jeśli n = 4 i jako seq [n] = 3, nowa lista będzie be seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
jeśli n = 5 i as seq [n] = 3, nowa lista będzie seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5] i tak dalej.

Wtedy funkcja zwróci n-ty element listy.

Niektóre elementy listy:
[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]

Ograniczenie dla Pythona:
0 <= n <= 2 ^ 41

Mój kod działa pomyślnie w moim systemie dla dowolnej wartości n, w tym n = 2 ^ 41 (w ciągu 2,2 s). Ale w Codewars to się kończy. Czy ktoś może mi pomóc w optymalizacji mojego kodu? Z góry dziękuję.

Mój kod:

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

Tworzenie listy zajmuje dużo czasu. Zwróć uwagę, że arr += [i] * arr[i]w ikółko powtarza się tę samą wartość . Można to znacznie skompresować, po prostu przechowując repeat(i, arr[i]). Udaje się to w około 6 sekund, znacznie poniżej ich limitu 12 sekund:

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

Zwróć uwagę, że w tym n > 3przypadku zaczynamy już od cyfry 3, dodając ją dwukrotnie do listy. Zatem początek sekwencji [0, 1, 2, 2]potrzebujemy tylko [2], więc zaczynam od arr = [[2]](który jest krótszy niż [repeat(2, 1)]i chainnie przeszkadza).

---

Alternatywnie ... pamiętaj, że wydłużasz się arrznacznie szybciej, niż go zużywasz. Dla n = 2 ⁴¹ powiększasz ją do ponad 51 milionów elementów, ale tak naprawdę czytasz mniej niż pierwsze 70 tysięcy. Możesz więc przestać naprawdę rozszerzać listę w tym momencie. Udaje się to w około 4,7 sekundy:

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]

---

I ... możesz połączyć te dwa ulepszenia, tj . Zastosować to if arr_len < 70_000:do repeat-wersji. To się powiedzie w około 4,5 sekundy.

Wyniki testów porównawczych na moim komputerze dla 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)

---

Aha i komentarz dotyczący stylu: Robisz to dwa razy:

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

elseI wcięcie całego pozostałego kodu są niepotrzebne, a ja go uniknąć. Zrobiłem to w powyższych rozwiązaniach.