Codewars kata - "Sequenza ripetitiva"

Aug 17 2020

Sto cercando di risolvere il seguente kata di Codewars .

Ci viene data una lista come
seq = [0, 1, 2, 2]

Dovremo scrivere una funzione che, in primo luogo, aggiunge elementi all'elenco utilizzando la seguente logica.
se n = 3 e seq[n]=2, la nuova lista sarà seq = [0, 1, 2, 2, 3, 3]
se n = 4 e seq[n]=3, la nuova lista sarà be seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
se n = 5 e seq[n]=3, la nuova lista sarà seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5] e così via.

Quindi la funzione restituirà l'n-esimo elemento della lista.

Alcuni elementi della lista:
[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]

Vincolo per Python:
0 <= n <= 2^41

Il mio codice viene eseguito correttamente nel mio sistema per qualsiasi valore di n, incluso n=2^41 (entro 2,2 secondi). Ma scade in Codewars. Qualcuno può aiutarmi a ottimizzare il mio codice? Grazie in anticipo.

Il mio codice:

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]

Risposte

2 superbrain Aug 18 2020 at 00:13

Costruire l'elenco richiede molto tempo. Nota che il tuo arr += [i] * arr[i]ripete lo stesso valore ipiù e più volte. Questo può essere molto compresso semplicemente memorizzando repeat(i, arr[i])invece. Questo riesce in circa 6 secondi, ben al di sotto del loro limite di 12 secondi:

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

Nota che nel n > 3caso, iniziamo già con il numero 3, aggiungendolo due volte all'elenco. Quindi dell'inizio della sequenza [0, 1, 2, 2]abbiamo solo bisogno [2]di , quindi inizio con arr = [[2]](che è più breve di [repeat(2, 1)], e chainnon importa).


In alternativa... nota che stai estendendo arrmolto più velocemente di quanto lo stai consumando. Per n=2 41 , lo fai crescere fino a oltre 51 milioni di elementi, ma in realtà stai leggendo meno dei primi 70 mila. Quindi potresti smettere di estendere veramente l'elenco a quel punto. Questo riesce in circa 4,7 secondi:

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]

E... puoi combinare i due miglioramenti di cui sopra, cioè applicarli if arr_len < 70_000:alla repeat-versione. Che poi riesce in circa 4,5 secondi.

Risultati di benchmark sul mio PC per 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 e un commento di stile: lo fai due volte:

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

Il elsee il rientro di tutto il codice rimanente non sono necessari e lo eviterei. L'ho fatto nelle soluzioni di cui sopra.