Codewars kata - "Secuencia repetitiva"

Aug 17 2020

Estoy tratando de resolver el siguiente kata de Codewars .

Nos dan una lista como
seq = [0, 1, 2, 2]

Tendremos que escribir una función que, en primer lugar, agregue elementos en la lista usando la siguiente lógica.
si n = 3 y como seq[n]=2, la nueva lista será seq = [0, 1, 2, 2, 3, 3]
si n = 4 y como seq[n]=3, la nueva lista será be seq = [0, 1, 2, 2, 3, 3, 4, 4, 4]
si n = 5 y como seq[n]=3, la nueva lista será seq = [0, 1, 2, 2 , 3, 3, 4, 4, 4, 5, 5, 5] y así sucesivamente.

Entonces la función devolverá el n-ésimo elemento de la lista.

Algunos elementos de la 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]

Restricción para Python:
0 <= n <= 2^41

Mi código se ejecuta correctamente en mi sistema para cualquier valor de n, incluido n=2^41 (dentro de 2,2 s). Pero se agota en Codewars. ¿Alguien puede ayudarme a optimizar mi código? Gracias por adelantado.

Mi código:

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]

Respuestas

2 superbrain Aug 18 2020 at 00:13

Construir la lista lleva mucho tiempo. Tenga en cuenta que arr += [i] * arr[i]repite el mismo valor iuna y otra vez. Esto se puede comprimir mucho simplemente almacenando repeat(i, arr[i])en su lugar. Esto tiene éxito en unos 6 segundos, muy por debajo de su límite de 12 segundos:

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

Tenga en cuenta que en el n > 3caso, comenzamos ya con el número 3, agregándolo dos veces a la lista. Por lo tanto, del comienzo de la secuencia [0, 1, 2, 2]solo necesitamos [2], así que empiezo con arr = [[2]](que es más corto que [repeat(2, 1)], y chainno importa).


Alternativamente ... tenga en cuenta que se está extendiendo arrmucho más rápido de lo que lo está consumiendo. Para n=2 41 , lo aumenta a más de 51 millones de elementos, pero en realidad está leyendo menos de los primeros 70 mil. Entonces podría dejar de extender realmente la lista en ese punto. Esto tiene éxito en unos 4,7 segundos:

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]

Y... puede combinar las dos mejoras anteriores, es decir, aplicar eso if arr_len < 70_000:a la repeatversión -. Eso luego tiene éxito en aproximadamente 4.5 segundos.

Resultados de referencia en mi PC para 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)

Ah, y un comentario de estilo: dos veces haces esto:

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

El elsey la sangría de todo el código restante son innecesarios y lo evitaría. Lo he hecho en las soluciones anteriores.