Note de curs, clasele 11-12, 21 noiembrie 2013

From Algopedia
Revision as of 14:39, 14 December 2020 by Cata (talk | contribs) (înlocuiesc <source> cu <syntaxhighlight>)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Zilele acestea m-am uitat pe multe surse de la concursurile din această toamnă. Apoi am plâns. Din lacrimile mele s-a născut lecția de azi!

Chestiuni de programare

Preliminarii

Orice lucru rău trebuie spus încadrat de două lucruri bune. Voi sunteți printre cei mai buni elevi din generația voastră și sunt onorat să lucrez cu voi. Deci luați observațiile de mai jos nu ca pe o insultă personală, ci ca pe o ocazie să vă îmbunătățiți. Gata, am început cu un lucru bun. :-)

Noi, profesorii, avem partea noastră de vină în felul dezlânat în care programați voi. Ne batem singuri pe spate că elevii știu algoritmi, dar nu ne pasă cum îi codează. Adevărul este că cele două merg mână în mână, mai ales apropo de ceea ce am mai spus: voi nu vedeți destul cod scris de alții. Deci o lecție pe an dedicată programării este doar un început.

Programarea aproximativă

Banc: cică japonezii aud de Dacia -- mașină bună, fiabilă, piese ieftine. Cumpără planurile de la Dacia și încep și ei să o producă. Doar că, surpriză, de pe linia de asamblare le iese un tractor! Trimit un om la Pitești, să studieze uzina. Se uită el, se întoarce acasă, mai repară japonezii mici probleme la linia lor. Degeaba: de pe linia de asamblare ieșeau tractoare. Disperați, dau telefon în România și cer lămuriri. Românii îi liniștesc: „păi și nouă ne iese tot tractor, dar îl luăm la pilă!”

Toate subproblemele pe care le tratăm aici sunt doar vârfuri ale icebergului. Ele reflectă o problemă mai gravă: programarea aproximativă. Prin programare aproximativă înțelegem o serie de iterații de adăugare de cod care converge către o soluție. Programul capătă formă pe măsură ce îl scriem, ca și ideea de rezolvare:

  • Mai am nevoie de un element în vector? Adaug 1 la lungimea lui.
  • M-ar ajuta să am datele sortate? Ce idee bună, apelez un sort().
  • Trebuie să ies prematur dintr-o buclă? Deja am scris-o folosind for, deci inserez un break.

Nu ciocăniți ici și colo, nu programați reactiv, în funcție de erorile din iterația anterioară. Programați activ, gândindu-vă bine la algoritm și la detaliile lui și încercați să-l implementați bine din prima.

Veți vrea să mergeți la companii faimoase. Acolo oamenii se uită, încă de la interviu, la stilul vostru de codare. Iar, dacă veți fi acceptați, vă veți poticni la fiecare code review de aceleași observații. Dacă așteptați zece ani până să încercați să vă corectați, s-ar putea să fie prea târziu. Lenevirea creierului duce la o gândire încâlcită.

Constante

Folosim în general constante pentru a face codul mai solid și mai ușor de modificat.

Constantele sunt sublime, dar lipsesc cu desăvârșire

Cel mai grav este să nu folosiți deloc constante. Orice repetiție, chiar și a unui singur număr, chiar și doar o dată, este o practică riscantă. Un programator bun își ordonează codul astfel încât o modificare undeva în program să nu necesite modificări în alte părți fără legătură. Acest principiu se numește Don't repeat yourself (DRY).

Așa nu Așa da
int v[100000], w[100000];

...

int max = -2000000000;

...
#define MAX_N 100000
#define INFINITY 2000000000

int v[MAX_N], w[MAX_N];

...

int max = -INFINITY;

...

Scenariu catastrofic: declarați 5 vectori de mărime 1.000. Testați programul, care trece toate testele mici. Înlocuiți 1.000 cu 100.000, dar omiteți una dintre aparițiile constantei. Trimiteți problema, care ia 0 puncte.

#define N "vreo 100000 și 17, să fie"

Aproape fără excepție am observat constante declarate cu „câteva” unități mai mari decât este necesar. Dacă problema specifică N ≤ 100.000, voi declarați 100.002, 100.005, 100.007. Unii mai creativi ajung la 111.111 (ce-i drept, estetica acestui număr este incontestabilă).

De ce faceți asta? Următoarele răspunsuri nu sunt acceptate:

  • Îmi este teamă că programul are o viață proprie și că decide, de capul lui, să se reverse cu câteva elemente;
  • Mă gândesc că biții nu sunt bine separați și că se pot păta unii de la alții;
  • Cred că pointerul care iterează prin vector frânează greu și nu se va opri la timp;
  • Am de gând să folosesc vectorul de la 1, deci un element deja s-a pierdut.

Următorul răspuns este acceptat:

  • Nu am încredere în aptitudinile mele de programator și în robustețea codului pe care îl produc; vectorul este accesat și modificat în câteva locuri diferite și eu nu pot să demonstrez că mă încadrez în N elemente.

Nu programați în dorul lelii. Fiți stăpâni pe program. Nimeni nu jelește 10 octeți irosiți, dar este vorba de un principiu.

În plus, la matricele multidimensionale risipa se cumulează. 1.010 octeți în loc de 1.000? 1% risipă. 1.0103 octeți în loc de 1.0003? 3% risipă.

Dacă vă plac algoritmii, veți ajunge să învățați unii tot mai complicați. Dacă nu sunteți pe deplin stăpâni nici pe aceste cărămizi de la bază, vă va fi greu să construiți peste ele.

Patul lui Procust pentru constante

Adesea aveți nevoie de vectori de lungimi ușor diferite. Poate un vector se termină cu o santinelă, sau poate altul are santinele la ambele capete. Poate altul are N ≤ 100.000 elemente și va mai câștiga alte K ≤ 1.000 elemente în viitor. De cele mai multe ori, voi definiți constanta în program pentru a acoperi toate aceste cazuri.

Nu este bine, tot din principiu. Declarați o constantă egală cu cea specificată de datele problemei, apoi ajustați fiecare vector în funcție de necesități.

Așa nu Așa da
#define MAX_N 101000
int v[MAX_N], w[MAX_N], x[MAX_N], y[MAX_N];
#define MAX_N 100000
#define MAX_K 1000

int v[MAX_N];
int w[MAX_N + 1];     // bordat cu santinelă la sfârșit
int x[MAX_N + 2];     // bordat cu santinelă la ambele capete
int y[MAX_N + MAX_K]; // Va căpăta un element la fiecare iterație

Codul vostru va câștiga mult în eleganță și în claritate, căci scopul fiecărei variabile va deveni mai clar. Reiese și că 1 și 2 sunt constante (numărul de santinele nu depinde de mărimea intrării), dar K poate și el să varieze dacă datele problemei se schimbă.

Break, continue și return prematur

Evităm, cu rare excepții, break, continue și return prematur pentru că fac codul mai greu de citit. Se aplică și la concurs, chiar dacă voi sunteți singurii cititori.

„Să oprească proștii la stop”

La semnele de stop (octogonul roșu), legea spune că trebuie să oprești complet mașina (să stea roata). În practică, mai devreme sau mai târziu toți șoferii ne dăm seama că putem să trecem pe lângă semn fără să oprim complet. Nu cunosc pe nimeni care să respecte la sânge această lege. „Rostogolirea” prin semnul de stop reduce uzura frânelor, deci are un avantaj palpabil. Dar suntem conștienți că facem o prostioară și că nu putem face asta oricând, oriunde -- în special când de pe strada cu prioritate vin mașini. Cine încalcă această lege fără discernământ se expune la accidente, potențial catastrofice.

La fel este și cu programarea nestructurată. Scopul nu este să urmăm orbește niște legi, ci să facem codul mai ușor de înțeles și de întreținut. Prin această prismă, situațiile legitime de folosire a programării nestructurate sunt rarisime.

Dar programez mai ușor așa

Viața nu e ușoară. Cu toții ne străduim azi ca să ne fie bine mai încolo, pe termen lung.

Dar scriu cod mai clar așa

Claritatea este în ochii cititorului. Dacă vă obișnuiți să programați aproximativ, orice program neaproximativ vi se va părea straniu.

Iată un exemplu tipic: căutarea lui x în vectorul v.

Așa nu Așa da
for (int i = 0; i < n; i++) {
  if (v[i] == x) {
    break;
  }
}
int i = 0;
while ((i < n) && (v[i] != x)) {
  i++;
}

Codul este mai scurt și mai citibil. Versiunea cu break promite o condiție de ieșire (i >= n), apoi ne păcălește ieșind pe o cu totul altă condiție (v[i] == x). În versiunea structurată, ambele condiții sunt listate clar în instrucțiunea while.

Un alt exemplu: un test dacă șirul s este palindrom.

Așa nu Așa da
bool palindrom(char *s){
  for (int i = 0; 2 * i < n; i++) {
    if (s[i] != s[n - 1 - i]) {
      return false;
    }
  return true;
}
bool palindrom(char *s){
  int i = 0;
  while ((2 * i < n) && (s[i] == s[n - 1 - i])) {
    i++;
  }
  return (s[i] == s[n - 1 - i]);
}

Dar cum pot să scriu un switch fără break?

Limbajul C a apărut prin 1972, când informaticienii abia începeau să înțeleagă diferențele între programarea structurată și cea nestructurată. Demonstrația că orice program se poate scrie numai cu blocuri structurate datează din 1966. În anii următori, polemica programării structurate versus cea nestructurată a polarizat lumea informaticii. Dijkstra era pro-structurare, pe când Knuth a dat exemple când instrucțiunea GOTO produce cod mai citibil.

Nu este, deci, de mirare, că limbajul C încorporează un atavism ca break. Îl vom folosi, dar doar fiindcă nu putem altfel. Nu abuzăm de el; în special, nu permitem „curgerea” dintr-o ramură într-alta. Fiecare ramură trebuie să aibă break-ul propriu.

Când este acceptabil să programăm nestructurat?

Iată câteva exemple:

  • Când o funcție are de testat 2-3-4 precondiții, este mai firesc să apelăm return prematur decât să scriem corpul principal al funcției sub 2-3-4 niveluri de indentare.
  • Cazul de bază în funcțiile recursive poate fi pus la început și terminat cu return.
  • Pentru switch folosim break căci nu putem evita asta.

În toate situațiile folosim return sau break dintr-un if, niciodată dintr-o buclă.

Un program de 10 linii poate fi TLDR

Ați încercat vreodată să citiți o carte tipărită la o editură de bloc? Cu margini de 1 mm, font de 8 și spațiere minusculă? Nu-i așa că e enervant?

Și programele pot fi ilizibile. Nu veți lucra toată viața de unii singuri, iar într-o echipă lizibilitatea este la fel de importantă ca eficiența. Uneori mi se pare că scopul vostru este un program cât mai scurt. De unde și până unde?

Încercați să deprindeți următoarele aspecte:

  • O instrucțiune pe linie. Liniile scurte fac codul mai citibil.
  • Spațierea. O linie goală este ca o virgulă. Folosiți-o acolo unde programul face trecerea între două bucăți separate logic: două funcții, două blocuri logic distincte în aceeași funcție. Nu exagerați cu spațierea. Este important ca fiecare funcție să încapă pe un singur ecran.
  • Lungimea numelor de variabile. O literă este acceptabilă numai pentru scopuri încetățenite: i, j, k pentru variabilele de ciclu, m, n pentru dimensiunile matricei. Pentru orice altceva, alegeți nume mai clare (dar nici 3 cuvinte, căci ajungem la linii prea lungi).
  • Goana stupidă după scurtimea codului. Două lucruri rele nu fac un lucru bun. Voi scrieți cod lung pentru că acolo converge procesul iterativ, iar pe parcurs îl scurtați mâncând acolade, spațiere și scurtând numele de variabile.
  • Virgula în loc de acolade. Un caz particular al punctului anterior. Sunteți tentați să folosiți virgula ca să înghesuiți două instrucțiuni în același if, fără să adăugați acolade. Vă puteți păcăli singuri.
  • Folosim for numai pentru număr cunoscut de iterații. Rezistați tentației de a deveni hackeri. Nu este o regulă unanim acceptată, dar este o idee bună. Și Wikipedia o menționează.
  • Variabile cât mai locale. Dacă tot folosiți toate prostiile din C++, măcar folosiți și lucrurile bune. Declarați variabilele cât mai local (fără însă a împăna tot programul cu declarații). În special evitați variabilele globale pentru programe netriviale. Este ușor să pierdeți socoteala cine le modifică și când.
  • Evitați freopen(). Este o idee proastă să închideți stdin și în special stdout. În stdout puteți tipări mesaje de depanare pe care, dacă cumva le uitați în program, nu se întâmplă nimic rău. Dar dacă stdout și fișierul de ieșire al problemei sunt unul și același, riscați să tipăriți gunoaie în fișierul de ieșire. În plus, freopen() este o metodă foarte lipsită de considerație. Într-un program mai mare, cine știe ce bibliotecă vrea să tipărească mesaje pe ecran. Voi îi răpiți această posibilitate.

Recursivitate inutilă

Nu vă fie frică să eliminați recursivitatea acolo unde ea nu este necesară. Cel mai comun exemplu este la problemele de programare dinamică, acolo unde, pe lângă valoarea soluției, se cere și soluția explicită.

Exemplu: cel mai lung subșir comun între două șiruri. Presupunând că avem două șiruri, a de lungime m, și b de lungime n, și că am calculat matricea d pentru toate perechile de prefixe, soluția se calculează recursiv astfel:

char s[MAX_SOL];

void solutie(int i, int j) {
  if (d[i][j]) {
    if (a[i] == b[j]) {
      solutie(i - 1, j - 1);
      s[d[i][j] - 1] = a[i];
    } else if (d[i][j - 1] > d[i - 1][j] {
      solutie(d[i][j - 1]);
    } else {
      solutie(d[i - 1][j]);
    }
  }
}
...
solutie(m - 1, n - 1);

Nu este rău, dar nu uitați că recursivitatea cere timp și memorie! Stiva de apeluri poate avea O(n) niveluri. Dacă spațiul sau timpul sunt o problemă, eliminați recursivitatea:

char solutie[MAX_SOL];

int i = m - 1, j = n - 1;
solutie[d[i][j]] = '\0';

while (d[i][j]) {
  if (a[i] == b[j]) {
    solutie[d[i][j] - 1] = a[i];
    i--;
    j--;
  } else if (d[i][j - 1] > d[i - 1][j] {
    j--;
  } else {
    i--;
  }
}

Se pierde foarte puțin din claritatea codului, căci relația de recurență nu mai este susținută de apelul recursiv propriu-zis. Totuși, condițiile de recurență (din if-uri) sunt încă vizibile, iar codul necesită O(1) spațiu.

STL este o armă cu două tăișuri

Această secțiune se aplică surselor scrise în afara concursurilor. La concurs, totul este permis. Totuși, nu uitați că omul folosește sculele cu care este obișnuit.

De ce venim la cerc? Pentru că vrem să învățăm algoritmi, nu doar să-i apelăm. Cu algoritmii din STL programați mai repede, dar nu învățați nimic. Sunt numeroase exemplele când trebuie să înțelegeți (și să particularizați) porțiuni dintr-un algoritm: pivotarea din quicksort, construirea automatului din KMP, operațiile pe vectori de biți.

Nu uitați că algoritmii din STL pot fi mai lenți sau mai consumatori de memorie decât cei scriși de voi. Este firesc, căci aceia sunt prea generali și adesea fac operații care nu sunt necesare pentru problema voastră. Qsort din stdlib, de exemplu, necesită aproape dublul memoriei și este mai lent. Am observat asta de mai multe ori. De exemplu, am trimis două surse la problema Avioane. A doua diferă doar prin faptul că mi-am scris propriul quicksort. Nu știu dacă și sortarea din biblioteca algorithm are această problemă.

La problema Dirty, am comparat sursa mea cu a unor concurenți care făceau cam același lucru, doar că foloseau vectori STL (și iteratori) în loc de vectori C. Diferența de timp este considerabilă. Ajungeți să parsați manual fișierul de intrare ca să câștigați timp. Care mai e câștigul? Ce luați pe mere dați pe pere.

Nu uitați de ce lucrăm în C/C++, nu în PHP sau în Ruby: avem nevoie de viteză, iar C se pretează cel mai bine la asta.

Sortarea, înger și demon

Sortarea din STL merită un capitol special. Nu zic să nu o folosiți ca să câștigați 10 minute la concurs. (Dacă vă ia mai mult de 10 minute să vă implementați propria sortare, deja avem probleme mai grave). Dar dacă dați una-două fuga la sortare, riscați să pierdeți esențialul din vedere.

  • Există cel puțin 5 sortări ușor de codat, fiecare cu avantajele ei (quicksort, mergesort, heapsort, radix sort, counting sort). Fiecare dintre ele are avantaje și poate fi personalizată. Luați ca exemplu problema numărării inversiunilor dintr-o permutare, dată la Șumen 2013, care se rezolvă ușor cu un merge sort adaptat. Dacă vă gândiți la sortare ca la o cutie neagră, veți uita ce posibilități aveți.
  • Radix sort și counting sort sunt O(n)! Dacă problema se pretează la o astfel de sortare, atunci sort() nu ajută, ci dăunează.
  • Unele probleme se pot rezolva pur și simplu fără sortare. Nu vă adormiți gândirea cu stereotipuri de genul „încep cu o sortare, să fie”.

Department of Redundancy Department

Evitați să copiați bucăți mari de cod cu copy-paste. Îl avem pe Victor Ponta pentru asta. Dacă aveți cazuri aproape identice, dar diferite pe alocuri, este mai bine să parametrizați codul și să-l mutați într-o funcție sau chiar într-un for.

Un exemplu concret: problema Avioane cerea, pentru anumite elemente dintr-un vector, calcularea unor distanțe la stânga și la dreapta. Cu toții ați rezolvat problema pentru direcția stângă, apoi ați dublat codul și ați modificat ce era necesar ca să-l faceți să meargă și spre dreapta. Mă simt onorat că v-a plăcut problema atât de mult, încât ați rezolvat-o de două ori. :-) Iată două metode de a elimina redundanța:

  1. Parametrizați tot ce se modifică între direcția stângă și cea dreaptă: punctul de pornire, cel de oprire, pasul (+/- 1). Fratele meu Cristi a pus tot codul într-un for în care singurul parametru era pasul (+/- 1). Deci se poate.
  2. Calculați toate valorile spre stânga, apoi întoarceți vectorul pe dos și recalculați valorile tot spre stânga.

Din nou, principiul este DRY: Don't Repeat Yourself. Riscați să găsiți un bug într-una din copii și să uitați să-l reparați și în cealaltă.

Bugurile de redundanță sunt greu de reparat pentru că avem de luptat și împotriva naturii noastre umane. Ni se pare că nu are sens să citim ambele blocuri, căci a doua e „la fel ca prima”. Nu vi s-a întâmplat niciodată să vă uitați 10 minute fără să vă dați seama ce e greșit în codul de mai jos?

for (int i = 0; i < m; i++) {
  for (int j = 0; i < n; j++) {
  }
}

Dimensiunea datelor de intrare

Fiți întotdeauna atenți la valorile minime și maxime pe care le poate lua o variabilă. Dacă vă obișnuiți să lucrați numai cu int și cu long long, veți uita că puteți face economii mari de memorie folosind short și char.

Mai mult, uneori valorile încap pe 4 biți, pe 2 sau chiar pe unul singur. Toate aceste cazuri pot fi tratate ușor cu rutine de 1-2 linii. Iată o implementare pentru baza 4 (codul complet este în media:two-bit.cpp).

#define MAX_N 1000000

unsigned char b[MAX_N / 4];

int get(int i) {
  return (b[i/4] >> (2 * (i % 4))) & 3;
}

void set(int i, int x) {
  // Clear the previous value if needed
  b[i/4] &= ~(3 << (2 * (i % 4)));
  b[i/4] ^= x << (2 * (i % 4));
}

Exemplu: la problema Palindrom primeați foarte puțină memorie. Algoritmul de programare dinamică nu este dificil, dar pentru reconstituirea soluției avem nevoie de întreaga matrice, mai exact de triunghiul superior al unei matrice de dimensiuni n x n. Cum n ≤ 5.000, în aparență avem nevoie de 25 MB. În realitate, o celulă din matrice necesită un singur bit pentru stocare, deci necesarul de memorie este 5.000 x 5.000 / 2 / 8 = 1,56 MB.

Parsarea intrării: când ai un ciocan, totul în jur pare un cui

Haideți să lămurim ceva: profesorii și propunătorii de probleme nu sunt sadici. Nu stau zile întregi să stoarcă fiecare picătură de eficiență dintr-o implementare, pentru ca apoi să vă ceară vouă să reușiți același lucru într-o oră. Limitele de timp sunt, în general, alese adăugând o marjă generoasă la o implementare curată, dar neoptimizată la sânge.

Dacă doriți să câștigați câteva zeci de milisecunde, aveți opțiunea să parsați intrarea. Dar amintiți-vă că sunteți pe un drum greșit și undeva ați pierdut din vedere ceva mult mai important. Nu lucrați cu ciocanul. Lucrați cu bisturiul.

Dacă totuși faceți parsarea datelor de intrare, faceți-o cu stil. Am observat codul următor (îl public anonim, dă-mi de veste dacă dorești credit).

const int DIM = (1 << 12);
char buff[DIM];
int poz = 0;

void read(int &numar) {
    numar = 0;
    while (buff[poz] < '0' || buff[poz] > '9')
        if (++poz == DIM)
            fread(buff, 1, DIM, stdin), poz = 0;
    while ('0' <= buff[poz] && buff[poz] <= '9') {
        numar = numar * 10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff, 1, DIM, stdin), poz = 0;
    }
}

Hai să-l scriem mai elegant și mai eficient de atât. I-am adus următoarele îmbunătățiri:

  • (de stil) Funcția de citire a unui caracter trebuie separată. Separarea bufferării la un nivel abstract este un lucru bun. Această funcție amestecă citirea bufferată cu parsarea numărului.
  • (de stil) Funcția citește în gol bufferul prima dată înainte de a citi primul bloc de pe disc. Este păcat.
  • (de eficiență) Neapărat testați prezența unei cifre cu isdigit() din <ctype.h>. Codul de mai sus testează două condiții. isdigit() nu testează decât una, căci are un tabel de 256 de valori.
  • (de eficiență) Declarați funcția / funcțiile inline. Compilatorul își poate da seama că este nevoie de asta, dar nu e garantat.
  • (posibil de eficiență) Declarați fișierul de intrare global, ca să nu mai fie trimis ca parametru. Nu ar trebui să aibă niciun efect.

Primele patru modificări produc codul:

#define BUF_SIZE 4096
char buf[BUF_SIZE];
int pos = BUF_SIZE;

inline char getChar(FILE *f) {
  if (pos == BUF_SIZE) {
    fread(buf, 1, BUF_SIZE, f);
    pos = 0;
  }
  return buf[pos++];
}

inline int readInt(FILE *f) {
  int result = 0;
  char c;
  do {
    c = getChar(f);
  } while (!isdigit(c));

  do {
    result = 10 * result + c - '0';
    c = getChar(f);
  } while (isdigit(c));

  return result;
}

Am rulat un experiment cu patru versiuni de program:

  • una care citește cu fscanf
  • una care citește cu codul de mai sus
  • una care folosește primele patru optimizări
  • una care folosește și a cincea optimizare

Fișierul de intrare are 10.000.000 de numere (79 MB). Am rulat fiecare program de zece ori, chiar pe serverul Varena, am eliminat cea mai rapidă și cea mai lentă rulare și am calculat media.

versiune timp mediu de rulare sursă
cu fscanf 4.31 s media:parse1.cpp
cu codul de mai sus 0.819 s media:parse2.cpp
cu primele patru optimizări 0.366 s media:parse3.cpp
cu toate optimizările 0.355 s media:parse3.cpp

Versiunea mai elegantă nu este mai lentă, ci chiar dimpotrivă. Pentru fișiere cu mărimi mai realiste (5-6 MB), versiunea 3 este cu circa 30 ms mai rapidă decât versiunea 2.

Nu uitați că puteți câștiga timp semnificativ, cam 50% față de versiunea cu fscanf(), folosind getc() pentru citirea caracter cu caracter. Folosim bufferul oferit de sistem. În multe situații poate fi suficient.

Morala? Să renunți la stil și să pierzi și din viteză este un compromis tare păgubos.