¿Evitar la repetición del código después del bucle?

Question

A menudo termino escribiendo un poco de código dos veces cuando uso un bucle. Por ejemplo, mientras que va a lo largo de la informática Udacity, escribí el código (para una función para encontrar el elemento que más se repite 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 previamente más repetido. Esto sucede tanto cuando el elemento actual es diferente al último como cuando llegué al final de la lista.

También me he encontrado con esto algunas veces al analizar una cadena carácter 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 creo/código. ¿Que debería hacer?

edición: Del mismo modo, en un ejemplo de cadena artificiosa división:

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 se trataba de que fue escrito para los estudiantes del curso que no se espera que tenga ningún conocimiento fuera de Python; solo lo que se enseñó en las unidades anteriores. Aunque tengo experiencia previa en Python, intento 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 nada sobre las importaciones, especialmente cosas como groupby. Dicho esto, ¿cómo debería escribirse sin ninguna de las características del lenguaje que probablemente no se enseñarían en un curso de introducción a la programación?

Answer 1

Dado que etiquetó language-agnostic, veo que no estará demasiado interesado en las cosas específicas de Python que podría utilizar para que su código sea eficiente, compacto y legible. Por la misma razón, no voy a mostrar cuán hermoso se puede escribir un código en Python.

En algunos de los casos se puede evitar if 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 compilados como C/C++/etc. el compilador realiza varios tipos de optimizaciones de bucle, incluyendo mover los bloques if de un bucle si hace lo mismo.

me corrieron y se comparó el tiempo de ejecución de varios fragmentos:

• @JFSebastian - 8,9939801693
• @srgerg - 3.13302302361
• la suya - 2,8182990551.

No es una generalización que un trailing if le de el mejor momento. Mi punto es: simplemente sigue tu algoritmo y trata de optimizarlo. No hay nada de malo con un if al final. Probablemente las soluciones alternativas son costosas.

Acerca del segundo ejemplo que ha introducido: El control tmp == '' se realiza para garantizar que solo se devuelvan cadenas no vacías. Eso en realidad es una especie de condición adicional sobre tu 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 presionar una condición if dentro del ciclo como if curCharIndex == lastIndex: push items to list que se ejecutará en cada iteración, y es una especie de caso similar.

Mi respuesta en pocas palabras:

• Su código es tan eficiente como el algoritmo que tiene en mente.
• Al final, se encuentran los if s, sin necesidad de preocuparse por ellos, pueden hacer que el código sea más eficiente que los enfoques alternativos sin un ejemplo (ejemplos aquí).
• Además, los compiladores también pueden detectar y modificar/mover los bloques alrededor de su código.
• Si hay una función de idioma/biblioteca que hace que su código sea rápido y al mismo tiempo legible, úselo. (Otras respuestas aquí señalan qué ofrece Python :))

Answer 2

No es raro que necesite volver a verificar una condición al final de un bucle que también se estaba verificando dentro del bucle. Si está dispuesto a sacrificar un poco de eficiencia, una forma de evitar la verificación repetida es verificarla en exceso dentro del ciclo. 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 de cheques para count > most_reps más a menudo de lo necesario, pero evita la necesidad de comprobar de nuevo después de que el bucle.

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

Answer 3

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

Aquí es el algoritmo que utiliza 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 de este tipo 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".

También, por supuesto, no tiene que haber caracteres en el algoritmo anterior, podría ser cualquier cosa que sea agrupable.

Editar: En respuesta a la edición de OP, pensé que no se te permitiría usar/saber sobre bibliotecas como itertools en una configuración de clase, pero no sugería que debieras depender de bibliotecas externas, pero más que deberías pensar en los problemas dividiéndolos en subproblemas más pequeños. Entonces, en este caso, implementaría su propio groupby y lo usaría.

Answer 4

técnica independiente del idioma para evitar la repetición de una condición después de un ciclo es agregar valores centinela a los datos de entrada, p., si delimiter se agrega al final de 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 la secuencia.

Otra opción es delegar algo de trabajo para una función separada, por ejemplo, una función cuenta el número de repeticiones, el otro se encuentra 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; tal vez no valga la pena el esfuerzo.

Answer 5

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

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 (algunos de) el procesamiento de "fin de la subsecuencia" después de cada carácter, para que la contabilidad sea correcta si la secuencia finaliza inmediatamente después de ese personaje. En su ejemplo, puede eliminar la condición "else" en su y ejecutar el código dentro de ella cada vez. (Esta es la respuesta de sergerg.)

Esto puede no ser fácil para algunos tipos de controles. Para contar palabras, debe agregar algo de lógica extra para evitar la acumulación de cruxt de las subsecuencias "parciales" que procesa. Aquí está el código que hace que:

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 la de añadir un valor centinela hasta el final de la secuencia, lo que disparará el "fin de la subsecuencia" comportamiento deseado. 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 larga, puede agregar cualquier valor que no sea igual al último elemento de la secuencia. None podría ser una buena opción. Para mi ejemplo palabras de contar, un carácter no-palabra (como una nueva línea) hará:

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 la iteración en una secuencia que podría terminar de forma inesperada. Puede usar generadores para preprocesar la secuencia, como en las otras respuestas que usan groupby desde itertools. (Por supuesto, las funciones del generador, si tiene que escribirlos usted mismo, pueden tener problemas similares.)

Para mi ejemplo palabra contando, puedo usar expresiones regulares desde el 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())) 

de salida, cuando se le da un texto convenientemente Pythonic (que es el mismo para todas las versiones de cuatro 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}) 

Answer 6

iteradores proporcionar una buena manera de romper 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.