Codewars kata - "Séquence répétitive"

Aug 17 2020

J'essaie de résoudre le kata Codewars suivant .

On nous donne une liste sous la forme
seq = [0, 1, 2, 2]

Nous devrons écrire une fonction qui va, dans un premier temps, ajouter des éléments dans la liste en utilisant la logique suivante.
si n = 3 et comme seq[n]=2, la nouvelle liste sera seq = [0, 1, 2, 2, 3, 3]
si n = 4 et comme seq[n]=3, la nouvelle liste sera be seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
si n = 5 et comme seq[n]=3, la nouvelle liste sera seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5] et ainsi de suite.

Ensuite, la fonction renverra le n-ième élément de la liste.

Quelques éléments de la 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]

Contrainte pour Python :
0 <= n <= 2^41

Mon code s'exécute avec succès dans mon système pour n'importe quelle valeur de n, y compris n = 2 ^ 41 (dans les 2,2 s). Mais cela expire dans Codewars. Quelqu'un peut-il m'aider à optimiser mon code ? Merci d'avance.

Mon 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]

Réponses

2 superbrain Aug 18 2020 at 00:13

Construire la liste prend beaucoup de temps. Notez que votre arr += [i] * arr[i]répète la même valeur iencore et encore. Cela peut être beaucoup compressé en stockant simplement à la repeat(i, arr[i])place. Cela réussit en environ 6 secondes, bien en dessous de leur limite de 12 secondes :

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

Notez que dans le n > 3cas, nous commençons déjà par le numéro 3, en l'ajoutant deux fois à la liste. Ainsi, du début de la séquence, [0, 1, 2, 2]nous n'avons besoin que [2]de , donc je commence par arr = [[2]](qui est plus court que [repeat(2, 1)], et chainne me dérange pas).


Sinon... notez que vous vous allongez arrbeaucoup plus vite que vous ne le consommez. Pour n=2 41 , vous l'augmentez à plus de 51 millions d'éléments, mais vous lisez en fait moins que les 70 000 premiers. Vous pouvez donc arrêter de vraiment étendre la liste à ce stade. Cela réussit en environ 4,7 secondes :

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]

Et... vous pouvez combiner les deux améliorations ci-dessus, c'est-à-dire les appliquer if arr_len < 70_000:à la repeatversion -. Cela réussit alors en environ 4,5 secondes.

Résultats de benchmark sur mon PC pour 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)

Oh et un commentaire de style : vous faites ceci deux fois :

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

Le elseet l'indentation de tout le code restant sont inutiles et je l'éviterais. Je l'ai fait dans les solutions ci-dessus.