Clasele 9-10 lecția 3 - 1 oct 2014

From Algopedia
Revision as of 23:15, 14 October 2014 by Cata (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Dacă este prima oară când învățați despre pointeri, merită să citiți și o lecție predată la gimnaziu: Clasa VI/VII/VIII lecția 36 - 28 mai 2013

Radix sort (încheiere)

Ora trecută am învățat algoritmul radix sort și am văzut că el folosește triplul memoriei, ceea ce îl face ineficient. Vom încheia discutând secțiunea Radix sort fără vector suplimentar.

Pointeri

Definiție

În C și în alte limbaje, variabilele constau din trei lucruri:

  1. numele ales de programator;
  2. valoarea stocată;
  3. adresa din memorie unde este stocată valoarea.

În absența pointerilor, adresa de memorie nu este vizibilă. După cum vom vedea, în multe situații este util să avem acces la ea.

Definiție: Un pointer este o variabilă care stochează adresa altei variabile.

Limbajul C oferă tipul de date pointer, dar există și alte mecanisme pentru implementarea pointerilor. Să considerăm următorul exemplu banal:

  // căutare de minim în vector
  int minIndex = 0;
  for (int i = 1; i < n; i++) {
    if (v[i] < v[minIndex]) {
      minIndex = i;
    }
  }

Conceptual, indicii în vector (i și minIndex) sunt niște pointeri. Când găsim la poziția i un element mai mic, salvăm un pointer către „adresa” lui în cadrul vectorului, adică îi salvăm indicele. Dacă ne interesa doar valoarea minimului, nu și indicele lui, am fi putut salva direct v[i], nu i.

Ptr01.png

Implementare în C

În C folosim următoarele notații și constante:

Notație semnificație
T *ptr; Declară că ptr va stoca adresa unei variabile de tip T (unde T poate fi int sau orice alt tip).
&n Obține adresa la care este stocată variabila n. Tipul lui &n este pointer la tipul lui n.
*ptr Obține conținutul adresei la care pointează ptr. Operațiile * și & sunt complementare.
NULL Un pointer care nu duce nicăieri.

Vizual, pointerii se reprezintă prin săgeți. În imaginea de mai jos, variabilele n și ptr au fost alocare întâmplător la adresele 1238 și respectiv 5682.

  int n = 17;
  ...
  int *ptr = &n; // p este adresa unei variabile de tip întreg

Ptr02.png

Iată un exemplu mai lung care arată că putem folosi interschimbabil n și *p atunci când ne referim strict la valoarea de la adresa lui n.

  int n = 17;
  int *p = &n;          // p pointează la n;
  printf("%d\n", *p);   // tipărește 17
  n += 5;
  printf("%d\n", *p);   // tipărește 22
  *p += 5;
  printf("%d\n", n);    // tipărește 27

Vectorii sunt pointeri

În C, un vector este un pointer la primul său element. De aceea, un vector poate fi declarat în două feluri. Probabil ați întâlnit deja fenomenul la stringuri:

  char a[100];
  char *b;

În prima sintaxă, memoria solicitată este și alocată. În al doilea caz, suntem responsabili să cerem alocarea memoriei.

Un lucru interesant se întâmplă la adunarea și scăderea (sau incrementarea și decrementarea) pointerilor. Dacă incrementăm un pointer, compilatorul își dă seama că adresa trebuie să crească cu un număr de octeți egal cu dimensiunea variabilei adresate. Nu are sens să pointăm la al doilea octet dintr-un întreg pe 4 octeți. De aceea, p++ îl face pe p să urce cu patru octeți reali. De exemplu:

  int v[3] = { 10, 20, 30 };
  int *p = v;                 // p pointează la primul element al lui v
  int *q = p + 1;             // q pointează la al doilea element al lui v
  printf("%d %d\n", *p, *q);  // tipărește 10 20
  printf("%p %p\n", p, q);    // tipărește (de exemplu) 0x7fffd01665a0 0x7fffd01665a4
  printf("%ld\n", q - p);     // tipărește 1, deși adresele de mai sus diferă prin 4

Ca fapt divers, următoarele două linii sunt echivalente (dar folosiți-o pe prima, căci este mai clară):

  scanf("%d", &v[i]);
  scanf("%d", v + i);

Alocare și dealocare

În C, memoria se alocă cu malloc() și se dealocă cu free(), definite în stdlib.h. Parametrul lui malloc() este un număr de octeți. Nu uitați, așadar, să înmulțiți numărul de elemente dorite cu dimensiunea unui element. De asemenea, malloc() returnează un pointer fără tip (void*), care trebuie convertit la un pointer de tipul dorit.

  // Alocă un vector de n întregi
  int *p = (int*)malloc(n * sizeof(int));
  ...
  free(p);

În C++, memoria se alocă cu new și se dealocă cu delete (în cazul pointerilor simpli) sau delete[] (în cazul pointerilor la vectori):

  // Alocă un vector de n întregi
  int *p = new int[n];
  ...
  delete[] p;

Spre deosebire de limbaje ca Java, limbajul C nu oferă funcții de garbage collection. Programatorul este responsabil pentru gestiunea memoriei pe parcursul programului.

Transmiterea parametrilor

Acum putem lămuri ceea ce probabil știți: că, dacă dorim ca o funcție să modifice valoarea parametrilor primiți, trebuie să îi trimitem prin referință. De fapt, în C, absolut toți parametrii către funcții sunt trimiși prin valoare. Aceasta înseamnă că programul creează o copie a variabilei trimise și o pune pe stivă. Funcția operează asupra copiei, dar originalul rămâne neatins.

Putem realiza trimiterea prin referință trimițând un pointer la variabilă. Atunci putem să modificăm variabila originală -- doar pointerul trimis ca parametru rămâne nemodificat, ceea ce este bine.

Un al doilea caz în care dorim trimiterea prin referință este când variabila trimisă este foarte mare (o structură, un vector etc.). Atunci este costisitor să lăsăm programul să-i facă o copie. Desigur, în acest caz trebuie să avem grijă să nu modificăm variabila trimisă (dacă nu dorim).

În unele situații dorim să trimitem ca parametru chiar un pointer pe care să-l modificăm. Atunci trimitem funcției un pointer la pointer. De exemplu, funcția de mai jos returnează un pointer la următorul element dintr-un vector, în mod ciclic:

  int v[100], n;

  void next(int **p) {
    (*p)++;       // parentezele sunt necesare!
    if (*p - v == n) {
      *p = v;     // ciclează
    }
  }

Greșeli frecvente

Lucrul cu pointeri poate duce la blocări ale programului, iar bugurile cauzate de folosirea incorectă a pointerilor sunt notoriu de greu de depanat. Iată câteva cauze frecvente:

  • Ați uitat să inițializați un pointer. În funcție de valoarea (nedefinită) din pointer, accesarea pointerului va încerca să scrie / citească într-o zonă aberantă: peste codul programului, peste alte date, în spațiul alocat altor programe etc.
  • Funcția voastră creează și returnează un pointer la o variabilă locală. Variabilele locale se dealocă la ieșirea din funcție, iar pointerul vostru pointează undeva aiurea pe stivă.
  • Ați declarat un vector de 10 elemente și accesați v[10]. Acea adresă nu mai aparține vectorului, ci (posibil) următoarei variabile definite sau chiar altui program.
  • Trimiteți variabile mari ca parametru. Acesta nu este un bug, este doar foarte costisitor.
  • Ați pierdut ultimul pointer către o zonă de memorie alocată (prin suprascriere sau prin părăsirea domeniului de valabilitate a variabilei-pointer). Zona de memorie este dedicată programului vostru, dar nu mai aveți cum să o accesați. Această eroare se numește memory leak (scurgere de memorie) și, dacă se întâmplă într-o buclă, poate epuiza memoria.

Liste înlănțuite

Definiție

O aplicație extrem de puternică a pointerilor sunt listele înlănțuite. O listă înlănțuită (engl. linked list) este o serie de noduri în care fiecare nod stochează, printre alte informații, un pointer la următorul nod din serie.

Ptr03.png

Pentru a localiza o listă în memorie, avem nevoie doar de un pointer la primul element. Toate celelalte elemente pot fi vizitate traversând lista din pointer în pointer. Avantajul listelor este că permit inserarea și ștergerea rapidă a elementelor la orice poziție în listă, cât timp avem un pointer la acea poziție (în cazul inserării) sau cu o poziție înainte (în cazul ștergerii).

inserare ștergere
Ptr04.png Ptr05.png

Comparație cu vectorii

operație complexitate (liste) complexitate (vectori)
accesarea unui element aleator O(n) O(1)
inserare O(1) O(n)
ștergere O(1) O(n)

Observăm că marea deficiență a listelor este accesul aleator, căci nu putem ajunge la elementul de pe poziția k altfel decât pornind de la început și avansând k pași.

Implementare cu pointeri în C

Definim o structură care încapsulează informația unui element: valoarea (presupusă int) și pointerul la următorul element:

  typedef struct _list { 
    int val;
    struct _list *next;
  } list;

  list *l;

Am folosit eticheta auxiliară _list ca să evităm o problemă de tip „oul sau găina”: dacă list s-ar referi recursiv la list, care este definit doar la sfârșitul typedef-ului, atunci compilatorul ar da eroare.

Exemple de cod:

  // parcurgerea unei liste
  while (l != NULL) {
    printf("%d\n", l->val);
    l = l->next;
  }
  // inserarea unui element într-o listă; p este poziția după care facem inserarea
  void insert(list *p, int val) {
    list *elem = (list*)malloc(sizeof(list));
    elem->val = val;
    elem->next = p->next;
    p->next = elem;
  }

Observație: ordinea manipulării pointerilor este importantă! Dacă îl modificam întâi pe p->next, am fi pierdut accesul la tot restul listei.

Implementarea listelor folosind alocare dinamică (malloc() / new) este ineficientă deoarece:

  • Apelurile de alocare a memoriei trec prin kernel, care decide dacă și unde are memorie să ne aloce.
  • Memoria poate fi alocată oriunde în memorie. În general ea ne este alocată contiguu, dar nu garantat. Aceasta poate duce la probleme de caching.
  • Pe arhitecturile pe 64 de biți, un pointer are 8 octeți. Pentru o listă de int (4 octeți), pointerii triplează memoria folosită.

Implementare pe vector

Pentru a preveni aceste dezavantaje, ne putem prealoca memoria sub formă de vector și simula pointerii prin indici în acești vectori.

  #define NIL -1
  typedef struct { 
    int val;
    int next;         // indicele în vector al următorului element
  } list;

  list buf[1000];
  int bufPtr = 0;     // numărul primei celule disponibile
  // parcurgerea unei liste
  int l = ...;
  while (l != NIL) {
    printf("%d\n", buf[l].val);
    l = buf[l].next;
  }
  // inserarea unui element într-o listă; p este poziția după care facem inserarea
  void insert(int p, int val) {
    buf[bufPtr].val = val;
    buf[bufPtr].next = buf[p].next;
    buf[p].next = bufPtr++;
  }

Dezavantajul implementării pe vector este că trebuie să ne gândim de la început de câte elemente vom avea nevoie, pentru a prealoca vectorul buf. Dar, în general, merită făcut acest efort.

  • Discuție despre gestionarea memoriei dealocate (stivă de pointeri la celule).

Tipuri de liste

Listele pot fi liniare (ultimul element are un pointer nul) sau circulare (ultimul element pointează la primul. Un al treilea caz teoretic sunt listele în formă de „6”, dar acesta apare rar în practică.

Listele pot fi simplu sau dublu înlănțuite. Listele dublu înlănțuite rețin și un pointer către elementul anterior. Această structură consumă încă un pointer per element, dar poate fi utilă. De exemplu, putem șterge un element primind un pointer către element, pe când în cazul listelor simplu înlănțuite avem nevoie de un pointer către elementul anterior.

Observație: există un truc care ne permite să ștergem un element dintr-o listă simplu înlănțuită primind un pointer chiar la element:

  void șterge (list *p) {
    if (p->next != NULL) {
      list *n = p->next;
      p->val = n->val;
      p->next = n->next;
      free(n);
    }
  }

Pentru a putea folosi acest truc, însă, trebuie să ținem minte că:

  1. Valoarea elementului este copiată, ceea ce poate dura. În exemplu val este întreg, dar putea fi o structură de 1.000 de octeți.
  2. Rutina nu merge corect când p este ultimul element.

Ocazional, listele dublu înlănțuite merită stocate cu o santinelă. Predecesorul primului nod și succesorul ultimului pointează la această santinelă și invers. Practic, lista devine o listă circulară dublu înlănțuită.

Ptr06.png

Santinela simplifică uneori codul. Ea se asigură că orice listă, chiar și cea vidă, are un element. De asemenea, unele testări de NULL pot fi evitate, ceea ce duce la cod mai rapid. Iată codul care caută un element într-o listă.

  void caută(list *s, int x) {
    s->val = x;
    list *l = s->next;
    while (l->val != x) {   // Fără santinelă, aici ar fi necesar... (l != NULL && l->val != x)
      l = l->next;
    }
    return (l == s) ? NULL : l;
  }

Operații pe liste

Asigurați-vă că înțelegeți toate aceste operații pe liste liniare și circulare, simplu sau dublu înlănțuite:

  • parcurgere
  • inserare de element
  • ștergere de element
  • întoarcere pe dos
  • concatenare
  • dealocare

Aplicație: structura de date coadă

O coadă este o listă înlănțuită în care, prin convenție, facem doar următoarele operații:

  • inserare la sfârșitul cozii;
  • ștergere de la începutul cozii.

Evident, se numește coadă deoarece seamănă cu coada la un magazin. Coada urmează principiul FIFO, adică „primul venit, primul servit” (engl. first in, first out). Cozile apar peste tot în informatică, de exemplu:

  • în algoritmi: parcurgerea în lățime a grafurilor și a arborilor, algoritmul lui Lee;
  • coada de joburi a unei imprimante;
  • coada de mesaje în așteptare a unui server de e-mail;
  • coada de requesturi a unui server web (în caz că devine suprasolicitat);

Cozile se implementează, în general, direct pe un vector circular.

// TODO expandează

Probleme

Ușoare

Scrieți un program care elimină duplicatele dintr-o listă sortată.

Scrieți un program care calculează intersecția / reuniunea a două liste sortate cu elemente distincte. Varianta ușoară: creați o a treia listă. Varianta mai grea: distrugeți prima listă și modificați-o pe a doua pentru a obține rezultatul.

Scrieți un program care simulează o numărătoare în cerc ca la v-ați ascunselea. Se dau n, numărul de copii, și k, poziția de la care începe numărătoarea. Să se tipărească copiii în ordinea eliminării.

Scrieți un program care să întoarcă o listă pe dos printr-o funcție recursivă. Complexitatea programului trebuie să fie O(lungimea listei).

Scrieți un program care sortează o listă prin metoda bulelor (bubble sort).

Scrieți un program care sortează o listă prin selecție (select sort).

Moderate

Se dă un număr n. Să se tipărească al n-lea număr de forma 2^{{i}}3^{{j}}5^{{k}}, cu i, j, k ≥ 0. De exemplu, primele 10 numere sunt 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Găsiți un algoritm pentru a depista dacă o listă este liniară sau circulară. Dacă lista este circulară, aflați la ce poziție începe ciclul și care este lungimea lui.

Se dau două liste. Să se depisteze dacă ele se unesc și care este primul lor element comun. Prin „primul element comun” înțelegem elementul care aparține ambelor liste și care este cât mai apropiat de începutul primei liste. Atenție, problema are multe cazuri particulare delicate. Intersecția în „Y” este simplă, dar oricare dintre liste poate fi în formă de „6”.

Grea: LRU cache

Pentru cei avansați: încercați să proiectați următoarea structură de date, numită LRU cache.

Un cache este, în esență o tabelă hash. O tabelă hash admite următoarele trei operații în O(1):

  • inserarea unei perechi (cheie, valoare);
  • ștergerea unei perechi dându-se cheia;
  • returnarea valorii asociate, dându-se cheia.

Presupunem existența tabelelor hash (nu este nevoie să știți cum operează).

Cache-urile sunt folosite pretutindeni în practică:

  • Un server web, odată ce a calculat conținutul unei pagini, îl poate salva într-un cache pentru a răspunde instantaneu la următoarele cereri pentru aceeași pagină. El inserează în cache perechea (URL, conținut pagină).
  • Un calculator, după ce caută în DNS adresa IP corespunzătoare unui hostname, poate salva perechea (hostname, IP) într-un cache pentru accesări mai rapide în viitor.
  • Procesorul poate salva în cache-ul local pagini de memorie, pentru a le accesa mai repede.

Fiecare cache are o dimensiune limită N, un număr maxim de perechi (cheie, valoare) pe care le poate stoca. Cum procedăm când se umple? Dacă cache-ul conține deja N înregistrări și dorim să inserăm încă una, trebuie să ștergem una din înregistrările existente. O politică cu rezultate bune în practică este evacuarea LRU (engl. least recently used): ștergem înregistrarea care a fost accesată ultima oară cel mai demult. Scopul evacuării LRU este să țină în cache înregistrările accesate frecvent.

Cum am putea extinde tabela hash cu date auxiliare ca să admită evacuarea LRU, păstrând timpii O(1) pentru operații?

Temă