¿Evitar la repetición de código tras bucle?

A menudo termino escribiendo un poco de código dos veces cuando uso un bucle. Por ejemplo, mientras revisaba el curso de informática de Udacity, escribí el código (para que una función encuentre el elemento repetido más secuencialmente):

def longest_repetition(l): if not l: return None most_reps = count = 0 longest = prv = None for i in l: if i == prv: count += 1 else: if count > most_reps: longest = prv most_reps = count count = 1 prv = i if count > most_reps: longest = prv return longest 

En este caso, estoy comprobando dos veces si el recuento es mayor que el elemento más repetido anteriormente. Esto sucede cuando el elemento actual es diferente del último y cuando llego al final de la lista.

También me he encontrado con esto unas cuantas veces al analizar una cadena de caracteres por carácter. También ha habido algunas veces en las que ha habido hasta 5 líneas de código. Es esto común, o un resultado de la forma en que pienso / código. ¿Qué tengo que hacer?

editar: De manera similar, en un ejemplo de división de cadena artificial:

 def split_by(string, delimeter): rtn = [] tmp = '' for i in string: if i == delimeter: if tmp != '': rtn.append(tmp) tmp = '' else: tmp += i if tmp != '': rtn.append(tmp) return rtn 

edición: el examen del que se realizó fue escrito para estudiantes del curso que no se espera que tengan ningún conocimiento externo de Python; Solo lo enseñado en las unidades anteriores. Aunque tengo experiencia previa en Python, estoy tratando de cumplir con estas restricciones para aprovechar al máximo el curso. Se enseñaron cosas como str.split, listas y muchos de los fundamentos de Python, pero todavía no hay nada importante, especialmente no cosas como groupby. Dicho esto, ¿cómo debería escribirse sin ninguna de las características del lenguaje que probablemente no se enseñarán en un curso de introducción a la progtwigción?

Desde que etiquetó el language-agnostic , veo que no estará muy interesado en las cosas específicas de python que podría usar para hacer que su código sea eficiente, compacto y legible. Por la misma razón, no voy a mostrar cuán hermoso puede escribirse un código en python.

En algunos de los casos, ese extra if se puede evitar al final dependiendo de su algoritmo, pero la mayoría de los casos es como “Si existe, debería ser significativo y / o eficiente”. No sé cómo funciona el intérprete de python, pero en lenguajes comstackdos como C / C ++ / etc. el comstackdor realiza varios tipos de optimizaciones de bucle, incluido el movimiento de los bloques if de un bucle si hace lo mismo.

Corrí y comparé el tiempo de ejecución de varios fragmentos:

  • @JFSebastian – 8.9939801693
  • @srgerg – 3.13302302361
  • el tuyo – 2.8182990551.

No es una generalización que un final if te da el mejor momento. Mi punto es: simplemente sigue tu algoritmo e intenta optimizarlo. No hay nada de malo en un if al final. Probablemente las soluciones alternativas sean caras.

Sobre el segundo ejemplo que ha puesto: La comprobación tmp == '' se realiza para garantizar que solo se devuelvan cadenas no vacías. Eso en realidad es una especie de condición adicional sobre su algoritmo de división. En cualquier caso, necesita un rtn.append adicional después del bucle porque todavía hay algo más allá del último delimitador. Siempre se puede insertar una condición if dentro del bucle como if curCharIndex == lastIndex: push items to list que se ejecutarán en cada iteración, y volverá a ser el mismo caso.

Mi respuesta en breve:

  • Su código es tan eficiente como su algoritmo que tiene en mente.
  • Los ” if al final se encuentran en muchos casos; no hay necesidad de preocuparse por ellos, pueden hacer que el código sea más eficiente que los enfoques alternativos sin tales if (los ejemplos están aquí).
  • Además, los comstackdores también pueden detectar y modificar / mover los bloques alrededor de su código.
  • Si hay una función / biblioteca de idioma que hace que su código sea rápido y al mismo tiempo legible, utilícelo. (Otras respuestas aquí señalan lo que Python ofrece :))

Echa un vistazo a la implementación de itertools.groupby que hace casi exactamente lo que quieres. http://docs.python.org/library/itertools.html#itertools.groupby

Aquí está el algoritmo usando dicho código:

 from itertools import groupby string = "AAABBCCDDDD" maximum = 0 max_char = "" for i in groupby(string): x, xs = i n = len(list(xs)) if n > maximum: max_char = x maximum = n print max_char 

Mi recomendación para pensar en escribir algoritmos como este en el futuro es tratar de no hacer todo en una sola función. Piense en las funciones más pequeñas que resuelven el problema que está tratando de resolver, como “agrupar cada secuencia de elementos iguales en una secuencia en secuencias más pequeñas”.

Además, por supuesto, no tiene que ser caracteres en el algoritmo anterior, podría ser cualquier cosa que sea agrupable.

Edición: en respuesta a la edición del OP, pensé que no se le permitiría usar / conocer bibliotecas como itertools en una configuración de clase, pero no estaba sugiriendo que dependiera de bibliotecas externas, sino más de lo que debería pensar. sobre problemas dividiéndolos en subproblemas más pequeños. Entonces, en este caso, implementarías tu propio groupby y lo groupby .

Una técnica independiente del lenguaje para evitar repetir una condición después de un bucle es agregar valores de centinela a los datos de entrada, por ejemplo, si el delimiter agrega al final de la string entonces la condición no es necesaria en split_by() . Ejemplo canónico: en el algoritmo de búsqueda lineal se puede agregar una aguja a un pajar para evitar el final de la verificación de secuencia.

Otra opción es delegar algunos trabajos a una función separada, por ejemplo, una función cuenta el número de repeticiones, la otra encuentra el máximo como en longest_repetition() :

 from itertools import groupby def longest_repetition(iterable): return max(groupby(iterable), key=lambda x: sum(1 for _ in x[1]))[0] 

Si el código repetido es trivial; Puede que no valga la pena el esfuerzo.

No es infrecuente tener que volver a verificar una condición al final de un bucle que también se estaba revisando dentro del bucle. Si está dispuesto a sacrificar un poco de eficiencia, una forma de evitar la comprobación repetida es verificarla en exceso dentro del bucle. Por ejemplo:

 def my_longest_repetition(l): if not l: return None most_reps = count = 0 longest = prv = None for i in l: count = (count + 1) if i == prv else 1 if count > most_reps: longest = prv most_reps = count prv = i return longest 

Este código verifica el count > most_reps más a menudo de lo necesario, pero evita la necesidad de verificarlo nuevamente después del ciclo.

Desafortunadamente, este tipo de cambio no será aplicable en todas las circunstancias.

Creo que hay tres enfoques generales que podrían ayudarlo a evitar la repetición del código al final del ciclo. Para los tres usaré un problema de ejemplo ligeramente diferente al tuyo, contando palabras en una cadena. Aquí hay una versión “predeterminada” que, como su código, repite algo de lógica al final del ciclo:

 from collections import Counter def countWords0(text): counts = Counter() word = "" for c in text.lower(): if c not in "abcdefghijklmnopqrstuvwxyz'-": if word: counts[word] += 1 word = "" else: word += c if word: counts[word] += 1 # repeated code at end of loop return counts 

El primer enfoque es hacer (parte de) el procesamiento del “fin de subsecuencia” después de cada carácter, de modo que la contabilidad sea correcta si la secuencia termina inmediatamente después de ese carácter. En su ejemplo, podría eliminar la condición “else” en su y ejecutar el código dentro de él cada vez. (Esta es la respuesta de sergerg.)

Sin embargo, esto puede no ser fácil para algunos tipos de controles. Para contar palabras, debe agregar un poco de lógica adicional para evitar que se acumulen cruces de las subsecuencias “parciales” que procesa. Aquí está el código que hace eso:

 def countWords1(text): counts = Counter() word = "" for c in text.lower(): if c not in "abcdefghijklmnopqrstuvwxyz'-": word = "" else: if word: counts[word] -= 1 # new extra logic word += c counts[word] += 1 # this line was moved from above return counts + Counter() # more new stuff, to remove crufty zero-count items 

La segunda opción sería agregar un valor de centinela al final de la secuencia que activará el comportamiento deseado de “fin de subsecuencia”. Esto puede ser complicado si necesita evitar que el centinela contamine sus datos (especialmente para cosas como números). Para su problema de subsecuencia consecutiva más largo, puede agregar cualquier valor que no sea igual al último elemento de la secuencia. None puede ser una buena opción. Para mi ejemplo de palabras de conteo, un carácter sin palabras (como una nueva línea) servirá:

 def countWords2(text): counts = Counter() word = "" for c in text.lower() + "\n": # NOTE: added a sentinel to the string! if c not in "abcdefghijklmnopqrstuvwxyz'-": if word: counts[word] += 1 word = "" else: word += c # no need to recheck at the end, since we know we ended with a space return counts 

El tercer enfoque es cambiar la estructura del código para evitar iterar sobre una secuencia que podría terminar inesperadamente. Puede usar generadores para preprocesar la secuencia, como en las otras respuestas que usan groupby de itertools . (Por supuesto, las funciones del generador, si tiene que escribirlas usted mismo, pueden tener problemas similares).

Para mi ejemplo de conteo de palabras, puedo usar expresiones regulares del módulo re para encontrar las palabras:

 from re import finditer def countWords3(text): return Counter(match.group() for match in finditer("[\w'-]+", text.lower())) 

Salida, cuando se le da un texto Pythonic adecuado (es el mismo para las cuatro versiones de countWords):

 >>> text = """Well, there's egg and bacon; egg sausage and bacon; egg and spam; egg bacon and spam; egg bacon sausage and spam; spam bacon sausage and spam; spam egg spam spam bacon and spam; spam sausage spam spam bacon spam tomato and spam; spam spam spam egg and spam; spam spam spam spam spam spam baked beans spam spam spam; or Lobster Thermidor a Crevette with a mornay sauce served in a Provencale manner with shallots and aubergines garnished with truffle pate, brandy and with a fried egg on top and spam.""" >>> countWords0(text) Counter({'spam': 28, 'and': 12, 'egg': 8, 'bacon': 7, 'sausage': 4, 'a': 4, 'with': 4, 'well': 1, 'lobster': 1, 'manner': 1, 'in': 1, 'top': 1, 'thermidor': 1, "there's": 1, 'truffle': 1, 'provencale': 1, 'sauce': 1, 'brandy': 1, 'pate': 1, 'shallots': 1, 'garnished': 1, 'tomato': 1, 'on': 1, 'baked': 1, 'aubergines': 1, 'mornay': 1, 'beans': 1, 'served': 1, 'fried': 1, 'crevette': 1, 'or': 1}) 

Los iteradores proporcionan una buena manera de romper los bucles:

 def longest_repetition(l): i=iter(l) n=next(i,None) longest=None most_reps=0 while n is not None: p=n count=0 while p==n: n=next(i,None) count+=1 if count>most_reps: most_reps=count longest=p return longest 

Muchos idiomas tienen un concepto similar.