Codewars-Kata - „Wiederkehrende Sequenz“

Question

Ich versuche, die folgende Codewars-Kata zu lösen .

Wir erhalten eine Liste als
seq = [0, 1, 2, 2]

Wir müssen eine Funktion schreiben, die zunächst Elemente in der Liste mit der folgenden Logik hinzufügt.
wenn n = 3 und als seq[n]=2, wird die neue Liste seq = [0, 1, 2, 2, 3, 3] sein,
wenn n = 4 und als seq[n]=3, wird die neue Liste sein sei seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
wenn n = 5 und da seq[n]=3 ist, wird die neue Liste seq = [0, 1, 2, 2 sein , 3, 3, 4, 4, 4, 5, 5, 5] und so weiter.

Dann gibt die Funktion das n-te Element der Liste zurück.

Einige Elemente der Liste:
[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]

Einschränkung für Python:
0 <= n <= 2^41

Mein Code wird in meinem System für jeden Wert von n erfolgreich ausgeführt, einschließlich n = 2 ^ 41 (innerhalb von 2,2 s). Aber es läuft in Codewars ab. Kann mir jemand bei der Optimierung meines Codes helfen? Danke im Voraus.

Mein Code:

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

Das Erstellen der Liste nimmt viel Zeit in Anspruch. Beachten Sie, dass Ihr arr += [i] * arr[i]den gleichen Wert iimmer wieder wiederholt. Dies kann stark komprimiert werden, indem repeat(i, arr[i])stattdessen nur gespeichert wird. Dies gelingt in etwa 6 Sekunden, weit unter ihrer 12-Sekunden-Grenze:

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

Beachten Sie, dass n > 3wir in diesem Fall bereits mit der Zahl 3 beginnen und sie zweimal an die Liste anhängen. [0, 1, 2, 2]Daher brauchen wir vom Sequenzstart nur [2], also beginne ich mit arr = [[2]](was kürzer ist als [repeat(2, 1)], und chainnichts dagegen hat).

---

Alternativ ... beachten Sie, dass Sie sich viel schneller ausdehnen arr, als Sie es verbrauchen. Bei n=2 ⁴¹ wachsen Sie auf über 51 Millionen Elemente, aber Sie lesen tatsächlich weniger als die ersten 70.000. Sie könnten also an dieser Stelle aufhören, die Liste wirklich zu erweitern. Das gelingt in etwa 4,7 Sekunden:

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]

---

Und ... Sie können die beiden obigen Verbesserungen kombinieren, dh if arr_len < 70_000:auf die repeat-Version anwenden. Das gelingt dann in etwa 4,5 Sekunden.

Benchmark-Ergebnisse auf meinem PC für 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)

---

Oh und ein Style-Kommentar: Du machst das zweimal:

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

Die elseund die Einrückung des restlichen Codes sind unnötig und ich würde es vermeiden. Ich habe dies in den obigen Lösungen getan.