Collecting Hack

Read this post in English

May 30, 2014 collections Facebook hack map pair PHP set vector
Share on:

Stamp-Collection

Ceva ce nu am abordat in blog-ul anterior au fost colectile. Hack vine cu o varietate de colectii pentru organizarea de date.

Structurile de date reprezinta o parte fundamentala a unui linbaj de programare, pentru ca acestea vor constitui modul in care informatia circula in aplicatie.

Pana la versiunea 5, PHP avea un singur tip de colectii de date, denumit “array”. Acest tip de date poate sa aiba trei moduri: array, hash table sau o combinatie intre cele doua.

In PHP 5 au fost introdusi o serie de iteratori pentru a facilita constructia de structuri. Din pacate si structurile rezultate aveau scopul sa ofere posibilitatea de a accesa obiectele intr-un mod similar cu array-urile.

Abea in PHP 5.3 au aparut structuri de date cu adevarat diferite, cum ar fi SplStack, dar si multe altele.

Cu toate astea, structuri cum ar fi vectori si tupluri nu au aparut niciodata in mod nativ. Se pot construi, dar nu este simplu sau intuitiv.

Hack din HHVM a venit cu o alta abordare, o serie de colectii native care sunt gata de folosire.

Tipurile de colectii

Lista de colectii este:

  • Vector – lista ordonata folosind un index
  • Map – hash table tip dictionar
  • Set – lista care stocheaza doar valori unice
  • Pair – un caz particular de Vector care are doar doua elemente.

Vector, Map si Set au si cate un echivalent immutable (inflexibil si read-only). Acestia sunt: ImmVector, ImmMap si ImmSet. Scopul acestor tipuri de date este sa expuna informatii pentru citire, fara sa permita modificarea acestora. O colectie immutable se poate genera direct, folosind constructorul, sau folosind metodele toImmVector, toImmMap si respectiv toImmSet.

Chiar si mai mult, exista si o serie de clase abstracte pentru a implementa cu usurinta structuri similare:

 

Vector

Avantajul unui vector este ca va avea tot timpul cheile in succesiune, iar ordinea elementelor nu se schimba. Cand vine vorba de array nu este nici o modalitate simpla de a verifica daca ar trebui sa se comporte ca un hash table sau ca un vector. La vector, spre deosebire de hash table, valoarea cheii nu este relevanta, doar succesiunea elementelor si numarul lor sunt importante.

Sa luam un exemplu:

 1<?hh
 2
 3function listVector($vector) {
 4     echo 'Listing array: ' . PHP_EOL;
 5     for($i = 0; $i < count($vector); $i++) {
 6          echo $i . ' - ' . $vector[$i] . PHP_EOL;
 7     }
 8}
 9
10$array = array(1, 2, 3);
11
12listVector($array);
13
14// eliminarea unui element din array
15unset($array[1]);
16
17listVector($array);

Rezultatul va fi:

1Listing array:
20 - 1
31 - 2
42 - 3
5Listing array:
60 - 1
7
8Notice: Undefined index: 1 in ../vector.hh on line 6
91 -

Motivul este foarte simplu: count intoarce intr-adevar numarul de elemente, dar index-ul nu este garantat secvential. Atunci cand al doilea element din array a fost eliminat, numarul de elemente s-a redus cu unul, dar index-ul 1 a ramas nealocat, iar ultimul index este egal cu marimea, asa ca nu se va mai ajunge la el.

Sa luam acelasi exemplu folosind un vector:

 1<?hh
 2… 
 3$vector = Vector{1, 2, 3}; 
 4
 5listVector($vector); 
 6
 7// eliminarea unui element din vector
 8$vector->removeKey(1);
 9
10listVector($vector);

Asa cum am anticipat, rezultatul este:

1Listing array:
20 - 1
31 - 2
42 - 3
5Listing array:
60 - 1
71 - 3

Este de remarcat ca nu se poate folosi unset, pentru ca nu este o cheie cea care se elimina, ci elementul respectiv, iar urmatoarea valoare din vector ii va lua locul.

Un alt lucru important este ca, daca un index nu exista si incercam sa-l modificam, va aparea o exceptie de tip “OutOfBoundsException”.

Cateva exemple care vor genera exceptia anterioara:

 1<?hh 
 2
 3$vector = Vector{1,2,3,4}; 
 4
 5// va functiona pentru ca cheia nr 1 exista 
 6$vector->set(1, 2);
 7
 8// nu va functiona pentru ca inca nu exista cheia 4
 9$vector->set(4, 5);
10
11// nu va functiona din acelasi motiv
12$vector[4] = 5;
13
14// pentru a adauga un element nou se pot folosi doar metode care nu specifica cheia
15$vector[] = 5;
16
17// sau
18array_push($vector, 5);

Pentru accesare de elemente problema de “OutOfBoundsException” ramane la fel. De exemplu, daca indexul 10 nu exista:

1var_dump($vector[$unsetKey]);

Un alt caz mai special este atunci cand elementul nu exista, dar se foloseste metoda “get”.

1var_dump($vector->get($unsetKey));

Exemplul anterior nu va genera o eroare, in schimb rezultat va fi “null” atunci cand nu exista cheia. Mi se pare bizar un astfel de comportament, pentru ca poate exista un element null in vector, iar rezultatul va fi acelasi.

Pentru a evita confuzia intre elemente care nu sunt definite si elemente care sunt null, exista o metoda speciala pentru a vedea daca exista cheia:

1var_dump($vector->containsKey($unsetKey));

Scoaterea elementelor din vector se face folosind:

1$vector->remove($key);

Sau, pentru scoaterea ultimului element:

1$vector->pop();

Map

Intr-un hash table, fata de un vector, ordinea si numarul elementelor nu sunt foarte relevante. In schimb, asocierea cheie-valoare este foarte importanta. Din acest motiv, un Map se mai numeste si “dictionar” – pentru ca poti ajunge usor de la o cheie la o valoare, pentru ca sunt “mapate”. De acolo si denumirea de “Map”.

Implementarea HHVM va retine si ordinea in care elementele au fost introduse.

In PHP, echivalentului unui Map era un array asociativ.

Fata de Vector, Map are nevoie de o cheie care va ramane permanent asociata cu elementul, indiferent daca se vor scoate sau adauga elemente in colectie.

Functile array_push sau array_shift nu vor functiona pentru Map, pentru ca acesta nu trimit o cheie, iar asocierea cheie-valoare nu ar fi controlata:

1<?hh 
2
3$map = Map{0 => 'a', 1 => 'b', 3 => 'c'};
4
5array_push($map, 'd');
6
7array_unshift($map, 'e');
8
9var_dump($map);

Va genera urmatorul rezultat:

 1Warning: Invalid operand type was used: array_push expects array(s) or collection(s) in ../map.hh on line 5
 2
 3Warning: array_unshift() expects parameter 1 to be an array, Vector, or Set in ../map.hh on line 7
 4object(HH\Map)#1 (3) {
 5  [0]=>
 6  string(1) "a"
 7  [1]=>
 8  string(1) "b"
 9  [3]=>
10  string(1) "c"
11}

Dupa cum se poate vedea, elementele nu au fost adaugate si fiecare din cazuri a generat cate un Warning.

Adaugarea efectiva se poate face folosind:

 1<?hh 
 2
 3$map = Map{0 => 'a', 1 => 'b', 3 => 'c'};
 4
 5// adaugarea unui element folosind sintaxa de array
 6$map['new'] = 'd';
 7
 8// adaugarea unui element folosind metoda structurii
 9$map->set('newer', 'e');
10
11var_dump($map);

Rezultatul va fi:

 1object(HH\Map)#1 (5) {
 2  [0]=>
 3  string(1) "a"
 4  [1]=>
 5  string(1) "b"
 6  [3]=>
 7  string(1) "c"
 8  ["new"]=>
 9  string(1) "d"
10  ["newer"]=>
11  string(1) "e"
12}

Spre deosebire de Vector, pentru ca elementul care se schimba este strans legat de cheie, unset este o metoda valida de a elimina un element:

1unset($map[$key]);

Structura are si o metoda pentru a elimina elementul cu o anumita cheie:

1$map->remove($key);

In acest caz, nici una din optiuni nu va genera o eroare daca nu exista cheia.

Exceptia de “OutOfBoundsException” se aplica si aici pentru chei care nu sunt definite, dar la fel ca la Vectori, exista o metoda pentru a testa daca exista cheia:

1$map->contains($key);

Similar cu Vector, exista o metoda care intoarce cheia setata sau null daca aceasta nu exista:

1$map->get($key);

Pentru a ne asigura ca nu se genereaza o exceptie “OutOfBoundsException”, un Map nu ar trebui parcurs cu “for”, ci doar cu “foreach”.

Pentru ca metoda “pop” de la vector nu se bazeaza pe o cheie, nu exista in structura Map.

Set

Seturile au scopul de a pastra unicitatea valorilor. Pentru aceasta structura, valorile sunt restrictionate doar la tipurile scalare: string si integer.

Interfata pentru aceasta structura este mult mai simpla decat la Vector si Map, pentru ca scopul este mult mai limitat.

Pentru Set cheia nu poate fi accesata, dar este relevanta din alt punct de vedere.

Sa luam un exemplu pentru a evidentia:

1<?hh
2$set = Set{'a', 'b', 'c'}; 
3
4foreach($set as $key => $val) {
5     echo $key . ' - ' . $val . PHP_EOL;
6}

Rezultatul va fi:

1a - a
2b - b
3c - c

Cheia si valoarea sunt identice, un mod ingenios de a pastra si unicitatea.

Cu toate astea, operatiunea este transparenta, lucru care permite adaugarea de elemente fara a referentia o cheie:

 1<?hh
 2
 3$set = Set{'a', 'b', 'c'};
 4
 5array_push($set, 'd');
 6
 7array_unshift($set, 'e');
 8
 9$set[] = 'f';
10
11var_dump($set);

Vom avea un rezultat similar cu cel de la vectori:

1object(HH\Set)#1 (6) {
2  string(1) "e"
3  string(1) "a"
4  string(1) "b"
5  string(1) "c"
6  string(1) "d"
7  string(1) "f"
8}

Chiar daca se pot adauga noi valori folosind operatorul [], acestea nu pot fi referentiate folosind acest operator:

1<?hh
2
3$set = Set{'a', 'b', 'c'};
4
5echo $set['a'];

Va genera eroarea:

1Fatal error: Uncaught exception 'RuntimeException' with message '[] operator not supported for accessing elements of Sets' in ../set.hh:5
2Stack trace:
3#0 {main}

Pentru scoaterea de elemente se poate folosi doar metoda nativa (remove) si metode care nu presupun referentierea de chei:

 1<?hh 
 2
 3$set = Set{'a', 'b', 'c', 'd'}; 
 4
 5array_pop($set); 
 6
 7array_shift($set); 
 8
 9$set->remove('b');
10
11var_dump($set);

Rezultatul va fi:

1object(HH\Set)#1 (1) {
2  string(1) "c"
3}

Fata de Vector si Map, metoda “remove” va primi valoarea, nu cheia de acces.

Pentru Set nu exista nici un fel de cheie de acces, deci cam tot ce putem sa facem este sa verificam daca un element exista, folosind “contains”:

1$set->contains($value);

Metoda va returna o valoarea booleana, care arata daca elementul exista sau nu.

Pair

O pereche este o colectie cu doua elemente. Nu poate avea mai multe sau mai putine. Elementele sunt indexate la fel ca si Vectorul, printr-o cheie care in acest caz poate avea doar valorile 0 si 1.

Nu sunt multe de spus despre aceasta structura de date, pentru ca elementele nu se pot scoate, adauga sau inlocui. Acesta este si motivul pentru care nu exista un echivalent immutable, deoarece structura in sine nu este flexibila:

1<?hh 
2
3$pair = Pair{'a', 'b'}; 
4
5foreach($pair as $key => $val) {
6     echo $key . ' - ' . $val . PHP_EOL;
7}

Rezultatul va fi:

10 - a
21 - b

O structura foarte simpla cu un scop foarte simplu.

Notiuni comune

Aproape toate structurile prezentare anterior au cateva metode si comportamente comune. Spun aproape toate, pentru ca Set si mai ales Pair, prin natura lor mai restrictiva, nu dispun de unele functionalitati pe care Vector si Map le au.

Filter

Este o functie de filtrare care vine din programarea functionala. Scopul este de a filtra o structura de date si de a genera una noua de acelasi fel, exceptie facand Pair, ca urmare a restrictiei legate de numarul de elemente. In PHP, echivalentul este array_filter.

Vector si Map au doua metode: filter si filterWithKey. Acestea accepta un argument de tip “callable”, cu alte cuvinte o functie:

 1<?hh 
 2
 3$vector = Vector{'a', 'b', 'c', 'd', 'e'}; 
 4
 5// eliminarea elementului cu valoarea 'a' 
 6$result = $vector->filter($val ==> $val != 'a');
 7
 8// eliminarea fiecarui al doilea element folosind cheia
 9$result2 = $vector->filterWithKey(($key, $val) ==> ($key % 2) == 0);
10
11var_dump($vector);
12var_dump($result);
13var_dump($result2);

Rezultatul va fi:

 1object(HH\Vector)#1 (5) {
 2  [0]=>
 3  string(1) "a"
 4  [1]=>
 5  string(1) "b"
 6  [2]=>
 7  string(1) "c"
 8  [3]=>
 9  string(1) "d"
10  [4]=>
11  string(1) "e"
12}
13object(HH\Vector)#3 (4) {
14  [0]=>
15  string(1) "b"
16  [1]=>
17  string(1) "c"
18  [2]=>
19  string(1) "d"
20  [3]=>
21  string(1) "e"
22}
23object(HH\Vector)#5 (3) {
24  [0]=>
25  string(1) "a"
26  [1]=>
27  string(1) "c"
28  [2]=>
29  string(1) "e"
30}

Dupa cum se poate observa, rezultatul functiei “callable” este tratat ca un bool si, in functie de acesta, elemente sunt adaugate in structura rezultata.

Map are un comportament identic cu cel de la Vector, diferenta fiind doar in natura cheilor.

Un lucru interesant este ca o colectie poate sa fie si immutable, pentru ca operatiunea nu modifica structura de la care a plecat, dar colectia va fi si ea de tipul structurii initiale:

 1<?hh 
 2
 3$vector = Vector{'a', 'b', 'c'}; 
 4
 5$vector = $vector->toImmVector();
 6
 7// eliminarea elementului cu valoarea 'a'
 8$result = $vector->filter($val ==> $val != 'a');
 9
10var_dump($vector);
11var_dump($result);

Rezultatul va fi:

 1object(HH\ImmVector)#2 (3) {
 2  [0]=>
 3  string(1) "a"
 4  [1]=>
 5  string(1) "b"
 6  [2]=>
 7  string(1) "c"
 8}
 9object(HH\ImmVector)#4 (2) {
10  [0]=>
11  string(1) "b"
12  [1]=>
13  string(1) "c"
14}

Pair are si el aceleasi functii ca Vector si Map, dar comportamentul nu este identic, din cauza faptului ca un Pair poate sa aiba doar 2 elemente, nici mai mult nici mai putin. Din acest motiv, cand se filtreaza un Pair, rezultatul va fi ImmVector, adica o structura similara cu Pair, dar care nu are un numar exact de elemente:

1<?hh 
2
3$pair = Pair{'a', 'b'}; 
4
5// eliminarea elementului cu valoarea 'a' 
6$result = $pair->filter($val ==> $val != 'a');
7
8var_dump($result);

Structura rezultata va fi:

1object(HH\ImmVector)#3 (1) {
2  [0]=>
3  string(1) "b"
4}

Set nu are decat metoda “filter”, pentru ca, asa cum am demonstrat anterior, cheile sunt identice cu valorile. Daca ar fi existat si o valoare cu chei, ar fi functionat similar.

Map

O alta functie provenita din limbajele functionale este “Map”. Aceasta are scopul de a modifica valorile unei structuri, folosind o functie, rezultatul fiind o noua structura de tipul celei initiale. In PHP, echivalentul este array_map.

Similar cu filter, Vector si Map au metodele comune: “map” si “mapWithKey”. Si in acest caz, accepta un argument de tip “callable”:

 1<?hh 
 2
 3$vector = Vector {'a', 'b', 'c'}; 
 4
 5$result = $vector->map($val ==> $val . $val);
 6
 7$result2 = $vector->mapWithKey(($key, $val) ==> str_repeat($val, 1 + $key));
 8
 9var_dump($vector);
10var_dump($result);
11var_dump($result2);

Rezultatul va fi:

 1object(HH\Vector)#1 (3) {
 2  [0]=>
 3  string(1) "a"
 4  [1]=>
 5  string(1) "b"
 6  [2]=>
 7  string(1) "c"
 8}
 9object(HH\Vector)#3 (3) {
10  [0]=>
11  string(2) "aa"
12  [1]=>
13  string(2) "bb"
14  [2]=>
15  string(2) "cc"
16}
17object(HH\Vector)#5 (3) {
18  [0]=>
19  string(1) "a"
20  [1]=>
21  string(2) "bb"
22  [2]=>
23  string(3) "ccc"
24}

Rezultatul functiei “callable” este noua valoare a elementelor din structura.

La fel ca si in cazul “filter”, o colectie immutable are ca rezultat o colectie immutable.

Tot similar cu filter este si faptul ca functia map, aplicata pe un Pair, va avea ca rezultat un ImmVector:

1<?hh 
2
3$pair = Pair{'a', 'b'}; 
4
5$result = $pair->map($val ==> $val . $val);
6
7var_dump($result);

Va avea ca rezultat:

1object(HH\ImmVector)#3 (2) {
2  [0]=>
3  string(2) "aa"
4  [1]=>
5  string(2) "bb"
6}

Conversie

Unele elemente pot fi convertite in alte tipuri:

din \ catre Vector Map Set Pair Array
Vector da da da nu da
Map da da da nu da
Set da nu da nu da
Pair da da da nu da
Array da da da nu da

La tabelul de mai sus se mai adauga cateva restrictii de structura:

  1. Orice structura, cand se converteste catre Set, trebuie sa contina doar valori scalare de tip int sau string:
1(Map{})->add(Pair {'a', new stdClass()})
2    ->toSet();

Va genera eroarea:

1Fatal error: Uncaught exception 'InvalidArgumentException' with message 'Only integer values and string values may be used with Sets' in …
  1. Un Map, cand este convertit la orice alta structura in afara de array, isi va pierde cheile in majoritatea cazurilor.
    Conversia de la array catre altre structuri se face folosind:
1$vector = new Vector ($array);

In afara de Pair, toate structurile de mai sus au ca unic parametru al constructorului un element care implementeaza Traversable.

Concluzii

Hack aduce o noua perspectiva asupra celui mai popular tip de date din PHP. Motivul celor de la Facebook este unul simplu, optimizarea. Daca ai un comportament consistent, poti optimiza pentru structura respectiva. In PHP acest lucru nu este tocmai posibil, din cauza faptului ca un array in PHP poate sa fie orice fel de colectie.

Din punct de vedere al structurilor de date, mi se pare interesant sa ai astfel de tipuri de date. In framework-uri, de obicei exista structuri care emuleaza comportamentul colectiilor introduse de Hack. Spre exemplu, intr-un ORM, o colectie de obiecte este reprezentata in general ca un vector, pentru ca are scopul de a se itera asupra valorilor ei. Un obiect care reprezinta valorile unor campuri dintr-o tabela o sa fie o structura de tip Map, pentru ca valoarea campului este legata de denumirea campului.

Mi se pare foarte interesant nu doar faptul ca exista aceste structuri, dar si faptul ca exista interfete pentru a implementa unele noi.

Sper ca Hack sa influenteze PHP, aducand stucturi cu un scop bine determinat in limbaj.