two - python concatenate string and variable

¿Es esta complejidad de tiempo realmente O(n ^ 2)?

Question

Estoy trabajando en un problema fuera de CTCI.

El tercer problema del capítulo 1 tiene que tomar una cadena como

''Mr John Smith ''

y le pide que reemplace los espacios intermedios con %20 :

''Mr%20John%20Smith''

El autor ofrece esta solución en Python, llamándola O (n):

def urlify(string, length):
    ''''''function replaces single spaces with %20 and removes trailing spaces''''''
    counter = 0
    output = ''''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == '' '':
            output = output + ''%20''
        elif char != '' '':
            output = output + char
    return output

Mi pregunta:

Entiendo que esto es O (n) en términos de escaneo a través de la cadena real de izquierda a derecha. ¿Pero no son inmutables las cadenas en Python? Si tengo una cadena y le agrego otra cadena con el operador + , ¿no asigna el espacio necesario, copia sobre el original y luego copia sobre la cadena adjunta?

Si tengo una colección de n cadenas de longitud 1, entonces eso requiere:

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

o O (n ^ 2) tiempo, ¿sí? ¿O me equivoco en cómo Python maneja los anexos?

Alternativamente, si estuviera dispuesto a enseñarme cómo pescar: ¿cómo haría para descubrir esto por mí mismo? No he tenido éxito en mis intentos de buscar en Google una fuente oficial. Encontré https://wiki.python.org/moin/TimeComplexity pero esto no tiene nada en las cadenas.

Answer 1

El autor confía en una optimización que está aquí, pero no es explícitamente confiable. strA = strB + strC es típicamente O(n) , lo que hace que la función O(n^2) . Sin embargo, es bastante fácil asegurarse de que todo el proceso sea O(n) , use una matriz:

output = []
    # ... loop thing
    output.append(''%20'')
    # ...
    output.append(char)
# ...
return ''''.join(output)

En pocas palabras, la operación de append se amortiza O(1) , (aunque puede hacer que sea fuerte O(1) preasignando la matriz al tamaño correcto), haciendo que el bucle O(n) .

Y luego la join también es O(n) , pero está bien porque está fuera del ciclo.

Answer 2

En CPython, la implementación estándar de Python, hay un detalle de implementación que hace que esto sea generalmente O (n), implementado en el código que el bucle de evaluación de bytecode llama para + o += con dos operandos de cadena . Si Python detecta que el argumento izquierdo no tiene otras referencias, llama a realloc para intentar evitar una copia cambiando el tamaño de la cadena en su lugar. Esto no es algo en lo que deba confiar, porque es un detalle de implementación y porque si realloc necesita mover la cadena con frecuencia, el rendimiento se degrada a O (n ^ 2) de todos modos.

Sin el detalle de implementación extraño, el algoritmo es O (n ^ 2) debido a la cantidad cuadrática de copia involucrada. Un código como este solo tendría sentido en un lenguaje con cadenas mutables, como C ++, e incluso en C ++ querría usar += .

Answer 3

Encontré este fragmento de texto en Python Speed> Use los mejores algoritmos y las herramientas más rápidas :

La concatenación de cadenas se realiza mejor con ''''.join(seq) que es un proceso O(n) . En contraste, usar los operadores ''+'' o ''+='' puede resultar en un proceso O(n^2) porque se pueden construir nuevas cadenas para cada paso intermedio. El intérprete de CPython 2.4 mitiga un poco este problema; sin embargo, ''''.join(seq) sigue siendo la mejor práctica

Answer 4

Para futuros visitantes: dado que es una pregunta CTCI, aquí no se requiere ninguna referencia al paquete de aprendizaje urllib , específicamente según OP y el libro, esta pregunta es sobre matrices y cadenas.

Aquí hay una solución más completa, inspirada en el pseudo de @ njzk2:

text = ''Mr John Smith''#13 
special_str = ''%20''
def URLify(text, text_len, special_str):
    url = [] 
    for i in range(text_len): # O(n)
        if text[i] == '' '': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''''.join(url) #O(n)


print(URLify(text, 13, ''%20''))