Maitriser les structures de données PHP 102 - Forum Paris 2012

Maitriser les structures de données PHP 102Patrick ALLAERT

Forum PHP 2012 Paris, France

Patrick ALLAERT

● Fondateur de Libereco Technologies● Travailles avec PHP/Linux depuis '98● Core développeur eZ Publish● Auteur de l'extension PHP APM● @patrick_allaert● patrickallaert@php.net● http://github.com/patrickallaert/● http://patrickallaert.blogspot.com/

APM

APM

Structures de données PHP natives

● NULL (IS_NULL)● Booléens (IS_BOOL)● Entiers (IS_LONG)● Nombres à virgule flottante

(IS_DOUBLE)● Chaine de caractères (IS_STRING)● Tableaux (IS_ARRAY,

IS_CONSTANT_ARRAY)● Objets (IS_OBJECT)● Ressources (IS_RESOURCE)● Callable (IS_CALLABLE)

Les structures de données sur Wikipedia● 2-3-4 tree● 2-3 heap● 2-3 tree● AA tree● Abstract syntax tree● (a,b)-tree● Adaptive k-d tree● Adjacency list● Adjacency matrix● AF-heap● Alternating decision

tree● And-inverter graph● And–or tree● Array● AVL tree● Beap● Bidirectional map● Bin● Binary decision

diagram● Binary heap● Binary search tree● Binary tree● Binomial heap● Bit array● Bitboard

● Bit field● Bitmap● BK-tree● Bloom filter● Boolean● Bounding interval

hierarchy● B sharp tree● BSP tree● B-tree● B*-tree● B+ tree● B-trie● Bx-tree● Cartesian tree● Char● Circular buffer● Compressed suffix

array● Container● Control table● Cover tree● Ctrie● Dancing tree● D-ary heap● Decision tree● Deque

● Directed acyclic graph

● Directed graph● Disjoint-set● Distributed hash

table● Double● Doubly connected

edge list● Doubly linked list● Dynamic array● Enfilade● Enumerated type● Expectiminimax tree● Exponential tree● Fenwick tree● Fibonacci heap● Finger tree● Float● FM-index● Fusion tree● Gap buffer● Generalised suffix

tree● Graph● Graph-structured

stack● Hash● Hash array mapped

trie

● Hashed array tree● Hash list● Hash table● Hash tree● Hash trie● Heap● Heightmap● Hilbert R-tree● Hypergraph● Iliffe vector● Image● Implicit kd-tree● Interval tree● Int● Judy array● Kdb tree● Kd-tree● Koorde● Leftist heap● Lightmap● Linear octree● Link/cut tree● Linked list● Lookup table

● Map/Associative array/Dictionary

● Matrix● Metric tree● Minimax tree● Min/max kd-tree● M-tree● Multigraph● Multimap● Multiset● Octree● Pagoda● Pairing heap● Parallel array● Parse tree● Plain old data

structure● Prefix hash tree● Priority queue● Propositional

directed acyclic graph

● Quad-edge● Quadtree● Queap● Queue● Radix tree● Randomized binary

search tree● Range tree

● Rapidly-exploring random tree

● Record (also called tuple or struct)

● Red-black tree● Rope● Routing table● R-tree● R* tree● R+ tree● Scapegoat tree● Scene graph● Segment tree● Self-balancing

binary search tree● Self-organizing list● Set● Skew heap● Skip list● Soft heap● Sorted array● Spaghetti stack● Sparse array● Sparse matrix● Splay tree● SPQR-tree● Stack● String● Suffix array

● Suffix tree● Symbol table● Syntax tree● Tagged union (variant

record, discriminated union, disjoint union)

● Tango tree● Ternary heap● Ternary search tree● Threaded binary tree● Top tree● Treap● Tree● Trees● Trie● T-tree● UB-tree● Union● Unrolled linked list● Van Emde Boas tree● Variable-length array● VList● VP-tree● Weight-balanced tree● Winged edge● X-fast trie● Xor linked list● X-tree● Y-fast trie● Zero suppressed

decision diagram● Zipper● Z-order

Jeu:Pouvez-vous reconnaitre ces

structures/concepts?

Array: Le mensonge PHP

Les “Arrays” PHP ne sont pas de vrais tableaux!

Array: Le mensonge PHP

Les “Arrays” PHP ne sont pas de vrais tableaux!

Un tableau ressemble typiquement à:

Data DataDataData Data Data

0 1 2 3 4 5

Array: Le mensonge PHP

Les “Arrays” PHP peuvent être modifiés dynamiquement et être itérés dans différentes directions (reset(), next(), prev(), end()), et ce exclusivement avec des operations en O(1).

Array: Le mensonge PHP

Les “Arrays” PHP peuvent être modifiés dynamiquement et être itérés dans différentes directions (reset(), next(), prev(), end()), et ce exclusivement avec des operations en O(1).

Imaginons une liste doublement chainée:

Data Data Data Data Data

Head Tail

Permet d'implémenter: Liste, Deque, File et Tas

Array: Le mensonge PHP

Les éléments d'un“Array” PHP peuvent à tout moment être accédés au moyen d'une clé (index).

Array: Le mensonge PHP

Les éléments d'un“Array” PHP peuvent à tout moment être accédés au moyen d'une clé (index).

Voyons avec une table de hachage:

Data Data Data Data Data

Head Tail

Bucket Bucket Bucket Bucket Bucket

Bucket pointers array

Bucket *

0

Bucket *

1

Bucket *

2

Bucket *

3

Bucket *

4

Bucket *

5 ...

Bucket *

nTableSize -1

Array: Le mensonge PHP

http://php.net/manual/fr/language.types.array.php:

“Ce type est optimisé pour différentes utilisations ; il peut être considéré comme un tableau, une liste, une table de hashage, un dictionnaire, une collection, une pile, une file d'attente et probablement plus.”

Optimisé pour tous les cas ≈ optimisé pour aucun cas!

Array: Le mensonge PHP

● En C: 100 000 entiers (long sur 64bits => 8 octets) peuvent être stockés moyennant 0.76 Mo.

● En PHP: cela prend 13.97 Mo!≅● Une variable PHP (contenant un entier par

exemple) prend 48 octets.● L'overhead des buckets pour chacune des entrées

d'un “array” est approximativement: 96 octets.● Plus de détails:

http://nikic.github.com/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

Structures de données

Structs (ou records, tuples,...)

Structs (ou records, tuples,...)

● Une struct est une valeur contenant habituellement plusieurs autres valeurs et qui sont accédées moyennant un nom.

● Exemple:Person => firstName / lastNameComplexNumber => realPart / imaginaryPart

Structs – Avec un array

$person = array( "firstName" => "Patrick", "lastName" => "Allaert");

Structs – Avec une classe

$person = new PersonStruct( "Patrick", "Allaert");

Structs – Avec une classe (Implémentation)

class PersonStruct{ public $firstName; public $lastName; public function __construct($firstName, $lastName) { $this->firstName = $firstName; $this->lastName = $lastName; }}

Structs – Avec une classe (Implémentation)

class PersonStruct{ public $firstName; public $lastName; public function __construct($firstName, $lastName) { $this->firstName = $firstName; $this->lastName = $lastName; } public function __set($key, $value) { // a. Ne rien faire // b. trigger_error() // c. Lancer une exception }}

Structs – Avantages et inconvénients

Array+ Utilise moins de mémoire (PHP < 5.4)

- Utilise plus de mémoire (PHP = 5.4)

- Pas de type hinting

- Structure flexible

+|- Moins OO

Class- Utilise plus de mémoire (PHP < 5.4)

+ Utilise moins de mémoire (PHP = 5.4)

+ Type hinting possible

+ Structure rigide

+|- Plus OO

(vrai) Arrays

(vrai) Tableaux

● Un tableau est une collection de taille fixe dont les éléments sont tous identifiés par un index numérique.

(vrai) Tableaux

● Un tableau est une collection de taille fixe dont les éléments sont tous identifiés par un index numérique.

Data DataDataData Data Data

0 1 2 3 4 5

(vrai) Tableaux – Avec SplFixedArray

$array = new SplFixedArray(3);$array[0] = 1; // ou $array->offsetSet()$array[1] = 2; // ou $array->offsetSet()$array[2] = 3; // ou $array->offsetSet()$array[0]; // donne 1$array[1]; // donne 2$array[2]; // donne 3

(vrai) Tableaux – Avantages et inconvénients

Array- Utilise plus de mémoire

+|- Moins OO

SplFixedArray+ Utilise moins de mémoire

+|- Plus OO

Files

Files

● Une pile est une collection ordonnée respectant l'ordre First In, First Out (FIFO).

● Les éléments sont insérés d'un côté et enlevés de l'autre.

Files

● Une pile est une collection ordonnée respectant l'ordre First In, First Out (FIFO).

● Les éléments sont insérés d'un côté et enlevés de l'autre.

Data DataDataData Data Data

Data

Data

Enqueue

Dequeue

Files – Avec un array

$queue = array();$queue[] = 1; // ou array_push()$queue[] = 2; // ou array_push()$queue[] = 3; // ou array_push()array_shift($queue); // donne 1array_shift($queue); // donne 2array_shift($queue); // donne 3

Files – Avec SplQueue

$queue = new SplQueue();$queue[] = 1; // ou $queue->enqueue()$queue[] = 2; // ou $queue->enqueue()$queue[] = 3; // ou $queue->enqueue()$queue->dequeue(); // donne 1$queue->dequeue(); // donne 2$queue->dequeue(); // donne 3

Piles

Piles

● Une pile est une collection ordonnée respectant l'ordre Last In, First Out (LIFO).

● Les éléments sont insérés et enlevés du même côté.

Piles

● Une pile est une collection ordonnée respectant l'ordre Last In, First Out (LIFO).

● Les éléments sont insérés et enlevés du même côté.

Data DataDataData Data Data

Data

Data

Push

Pop

Piles – Avec un array

$stack = array();$stack[] = 1; // ou array_push()$stack[] = 2; // ou array_push()$stack[] = 3; // ou array_push()array_pop($stack); // donne 3array_pop($stack); // donne 2array_pop($stack); // donne 1

Piles – Avec SplStack

$stack = new SplStack();$stack[] = 1; // ou $stack->push()$stack[] = 2; // ou $stack->push()$stack[] = 3; // ou $stack->push()$stack->pop(); // donne 3$stack->pop(); // donne 2$stack->pop(); // donne 1

Files/Piles – Avantages et inconvénients

Array- Utilise plus de mémoire

(overhead / entrée: 96 octets)

- Pas de type hinting

+|- Moins OO

SplQueue / SplStack+ Utilise moins de mémoire

(overhead / entrée: 48 octets)

+ Type hinting possible

+|- Plus OO

Ensembles

Personnes ayant une opinion très tranchée sur la

différenceentre geeks et

nerds

Geeks Nerds

Ensembles

● Un ensemble est une collection sans ordre spécifique particulièrement adapté pour tester l'appartenance d'une valeur à une collection ou pour réaliser une opération d'union/d'intersection/de complément entre eux.

Ensembles

● Un ensemble est une collection sans ordre spécifique particulièrement adapté pour tester l'appartenance d'une valeur à une collection ou pour réaliser une opération d'union/d'intersection/de complément entre eux.

Data

Data

Data

Data

Data

Ensembles – Avec un array

$set = array();

// Adding elements to a set$set[] = 1;$set[] = 2;$set[] = 3;

// Checking presence in a setin_array(2, $set); // truein_array(5, $set); // false

array_merge($set1, $set2); // unionarray_intersect($set1, $set2); // intersectionarray_diff($set1, $set2); // complement

Ensembles – Avec un array

$set = array();

// Adding elements to a set$set[] = 1;$set[] = 2;$set[] = 3;

// Checking presence in a setin_array(2, $set); // truein_array(5, $set); // false

array_merge($set1, $set2); // unionarray_intersect($set1, $set2); // intersectionarray_diff($set1, $set2); // complement

True performance killers!

Ensembles – Abus

if ($value === "val1" || $value === "val2" || $value === "val3"))){ // ...}

Ensembles – Abus

if (in_array($value, array("val1", "val2", "val3"))){ // ...}

Ensembles – Abus

switch ($value){ case "val1": case "val2": case "val3": // ...}

Ensembles – Avec un array (types simples)

$set = array();

// Adding elements to a set$set[1] = true; // Any dummy value$set[2] = true; // is good but NULL!$set[3] = true;

// Checking presence in a setisset($set[2]); // trueisset($set[5]); // false

$set1 + $set2; // unionarray_intersect_key($set1, $set2); // intersectionarray_diff_key($set1, $set2); // complement

Ensembles – Avec un array (types simples)

● Attention : les clés d'un array PHP ne peuvent être que des entiers ou des strings !

$set = array();

// Adding elements to a set$set[1] = true; // Any dummy value$set[2] = true; // is good but NULL!$set[3] = true;

// Checking presence in a setisset($set[2]); // trueisset($set[5]); // false

$set1 + $set2; // unionarray_intersect_key($set1, $set2); // intersectionarray_diff_key($set1, $set2); // complement

Ensembles – Avec un array (objets)

$set = array();

// Adding elements to a set$set[spl_object_hash($object1)] = $object1;$set[spl_object_hash($object2)] = $object2;$set[spl_object_hash($object3)] = $object3;

// Checking presence in a setisset($set[spl_object_hash($object2)]); // trueisset($set[spl_object_hash($object5)]); // false

$set1 + $set2; // unionarray_intersect_key($set1, $set2); // intersectionarray_diff_key($set1, $set2); // complement

Ensembles – Avec un array (objets)

$set = array();

// Adding elements to a set$set[spl_object_hash($object1)] = $object1;$set[spl_object_hash($object2)] = $object2;$set[spl_object_hash($object3)] = $object3;

// Checking presence in a setisset($set[spl_object_hash($object2)]); // trueisset($set[spl_object_hash($object5)]); // false

$set1 + $set2; // unionarray_intersect_key($set1, $set2); // intersectionarray_diff_key($set1, $set2); // complement

Store a reference of the object!

Ensembles – Avec SplObjectStorage (objets)

$set = new SplObjectStorage();

// Adding elements to a set$set->attach($object1); // ou $set[$object1] = null;$set->attach($object2); // ou $set[$object2] = null;$set->attach($object3); // ou $set[$object3] = null;

// Checking presence in a setisset($set[$object2]); // trueisset($set[$object2]); // false

$set1->addAll($set2); // union$set1->removeAllExcept($set2); // intersection$set1->removeAll($set2); // complement

Ensembles – Avec QuickHash (int)

● Pas (encore?) d'opérations d'union/d'intersection/de complément.

● Fonctionnalités intéressantes : (loadFrom|saveTo)(String|File)

$set = new QuickHashIntSet(64, QuickHashIntSet::CHECK_FOR_DUPES);

// Adding elements to a set$set->add(1);$set->add(2);$set->add(3);

// Checking presence in a set$set->exists(2); // true$set->exists(5); // false

// Soonish: isset($set[2]);

Ensembles – Avec des bitsets

define("E_ERROR", 1); // ou 1<<0define("E_WARNING", 2); // ou 1<<1define("E_PARSE", 4); // ou 1<<2define("E_NOTICE", 8); // ou 1<<3

// Adding elements to a set$set = 0;$set |= E_ERROR;$set |= E_WARNING;$set |= E_PARSE;

// Checking presence in a set$set & E_ERROR; // true$set & E_NOTICE; // false

$set1 | $set2; // union$set1 & $set2; // intersection$set1 ^ $set2; // complement

Ensembles – Avec des bitsets (exemple)

Au lieu de:function remove($path, $files = true, $directories = true, $links = true, $executable = true){ if (!$files && is_file($path)) return false; if (!$directories && is_dir($path)) return false; if (!$links && is_link($path)) return false; if (!$executable && is_executable($path)) return false; // ...}

remove("/tmp/removeMe", true, false, true, false); // WTF ?!

Ensembles – Avec des bitsets (exemple)

Essayer:define("REMOVE_FILES", 1 << 0);define("REMOVE_DIRS", 1 << 1);define("REMOVE_LINKS", 1 << 2);define("REMOVE_EXEC", 1 << 3);define("REMOVE_ALL", ~0); // Setting all bits

function remove($path, $options = REMOVE_ALL){ if (~$options & REMOVE_FILES && is_file($path)) return false; if (~$options & REMOVE_DIRS && is_dir($path)) return false; if (~$options & REMOVE_LINKS && is_link($path)) return false; if (~$options & REMOVE_EXEC && is_executable($path)) return false; // ...}

remove("/tmp/removeMe", REMOVE_FILES | REMOVE_LINKS); // Much better :)

Ensembles: Conclusions

● Utilisez la clé et non la valeur lorsque vous utilisez un array PHP.

● Utilisez QuickHash pour des ensembles d'entiers si possible.

● Utilisez SplObjectStorage dès que vous travaillez avec des objecs.

● N'utilisez par array_unique() / in_array() / array_search() lorsque vous avez besoin d'un ensemble !

Maps

● Une map est une collection de paires clé/valeur où chaque clé est unique.

Maps – Avec un array

● N'utilisez pas array_merge() sur des maps.

$map = array();$map["ONE"] = 1;$map["TWO"] = 2;$map["THREE"] = 3;

// Merging maps:array_merge($map1, $map2); // SLOW!$map2 + $map1; // Fast :)

Maps multi-clés – Avec un array

$map = array();$map["ONE"] = 1;$map["UN"] =& $map["ONE"];$map["UNO"] =& $map["ONE"];$map["TWO"] = 2;$map["DEUX"] =& $map["TWO"];$map["DUE"] =& $map["TWO"];

$map["UNO"] = "once";$map["DEUX"] = "twice";

var_dump($map);/*array(6) {["ONE"] => &string(4) "once"["UN"] => &string(4) "once"["UNO"] => &string(4) "once"["TWO"] => &string(5) "twice"["DEUX"] => &string(5) "twice"["DUE"] => &string(5) "twice"}*/

Tas (Heap)

● Un tas est une structure basée sur un arbre dans lequel les éléments sont ordonnés avec la clé la plus grande (ou petite) au sommet et les plus petites (ou grandes) comme feuilles.

Tas (Heap)

● Un tas est une structure basée sur un arbre dans lequel les éléments sont ordonnés avec la clé la plus grande (ou petite) au sommet et les plus petites (ou grandes) comme feuilles.

Tas (Heap) – Avec un array

$heap = array();$heap[] = 3;sort($heap);$heap[] = 1;sort($heap);$heap[] = 2;sort($heap);

Tas (Heap) – AvecSpl(Min|Max)Heap

$heap = new SplMinHeap;$heap->insert(3);$heap->insert(1);$heap->insert(2);

Tas (Heap): Conclusions

● BEAUCOUP plus rapide que de devoir réordonner un array à chaque insertion.

● Si vous n'avez pas besoin qu'une collection soit ordonnée à chaque étape et que vous pouvez insérer toutes les données en un coup et ensuite utilisez sort(). Dans ce cas l'array est une bien meilleure approche.

● SplPriorityQueue est très similaire, considérez qu'il s'agit de la même chose que SplHeap mais où le tri est fait sur la clé et non la valeur.

Filtre de Bloom

● Un filtre de Bloom est une structure probabiliste efficace en terme d'espace permettant de tester l'appartenance d'un élément à un ensemble.

● Les faux-positifs sont possibles, mais les faux-négatifs ne le sont jamais !

● Package PECL : bloomy

Filtre de Bloom – Avec bloomy

// BloomFilter::__construct(int capacity [, double error_rate [, int random_seed ] ])$bloomFilter = new BloomFilter(10000, 0.001);

$bloomFilter->add("An element");

$bloomFilter->has("An element"); // true for sure$bloomFilter->has("Foo"); // false, most probably

Autres projets apparentés

● SPL Types: Différents types implémentés comme objet: SplInt, SplFloat, SplEnum, SplBool et SplString http://pecl.php.net/package/SPL_Types

Autres projets apparentés

● SPL Types: Différents types implémentés comme objet: SplInt, SplFloat, SplEnum, SplBool et SplString http://pecl.php.net/package/SPL_Types

● Judy: Implémentation de Sparse dynamic arrays http://pecl.php.net/package/Judy

Autres projets apparentés

● SPL Types: Différents types implémentés comme objet: SplInt, SplFloat, SplEnum, SplBool et SplString http://pecl.php.net/package/SPL_Types

● Judy: Implémentation de Sparse dynamic arrays http://pecl.php.net/package/Judy

● Weakref: Implementation de « pointeurs faibles » (Weak reference).Permet de référencer un objet sans pour autant empêcher le GC de pouvoir récupérer cet objet.

Conclusions

● Utilisez des structures de données appropriées. Cela vous permet de garder un code propre et optimal.

Conclusions

● Utilisez des structures de données appropriées. Cela vous permet de garder un code propre et optimal.

● Pensez à la complexité en termes de temps et d'espaces impliquée par vos algorithmes.

Conclusions

● Utilisez des structures de données appropriées. Cela vous permet de garder un code propre et optimal.

● Pensez à la complexité en termes de temps et d'espaces impliquée par vos algorithmes.

● Nommez vos variables de manière appropriée :Utilisez « Map », « Set », « List », « Queue »,... afin de décrire leur rôle et utilisation.

Merci

● N'oubliez pas de donner votre évaluation sur cette session sur : http://joind.in/6446

Questions?

Crédits Photos● Tuned car:

http://www.flickr.com/photos/gioxxswall/5783867752

● London Eye Structure: http://www.flickr.com/photos/photographygal123/4883546484

● Cigarette:http://www.flickr.com/photos/superfantastic/166215927

● Heap structure:http://en.wikipedia.org/wiki/File:Max-Heap.svg

● Drawers:http://www.flickr.com/photos/jamesclay/2312912612

● Stones stack:http://www.flickr.com/photos/silent_e/2282729987

● Tree:http://www.flickr.com/photos/drewbandy/6002204996