Evitando la ripetizione del codice dopo il ciclo?

Question

Finisco spesso a scrivere un po 'di codice due volte quando si usano i loop. Per esempio, mentre andando oltre il corso di informatica Udacity, ho scritto il codice (per una funzione per trovare l'elemento più in sequenza ripetuta):

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 

In questo caso, sto controllando due volte se il conteggio è maggiore rispetto all'elemento precedentemente più ripetuto. Questo accade sia quando l'elemento corrente è diverso dall'ultimo e quando ho raggiunto la fine dell'elenco.

Ho anche incontrato alcune volte quando analizzo una stringa carattere per carattere. Ci sono state anche alcune volte in cui è stato applicato a circa 5 linee di codice. È comune o è il risultato del modo in cui penso/codice. Cosa dovrei fare?

edit: Allo stesso modo, in una artificiosa esempio stringa di scissione:

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 

edit: L'esame di questo è stato da stato scritto per gli studenti del corso che non sono tenuti ad avere alcuna conoscenza al di fuori di Python; solo ciò che è stato insegnato nelle unità precedenti. Sebbene io abbia una precedente esperienza in Python, sto cercando di rispettare queste restrizioni per ottenere il massimo dal corso. Cose come str.split, elenchi e molti dei fondamenti di Python sono stati insegnati, ma nulla ancora sulle importazioni - specialmente non cose come groupby. Detto questo, come dovrebbe essere scritto senza nessuna delle caratteristiche linguistiche che probabilmente non verrebbero insegnate in un corso introduttivo di programmazione.

Answer 1

Dato che hai taggato language-agnostic, vedo che non sarai molto interessato alle cose specifiche di Python che potresti usare per rendere il tuo codice efficiente, compatto e leggibile. Per la stessa ragione, non ho intenzione di mostrare quanto sia bello scrivere un codice in python.

In alcuni casi è possibile evitare l'ulteriore if a seconda dell'algoritmo, ma nella maggior parte dei casi è come "Se esiste, dovrebbe essere significativo e/o efficiente". Non so come funziona l'interprete python, ma in linguaggi compilati come C/C++/etc. il compilatore esegue vari tipi di ottimizzazioni del ciclo, incluso lo spostamento dei blocchi if di un loop se fa la stessa cosa.

ho corse e confrontato il tempo di esecuzione dei vari frammenti:

• @JFSebastian - 8,9939801693
• @srgerg - 3.13302302361
• vostro - 2,8182,990551 millions.

Non è una generalizzazione che un trailing if offre il momento migliore. Il mio punto è: basta seguire il tuo algoritmo e cercare di ottimizzarlo. Non c'è niente di sbagliato con un if alla fine. Probabilmente le soluzioni alternative sono costose.

Circa il secondo esempio che avete messo in: Il controllo tmp == '' viene fatto per garantire solo le stringhe non vuote vengono restituiti. In realtà è una sorta di condizione aggiuntiva rispetto all'algoritmo di divisione. In ogni caso, è necessario un ulteriore rtn.append dopo il ciclo perché c'è ancora qualcosa oltre l'ultimo delimitatore. È sempre possibile inserire una condizione if all'interno del ciclo come if curCharIndex == lastIndex: push items to list che verrà eseguita in ogni iterazione e il suo tipo dello stesso caso.

La mia risposta in breve:

• Il codice è efficiente come l'algoritmo che avete in mente.
• I if s, alla fine, si incontrano in molti casi - non c'è bisogno di preoccuparsi di loro, essi possono essere rendere il codice più efficiente rispetto agli approcci alternativi senza tale un if (esempi sono proprio qui).
• Inoltre i compilatori possono anche individuare e modificare/spostare i blocchi attorno al codice.
• Se esiste una funzione/libreria linguistica che rende il codice veloce e allo stesso tempo leggibile, utilizzarlo. (Altre risposte qui indicano cosa offre python :))

Answer 2

Non è raro dover ricontrollare una condizione alla fine di un ciclo che è stato controllato anche all'interno del ciclo. Se sei pronto a sacrificare un po 'di efficienza, un modo per evitare il controllo ripetuto è di controllarlo per eccesso all'interno del ciclo. Per esempio:

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 

Questo codice verifica la presenza di count > most_reps più spesso di quanto dovrebbe, ma evita la necessità di controllare di nuovo dopo il ciclo.

Sfortunatamente questo tipo di modifica non sarà applicabile in tutte le circostanze.

Answer 3

Dai un'occhiata all'implementazione di itertools.groupby che fa quasi esattamente quello che desideri. http://docs.python.org/library/itertools.html#itertools.groupby

Ecco l'algoritmo utilizzando detto codice:

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 

La mia raccomandazione per pensando di scrivere algoritmi come questo in futuro è quello di cercare di non fare tutto in una funzione. Pensa alle funzioni più piccole che risolvono il problema che stai cercando di risolvere, come "raggruppare ogni sequenza di elementi uguali in una sequenza in sequenze più piccole".

Ovviamente non è necessario che siano presenti caratteri nell'algoritmo sopra riportato - potrebbe essere qualsiasi cosa che sia raggruppabile.

Modifica: in risposta alla modifica dell'OP, ho pensato che non avresti potuto usare/sapere su librerie come itertools in un'impostazione di classe, ma non stavo suggerendo che dovresti fare affidamento su librerie esterne, ma più che dovresti pensare ai problemi suddividendoli in sottoproblemi più piccoli. Quindi in questo caso dovresti implementare il tuo groupby e usarlo.

Answer 4

La tecnica agnostica della lingua per evitare di ripetere una condizione dopo un ciclo consiste nell'applicare i valori sentinella ai dati di input, ad es., se delimiter viene aggiunto alla fine di string, la condizione non è necessaria in split_by(). Esempio canonico: nell'algoritmo di ricerca lineare un ago può essere aggiunto ad un pagliaio per evitare la fine del controllo di sequenza.

Un'altra opzione è quella di delegare certo lavoro per una funzione separata per esempio, una funzione conta il numero di ripetizioni, dall'altro ritiene massimo come in longest_repetition():

from itertools import groupby 

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

Se il codice ripetuta è banale; potrebbe non valere la pena.

Answer 5

Penso che ci siano tre approcci generali che potrebbero aiutarti a evitare di ripetere codice alla fine del ciclo. Per tutti e tre ho intenzione di utilizzare un problema di esempio leggermente diverso dal tuo, contando le parole in una stringa.Ecco una versione "default" che, come il codice, si ripete un po 'la logica alla fine 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 

Il primo approccio è quello di fare (alcuni dei) al trattamento di "fine subsequence" dopo ogni carattere, in modo che la contabilità sia corretta se la sequenza termina immediatamente dopo quel personaggio. Nel tuo esempio, potresti eliminare la condizione "else" sul tuo ed eseguire il codice al suo interno ogni volta. (Questa è la risposta di sergerg.)

Tuttavia, questo potrebbe non essere semplice per alcuni tipi di controlli. Per contare le parole, è necessario aggiungere qualche logica aggiuntiva per evitare di accumulare cruft dalle sottosequenze "parziali" elaborate. Ecco il codice che lo fa:

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 seconda opzione sarebbe quella di aggiungere un valore sentinella, alla fine della sequenza che attiverà la "fine del subsequence" desiderato comportamento. Questo può essere complicato se devi evitare che la sentinella contamini i tuoi dati (specialmente per cose come numeri). Per il tuo problema di sottosequenza consecutiva più lungo, puoi aggiungere qualsiasi valore che non sia uguale all'ultima voce nella sequenza. None potrebbe essere una buona scelta. Per il mio parole conteggio esempio, un carattere non-parola (come una nuova riga) farà:

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 

Il terzo approccio è quello di modificare la struttura del codice per evitare l'iterazione su una sequenza che può terminare inaspettatamente. È possibile utilizzare i generatori per pre-elaborare la sequenza, come nelle altre risposte che utilizzano groupby da itertools. (Naturalmente, le funzioni del generatore, se si deve scrivere da soli, possono avere problemi simili.)

Per il mio esempio, il conteggio parola, posso usare le espressioni regolari dal modulo re di trovare le parole:

from re import finditer 

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

uscita, quando somministrato un testo opportunamente Pythonic (è lo stesso per tutte e quattro le versioni di 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

iteratori forniscono un bel modo per rompere loop:

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 

Molte lingue hanno un concetto simile.