1

Estoy confrontando un problema con este problema. El resultado está bien pero no se valida porque corre muy lentamente :-(

He aquí el problema:

Al estudiar diferentes tipos de textos (novelas, leyes, artículos periodísticos ...), nos damos cuenta de que no solo las palabras utilizadas no son las mismas, sino que sus longitudes son estadísticamente diferentes: por ejemplo, es mucho más común encontrar palabras largas y complejas en un artículo de ley que en un libro para niños.

Para intentar determinar automáticamente a qué categoría pertenece un libro, queremos determinar el número de palabras de 1 letra, 2 letras, 3 letras ... que contiene.

Restricciones • El texto contiene un conjunto de palabras, separadas por espacios, sin puntuación. • Cada palabra contiene como máximo 100 caracteres.

Entrada • La primera línea contiene dos enteros: num_lineas y num_palabras.

Salida Para cada longitud de palabra posible, y solo si hubiera palabras de esta longitud en el texto, debe mostrar en una línea la longitud y el número de palabras de esa longitud, separado por dos puntos (debe colocarse un espacio a cada lado de los dos puntos).

Ejemplo:

Entrada 2 7

Salida

2 : 2

3 : 3

4 : 4

5 : 3

7 : 2

Mi programa:


num_lineas, num_palabras = map(int, input().split())
palabras = []
long_palabras = []
long = 0

for i in range(num_lineas):
   palabras.append(input().split())
   li_palabras = sum(palabras,[])

for i in range(len(li_palabras)):
   long_palabras.append(len(li_palabras[i]))
   long_palabras.sort()

for i in long_palabras:
   ol_long_palabras = long_palabras.count(i)
   if i > long:
      lng = i
      print(long,":",ol_long_palabras)

Gracias de antemano por tu respuesta :-)

1 respuesta 1

3

Cuestiones dudosas en el código

¿Para qué la lista li_palabras? Le asignas valores dentro de un bucle mediante la línea:

   li_palabras = sum(palabras,[])

pero ya que palabras es la lista de palabras encontradas hasta ese momento y mediante sum() le añades una lista vacía, el resultado es equivalente a haber hecho li_palabras = palabras. Además en cada iteración del bucle le estás cambiando el valor. Por suerte, ya que palabras va almacenando todas las palabras encontradas hasta ese momento, no se pierde ninguna. Pero lo mismo podrias hacer con el código siguiente, acumulando los resultados en li_palabras en vez de en palabras:

li_palabras = []
for i in range(num_lineas):
   li_palabras.extend(input().split())

El siguiente bucle que haces:

for i in range(len(li_palabras)):
   long_palabras.append(len(li_palabras[i]))
   long_palabras.sort()

es para crear otra lista que contenga las longitudes de las palabras. El bucle es más pythónico (y fácil de leer) si iteras por las propias palabras en lugar de por sus índices. Además no tiene sentido que llames a sort() en cada iteración del bucle. Mejor te esperas a haber creado la lista completa y llamas a sort() después. Así:

for palabra in li_palabras:
   long_palabras.append(len(palabra))
long_palabras.sort()

Finalmente el tercer bucle es el más ineficiente:

for i in long_palabras:
   ol_long_palabras = long_palabras.count(i)
   if i > long:
      lng = i
      print(long,":",ol_long_palabras)

Ya que en long_palabras tendrás la longitud de cada una de las palabras introducidas, es decir, si se han introducido 1000 palabras esta lista tendrá 1000 números, el bucle se estaría repitiendo todas esas veces.

En cada repetición del bucle haces un long_palabras.count(i), que obliga a recorrer de nuevo todos los elementos de la lista (en un bucle implícito que Python hará por tí). ¿Por qué es eso? Imagina que el primer elemento del array es 3. Eso significa que la primera palabra leída tenía 3 letras. Pero long_palabras.count(3) le está pidiendo a Python "dame cuántos elementos de esta lista valen 3". Para responder a esa pregunta Python debe recorrer toda la lista.

Si el siguiente elemento de la lista vuelve a ser 3, de nuevo estarías re-contando cuántas veces aparece el 3. Y esto lo haces para cada número en long_palabras. Si long_palabras tenía 1000 elementos, ya que en cada iteración del bucle llamas a .count(), que se ve obligado a recorrer otra vez los 1000 elementos, al final tienes dos bucles anidados que acceden 1000000 de veces a la lista.

Después tienes un if i > long para imprimir ese resultado, pero esa condición es siempre cierta ya que nunca cambias de valor a long, sino a lng (una errata)

Una alternativa más sencilla

En el segundo bucle en que vas computando las longitudes de cada palabra, ya podemos aprovechar para ir contando cuantas veces aparece cada longitud, ahorrándonos así el tercer e ineficiente bucle.

Por ejemplo podemos tener un diccionario cuyas claves serán las longitudes de las palabras y los valores el número de veces que aparece esa longitud. Inicialmente el diccionario estará vacío. Cada vez que encontramos una palabra de longitud n, si esa clave ya existía en el diccionario, incrementamos su valor. Si no existía la añadimos con un valor de 1. Así:

cuenta = {}
for palabra in li_palabras:
   long_palabra = len(palabra)
   if long_palabra in cuenta:
       cuenta[long_palabra] += 1
   else:
       cuenta[long_palabra] = 1

A la salida de este bucle el diccionario podría tener por ejemplo este valor:

{ 1: 3, 2: 1, 3: 2, 5: 1, 7: 1 }

que significa "de longitud 1 hay 3 palabras, de longitud 2 hay una, etc..." Ya sólo te queda recorrer este diccionario con cuenta.items() para mostrar el resultado. De momento te lo dejo a tí, si tienes dudas pregunta de nuevo en un comentario.

2
  • Muchísimas gracias por la valiosa ayuda. Tienes razón, mi código puede ser muy redundante a causa de mi nivel de principiante. Yo había usado li_palabras = sum(palabras,[]) para aplanar la lista de listas obtenida en li_palabras.append(input().split()) y poder manipularla mejor. De lo contrario, sort() no funciona sino sobre las sublistas y el resultado final no es el esperado. Commented el 28 ene. 2019 a las 13:04
  • 1
    Sí, edité mi respuesta para usar extend() en lugar de append(). De este modo no tienes que aplanar (ya queda plana). Por otro lado, no veo para qué era necesario el sort() y ya no es necesario con el enfoque del diccionario que lleva la cuenta. De entrada no te piden que la salida esté ordenada de ninguna forma, pero si te lo pidieran, la ordenación ocurriría al mostrar el diccionario, pero no al procesarlo. El número de elementos a ordenar en el diccionario es mucho menor que en tu lista long_palabras, que además repetías dentro de un bucle.
    – abulafia
    Commented el 28 ene. 2019 a las 13:06

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.