Unikanie powtórzenia kodu po pętli?

Question

Często kończę pisanie trochę kodu dwa razy podczas korzystania z pętli. Na przykład, podczas przechodzenia na witrynie Udacity informatyki oczywiście, napisałem kod (dla funkcji, aby znaleźć najbardziej sekwencyjnie powtarzany element):

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 

W tym przypadku, mam sprawdzanie dwukrotnie jeśli liczba jest większa niż poprzednio najbardziej powtarzany element. Dzieje się tak zarówno wtedy, gdy bieżący element różni się od ostatniego, jak i po osiągnięciu końca listy.

Zdarzyło mi się to również kilka razy podczas analizowania łańcucha znaków według znaków. Było też kilka razy, gdy było to około 5 linii kodu. Czy jest to powszechne, czy też wynikiem sposobu w jaki myślę/kod. Co powinienem zrobić?

edit: Podobnie w contrived przykład rozłupywania ciąg:

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: Egzamin ten pochodził został napisany dla studentów, którzy oczywiście nie oczekuje się żadnego zewnętrznego znajomość Pythona; tylko to, czego nauczono w poprzednich jednostkach. Chociaż mam wcześniejsze doświadczenia w Pythonie, staram się przestrzegać tych ograniczeń, aby jak najlepiej wykorzystać kurs. Takie rzeczy jak str.split, listy i wiele podstaw Pythona były nauczane, ale jeszcze nic na import - w szczególności nie takie rzeczy jak groupby. Biorąc to pod uwagę, jak to powinno być napisane bez żadnych cech językowych, które prawdopodobnie nie byłyby nauczane w kursie wprowadzającym do programowania.

Answer 1

Ponieważ oznaczono language-agnostic, widzę, że nie będziesz się zbytnio interesować rzeczami specyficznymi dla Pythona, których możesz użyć, aby twój kod był wydajny, zwarty i czytelny. Z tego samego powodu nie zamierzam pokazywać, jak pięknie można napisać kod w pytonie.

W niektórych przypadkach można uniknąć dodatkowego if w zależności od używanego algorytmu, ale w większości przypadków wygląda to tak: "Jeśli istnieje, powinien być znaczący i/lub wydajny." Nie wiem, jak działa interpreter python, ale w językach kompilowanych, takich jak C/C++/etc. kompilator wykonuje różne rodzaje optymalizacji pętli, w tym przesuwanie bloków if z pętli, jeśli robi to samo.

Pobiegłem i porównano czas pracy poszczególnych fragmentów:

• @JFSebastian - 8,9939801693
• @srgerg - 3.13302302361
• ciebie - +2,8182990551.

To nie jest uogólnienie, że końcowy if zapewnia najlepszy czas. Chodzi mi o to: po prostu zastosuj swój algorytm i spróbuj go zoptymalizować. Nie ma nic złego na końcu pod if. Prawdopodobnie alternatywne rozwiązania są drogie.

O drugim przykładzie, który wprowadziłeś: Sprawdzenie tmp == '' zostało wykonane w celu zapewnienia, że ​​zwracane są tylko niepuste ciągi. To w rzeczywistości jest dodatkowym warunkiem nad twoim algorytmem podziału. W każdym razie potrzebujesz dodatkowej rtn.append po pętli, ponieważ wciąż jest coś poza ostatnim ogranicznikiem. Zawsze możesz wcisnąć warunek if w pętli, taki jak if curCharIndex == lastIndex: push items to list, który będzie wykonywany w każdej iteracji i jej rodzaju w tym samym przypadku ponownie.

Moja odpowiedź w skrócie:

• Kod jest równie skuteczny jako algorytm, który masz na myśli.
• Na końcu w wielu przypadkach napotykamy na koniec - nie trzeba się o to martwić, mogą sprawić, że kod będzie bardziej wydajny niż alternatywne podejścia bez takiego przypadku (przykłady są tutaj).
• Dodatkowo kompilatory mogą również wykrywać i modyfikować/przesuwać bloki wokół kodu.
• Jeśli istnieje funkcja językowa/biblioteka, która sprawia, że ​​kod jest szybki i jednocześnie czytelny, użyj go. (Inne odpowiedzi tutaj wskazują, co oferuje Python :))

Answer 2

Często zdarza się, że trzeba ponownie sprawdzić stan na końcu pętli, która również była sprawdzana w pętli. Jeśli jesteś gotów poświęcić trochę wydajności, jednym ze sposobów na uniknięcie wielokrotnego sprawdzania jest sprawdzenie go w pętli. Na przykład:

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 

Ten kod sprawdza count > most_reps częściej niż to konieczne, ale eliminuje konieczność, aby sprawdzić go ponownie po pętli.

Niestety tego rodzaju zmiana nie będzie miała zastosowania we wszystkich okolicznościach.

Answer 3

Zapoznaj się z realizacją itertools.groupby, która ma prawie dokładnie to, co chcesz. http://docs.python.org/library/itertools.html#itertools.groupby

Oto algorytm stosując wspomniany kod:

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 

Moja rekomendacja dla myślenia o pisaniu algorytmów jak to w przyszłości jest nie próbować zrobić wszystko w jednej funkcji. Pomyśl o mniejszych funkcjach, które rozwiązują problem, który próbujesz rozwiązać, takich jak "grupowanie każdej sekwencji równych elementów w sekwencji w mniejsze sekwencje".

Oczywiście nie muszą to być znaki w powyższym algorytmie - może to być wszystko, co można zgrupować.

Edycja: W odpowiedzi na edycję OP, doszedłem do wniosku, że nie będziesz mógł używać/wiedzieć o bibliotekach takich jak itertools w ustawieniach klasy, ale nie sugerowałem, że powinieneś polegać na zewnętrznych bibliotekach, ale więcej powinieneś pomyśleć o problemach, dzieląc je na mniejsze podproblemy. Tak więc w tym przypadku możesz zaimplementować swój własny groupby i używać go.

Answer 4

Technika nieobsługiwana językowo w celu uniknięcia powtórzenia warunku po pętli polega na dodaniu wartości zmiennych do danych wejściowych, np., jeśli delimiter dołączony do końca string, warunek ten nie jest konieczny w split_by(). Przykład kanoniczny: w algorytmie wyszukiwania liniowego można dołączyć igłę do stogu siana, aby uniknąć końca sprawdzania sekwencji.

Inną możliwością jest, aby przekazać pewne prace z osobną funkcją na przykład, jedną z funkcji liczy liczbę powtórzeń, a drugi znajduje się w równej longest_repetition():

from itertools import groupby 

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

Jeżeli kod jest powtarzany trywialne; może nie jest to warte wysiłku.

Answer 5

Myślę, że istnieją trzy ogólne podejścia, które mogą pomóc uniknąć powtarzania kodu na końcu pętli. Dla wszystkich trzech zamierzam użyć przykładowego problemu nieco innego od twojego własnego, licząc słowa w ciągu.Oto „default” wersja, że ​​podobnie jak w kodzie, powtarza pewną logikę w końcu pętli:

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 

Pierwsze podejście to zrobić (niektórych) „koniec podciągu” przetwarzanie po każdym znaku, aby księgowość była poprawna, jeśli sekwencja kończy się bezpośrednio po tej postaci. W twoim przykładzie możesz wyeliminować warunek "else" na swoim i uruchomić kod w nim za każdym razem. (Jest to sergerg na odpowiedź.)

To może nie być łatwe dla niektórych rodzajów kontroli, choć. Aby policzyć słowa, musisz dodać trochę dodatkowej logiki, aby uniknąć gromadzenia się z "częściowych" podciągów, które przetwarzasz. Oto kod, który to robi:

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 

Drugim rozwiązaniem byłoby dołączyć wartości wskaźnikowych do końca sekwencji, która wywoła pożądaną „koniec podciąg” zachowania. Może to być trudne, jeśli chcesz uniknąć skażenia danych przez wartownika (szczególnie w przypadku numerów takich jak cyfry). W przypadku najdłuższego kolejnego problemu z podsekcją można dodać dowolną wartość, która nie jest równa ostatniej pozycji w sekwencji. None może być dobrym wyborem. Na moim przykładzie liczenia słowy, charakter non-word (takie jak znak nowej linii) zrobi:

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 

Trzecie podejście polega na zmianie struktury kodu w celu uniknięcia Iterowanie nad sekwencję, która może niespodziewanie zakończyć. Możesz użyć generatorów do wstępnego przetworzenia sekwencji, tak jak w innych odpowiedziach, które używają groupby od itertools. (Oczywiście, funkcje generatory, jeśli musisz to zrobić sam, może mieć podobne problemy.)

Na moje słowo licząc przykład, można użyć wyrażeń regularnych z modułu re znaleźć słowa:

from re import finditer 

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

wyjścia, gdy otrzymują odpowiednio pythonic tekst (to jest taki sam dla wszystkich czterech wersjach 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

Iteratory dostarczających miły sposób, aby rozbić pętle:

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 

Wiele języków ma podobną koncepcję.