¿La complejidad de tiempo de la cadena iterativa anexa es realmente O (n ^ 2) u O (n)?

89

Estoy trabajando en un problema 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 escanear 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 ncadenas de cada uno 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 la agregación?

Alternativamente, si estuvieras dispuesto a enseñarme a 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.

usuario5622964
fuente
17
Alguien debería contarle al autor sobreurllib.urlencode
wim
11
@wim Está destinado a ser un problema de práctica sobre matrices y cadenas
user5622964
3
El propósito del libro es enseñar preguntas de entrevista, que comúnmente le piden que reinvente la rueda para ver el proceso de pensamiento del entrevistado.
James Wierzba
1
Dado que es Python, creo que hacer un rtrimy replacesería más preferido y en el estadio de O(n). Copiar sobre cadenas parece la forma menos eficiente.
OneCricketeer
2
@RNar ¿Puedes explicar cómo una copia puede llevar un tiempo constante?
James Wierzba

Respuestas:

83

En CPython, la implementación estándar de Python, hay un detalle de implementación que hace que esto generalmente sea O (n), implementado en el código que el ciclo de evaluación de código de bytes llama +o +=con dos operandos de cadena . Si Python detecta que el argumento de la izquierda no tiene otras referencias, llama reallocpara 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 realloctermina necesitando mover la cadena con frecuencia, el rendimiento se degrada a O (n ^ 2) de todos modos.

Sin el extraño detalle de implementación, 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 ++ que le gustaría usar +=.

user2357112 es compatible con Monica
fuente
2
Estoy mirando el código que vinculó ... parece que una gran parte de ese código está limpiando / eliminando punteros / referencias a la cadena que se agrega, ¿correcto? Y luego, hacia el final, realiza la _PyString_Resize(&v, new_len)asignación de memoria para la cadena concatenada, y luego memcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len);cuál hace la copia. Si el cambio de tamaño en el lugar falla, lo hace PyString_Concat(&v, w);(supongo que esto significa cuando la memoria contigua al final de la dirección de la cadena original no está libre). ¿Cómo muestra esto la aceleración?
user5622964
Me quedé sin espacio en mi comentario anterior, pero mi pregunta es si estoy entendiendo o no ese código correctamente y cómo interpretar el uso de memoria / tiempos de ejecución de esas piezas.
user5622964
1
@ user5622964: Vaya, recordé mal el extraño detalle de implementación. No existe una política de cambio de tamaño eficaz; solo llama reallocy espera lo mejor.
user2357112 apoya a Monica el
¿Cómo memcpy(PyString_AS_STRING(v) + v_len, PyString_AS_STRING(w), w_len);funciona? De acuerdo con cplusplus.com/reference/cstring/memcpy , tiene definición void * memcpy ( void * destination, const void * source, size_t num );y descripción: "Copies the values of num bytes from the location pointed to by source directly to the memory block pointed to by destination."el número en este caso es el tamaño de la cadena adjunta, y la fuente es la dirección de la segunda cadena, supongo. Pero entonces, ¿por qué el destino (primera cadena) + len (primera cadena)? ¿Doble memoria?
user5622964
7
@ user5622964: Eso es aritmética de punteros. Si desea comprender el código fuente de CPython hasta los extraños detalles de implementación, necesitará saber C. La versión supercondensada PyString_AS_STRING(v)es la dirección de los datos de la primera cadena, y agregar le v_lenda la dirección justo después de la cadena los datos terminan.
user2357112 apoya a Monica el
40

El autor se basa en una optimización que se encuentra aquí, pero que no es explícitamente confiable. strA = strB + strCes típicamente O(n), haciendo 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 appendoperación se amortiza O(1) (aunque puede fortalecerla O(1)asignando previamente la matriz al tamaño correcto), creando el bucle O(n).

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

njzk2
fuente
Esta respuesta es buena porque dice cómo concatenar cadenas.
user877329
respuesta precisa en el contexto del cálculo de tiempos de ejecución.
Intesar Haider
25

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 lo ''.join(seq)que es un O(n)proceso. En contraste, el uso de los operadores '+'o '+='puede resultar en un O(n^2)proceso porque se pueden construir nuevas cadenas para cada paso intermedio. El intérprete CPython 2.4 mitiga un poco este problema; sin embargo, ''.join(seq)sigue siendo la mejor práctica

OneCricketeer
fuente
3

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

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'))
geekidharsh
fuente