My Profile Photo

Jociel Souza

PHP Clojure Javascript Mongodb ZendFramework


Desenvolvedor Web - Backend - PHP


Estudante de Ciência da Computação, desenvolvedor de software apaixonado por tecnologia e entusiasta de empreendedorismo,


Estudante de Ciência da Computação procurando sempre aprender algo novo, desenvolvedor web com conhecimento em PHP7^, Zend Framework, Doctrine ORM, Doctrine ODM, MongoDB, Javascript, HTML, GIT entre outros, atualmente estudando também Clojure, Elm e o paradigma funcional e tentando compartilhar o conhecimento adquirido.


PHP - Standard PHP Library (SPL) | Jociel Souza

PHP - Standard PHP Library (SPL)

Estrutura de dados e Tipos Abstratos de Dados


Quem já estudou ou pesquisou por algoritmos provavelmente já ouviu falar em Estrutura de Dados (ED), são modos genéricos de armazenar informações de forma eficiente ajudando a melhorar o desempenho e entendimento de um algoritmo. Tipos Abstratos de Dados (TAD), em um contexto de linguagem, denota um conjunto de dados e as operações possíveis de serem realizadas sob esses dados, estrutura de dados é uma forma concreta de um Tipo Abstrato de dados.

Nate Grant em Unsplash


Tipos Abstratos de Dados

Temos alguns TADs já conhecidos e bastante utilizados como Fila, Pilha, Lista, Árvore, etc, esses Tipos Abstratos de Dados podem ser divididos em dois grupos, lineares e não lineares.

Os TDA’s lineares são estruturas onde os dados são arranjados sequencialmente, estes possuem operações de adicionar ou remover um item que podem seguir modos diferentes, vamos tomar como exemplo uma Fila e uma Pilha, vamos imaginar uma fila em um caixa de um restaurante, quando uma pessoa entra na fila ela se posiciona atrás de todas as outras pessoas, no final da fila, se uma outra pessoa chegar, ela entra atrás desta, e assim por diante, seguindo esta lógica, as pessoas que estavam nas primeiras posições vão sendo atendidas e assim a fila vai “andando” e os “itens” vão sendo processados, esta forma de inserir e remover um item é chamado de FIFO (First In, First Out), Primeiro a entrar, primeiro a sair.


Agora imaginamos no mesmo restaurante alguém na cozinha lavando os pratos utilizados, a pessoa lava e coloca um sobre o outro ao lado da pia, assim vai formando-se uma pilha de pratos lavados, um em cima do outro, quando um prato é limpo é colocado no topo da pilha, caso precise ser utilizado um novo prato pra servir, como seria problemático retirar o último prato lá de baixo, podendo virar todos os outros, é retirado um prato também do topo da pilha, esta forma de inserir e remover itens é chamado de LIFO (Last In, First Out), último a entrar, primeiro a sair, o último item colocado na pilha, no topo, quando for preciso utilizar, será o primeiro a ser retirado.


Em relação aos TDA’s do tipo árvore existem diversos tipos, o que iremos ver é uma Heap, que é uma árvore binária balanceada.
Uma árvore binária é uma estrutura formada por nós onde são “guardados” os valores e cada pode ser “ligado” à no máximo dois nós filhos, nesta estrutura os dados são dispostos de forma hierárquica, o primeiro nó da árvore é chamado raiz da árvore, os últimos nós são chamados nós folhas.
Existem outros conceitos relacionados a árvores como grau, altura, percorrer uma árvore, entre outros, não iremos entrar em detalhes aqui.


SPL

A maioria das linguagens de programação fornecem bibliotecas que implementam essas abstrações, restando apenas usarmos. Desde a versão 5 o PHP tem built in a biblioteca Standard PHP Library (SPL). A SPL é um conjunto de interfaces e classes que fornecem algumas soluções de estrutura de dados pronta paras serem utilizadas, vamos ver o funcionamento de algumas delas.


Fila (SplQueue)

Esta estrutura, como o nome sugere, tem como comportamento o mesmo que uma fila do mundo real, cada item inserindo é alocado atrás do último já existente, e quando executado uma operação de remover, é retirado o primeiro item no momento da fila.
Usando a SplQueue da SPL.

<?php
    $queue = SplQueue();
    $queue->enqueue("pessoa 1");
    $queue->enqueue("pessoa 2");
    $queue->enqueue("pessoa 3");
    $queue->enqueue("pessoa 4");

No exemplo usamos a operação enqueue que “enfileira” itens. Para remover um item usamos a operação dequeue.

<?php
    echo $queue->dequeue(); // Remove “pessoa 1”
    echo $queue->dequeue(); // Remove “pessoa 2”

Cada vez que executamos essa operação ele remove o item que está atualmente na primeira posição da fila.
A Fila também possui uma operação para verificar se está vazia ou não.

<?php
    $queue = SplQueue();
    echo $queueisEmpty(); // true


Pilha (SplStack)

Podemos imagina uma Pilha como um conjunto de itens um em cima do outro formando uma “pilha” de itens. Usamos a SplStack para trabalhar com essa estrutura, uma Pilha possui duas operações básicas, push para empilhar um item e pop para desempilhar um item.

<?php
    $stack = SplStack();
    $stack->push("prato 1");
    $stack->push("prato 2");
    $stack->push("prato 3");
    $stack->push("prato 4");

Agora podemos observar o comportamento da Pilha, podemos imaginar visualmente a estrutura do exemplo da seguinte forma:

"prato 4"
"prato 3"
"prato 2"
"prato 1"

Como vimos anteriormente, quando removemos um item de uma Pilha, é removido o item que está atualmente no topo da estrutura.

<?php
    echo $stack->pop(); // Remove "prato 4"
    echo $stack->pop(); // Remove "prato 3"

Agora caso inserirmos mais itens na Pilha, observando o comportamento descrito anteriormente.

<?php
    $stack->push("prato 6");
    $stack->push("prato 7");

Seguindo o comportamento normal de uma Pilha de inserir um item sempre no topo, teremos os seguintes dados:

"prato 7"
"prato 6"
"prato 2"
"prato 1"

A Pilha também possui a operação para verificar se existe está vazia.

<?php
    $stack = SplStack();
    echo $stack->isEmpty(); // true


Deque

A SPL possui a SplDoublyLinkedList, esta estrutura implementa um tipo de Lista, a diferença é que a SplDoublyLinkedList permite a inserção ou remoção de dados em ambos os lados, sendo então um Deque, portando podemos inserir ou remover um item tanto no que seria o início da lista quanto no que seria o final da lista.

A SplDoublyLinkedList possui quatro operações básicas, inserir no início da lista, inserir no final da lista, remover do início da lista e remover do final da lista.

A operação unshift enfileira um item no início da lista.

<?php
    $doublyLinkedList = new SplDoublyLinkedList();
    doublyLinkedList->unshift("Arroz");
    doublyLinkedList->unshift("Pimentão");
    doublyLinkedList->unshift("Cenoura");
    doublyLinkedList->unshift("Tomate");

Mesmo que coloquemos os itens em uma ordem inversa, quando executado a operação com um item, ele é colocado sempre no início da lista. No momento esse exemplo tem a seguinte estrutura:

Tomate
Cenoura
Pimentão
Arroz

A operação push enfileira um item no final da lista, vamos pegar a lista anterior e adicionar um item ao final dela.

<?php
    doublyLinkedList->push("Feijão");

Agora nossa lista está completa:

Tomate
Cenoura
Pimentão
Arroz
Feijão // Item inserido no final da lista com push

Para desenfileirar temos duas operações, shift para remover do início da lista e pop para remover do final da lista.

<?php
    doublyLinkedListshift(); // Remove Tomate
    doublyLinkedListshift(); // Remove Cenoura
    
    doublyLinkedListpop(); // Remove Feijão
    doublyLinkedListpop(); // Remove Arroz


Heap (Árvore Binária)

A classe SplHeap da SPL é uma classe abstrata que implementa uma série de funcionalidades de uma Heap, sendo uma classe abstrata para usar uma estrutura Heap da SPL é preciso usar as classes concretas SplMaxHeap e SplMinHeap. Para inserir um item usamos a operação insert.

SplMaxHeap

A SplMaxHeap para definir a posição do valor a ser inserido na árvore ela mantém sempre o maior valor como raiz da árvore, assim apresentando os valores com uma ordenação decrescente.

<?php
    $tree = new SplMaxHeap();
    $tree->insert(1);
    $tree->insert(15);
    $tree->insert(27);
    $tree->insert(9);
    $tree->insert(6);
    $tree->insert(21);
    $tree->insert(23);
    $tree->insert(3);

Vamos ver os dados.

<?php
    foreach ($tree as $item) {
        echo $item . PHP_EOL;
    }

A saída apresentada será 27, 23, 21, 15, 9, 6, 3, 1.

SplMinHeap

A SplMinHeap ao contrário da SplMaxHeap mantém o menor valor como raiz da Árvore, apresentando os valores com ordenação crescente.

<?php
    $tree = new SplMinHeap();
    $tree->insert(1);
    $tree->insert(15);
    $tree->insert(27);
    $tree->insert(9);
    $tree->insert(6);
    $tree->insert(21);
    $tree->insert(23);
    $tree->insert(3);
<?php
    foreach ($tree as $item) {
        echo $item . PHP_EOL;
    }

A saída apresentada será 1, 3, 6, 9, 15, 21, 23, 27.


Sendo a SplHeap uma classe abstrata podemos criar nossa própria classe concreta extendendo a SplHeap e implementando seu método compare que é utilizado para definir a posição do valor a ser inserido na árvore.

<?php
class Person
{
	private $age;

	public function __constructor(int $age)
	{
		$this->age = $age;
	}

	public function getAge(): int
	{
		return $this->age;
	}
}

class PersonHeap extends SplHeap
{
	public function compare($personX, $personY)
	{
		return $personX->getAge() <=> $personYgetAge();
	}
}

Criamos uma classe Person para representar algumas entidades pessoas que iremos inserir na estrutura, também criamos nossa classe PersonHeap extendendo a SplHeap, notem o método compare, ele deve retornar -1 caso o primeiro valor seja menor que o segundo, 1 caso contrário e 0 se ambos forem iguais.
O segundo parâmetro do método compare é o valor a ser inserido no momento, no exemplo anterior a estrutura apresentará os valores em ondem decrescente, para mostrar em ordem crescente basta alterar a ordem de comparação no método compare, ficando da seguinte maneira:

<?php
	public function compare($personX, $personY)
	{
		return $personY->getAge() <=> $personX->getAge();
	}

Assim quando formos percorrer os valores, será em ordem crescente.


<?php
    $person1 = new Person(15);
    $person2 = new Person(5);
    $person3 = new Person(26);
    $person4 = new Person(39);
    $person5 = new Person(3);
    
    $personHeap = new PersonHeap();
    
    $personHeapinsert($person1);
    $personHeapinsert($person2);
    $personHeapinsert($person3);
    $personHeapinsert($person4);
    $personHeapinsert($person5);
    
    
    foreach ($personHeap as $person) {
        echo $person->getAge();
    }

Seguindo o primeiro exemplo, de forma descendente, a saída será 39, 26, 15, 5, 3.

Também é possível verificar se a estrutura está vazia.

<?php
    $personHeap = new PersonHeap();
    $personHeap->isEmpty(); //true


SplObjectStorage

A SplObjectStorage fornece um modelo de dicionário, onde recebe um objeto e cria um hash do mesmo para fazer referência a este objeto internamente, permite apenas valores únicos e trabalha bem com grandes quantidades de objetos.

<?php
    class Person
    {
        private $name;
    
        public function __construct(string $name)
        {
            $this->name = $name;
        }
        
        public function getName(): string
        {
            return $this->name;
        }
    }

    $person1 = new Person("joao");
    $person2 = new Person("carlos");
    $person3 = new Person("jose");
    $person4 = new Person("maria");
    $person5 = new Person("julieta");

Criamos uma classe Person e algumas instâncias dessa classe, para inserir um objeto na estrutura usamos a operação attach.

<?php
    
    $splObjectStorage = new SplObjectStorage();
    
    $splObjectStorage->attach($person1);
    $splObjectStorage->attach($person2);
    $splObjectStorage->attach($person3);
    $splObjectStorage->attach($person4);
    $splObjectStorage->attach($person5);

Temos algumas operações interessantes, para verificar a quantidade de itens e se a estrutura contém um determinado objeto.

<?php
    
    var_dump($splObjectStorage->count()); // Retorna a quantidade de itens, no exemplo 5
    
    var_dump($splObjectStorage->contains($person1)); // retorna true se contém um determinado objeto

Usamos detach para remover um determinado objeto.

<?php
    
    $splObjectStorage->detach($person1);
    
    var_dump($splObjectStorage->count()); // 4


SplFixedArray

A SPL também contém uma classe chamada SplFixedArray que implementa algumas funcionalidades de arrays, algumas diferenças entre a SplFixedArray e o array normal do PHP é que o SplFixedArray é definido um tamanho fixo, permitido alterar posteriormente, e suporta apenas índice numérico inteiro.

<?php

    $fixedArray = new SplFixedArray(2);
    
    $fixedArray[0] = 10;
    $fixedArray[1] = 20;
    
    $fixedArray[2] = 30; // PHP Fatal error: .....

Podemos alterar o tamanho do array.

<?php
    $fixedArray->setSize(5);
    
    $fixedArray[2] = 30;
    $fixedArray[3] = 40;
    $fixedArray[4] = 50;

É possível também criar uma SplFixedArray a partir de um array comum.

<?php
    $arr = [10, 20, 30, 40];

    $fixedArray = SplFixedArray::fromArray($arr);
    
    var_dump($fixedArray);


Conclusão

Como é bem pouco comentado a ideia é mostrar que existe também a possibilidade de usarmos estrutura de dados em PHP e com a facilidade que temos já abstraído várias estruturas com a SPL facilitando o uso, não entrei em detalhes muito a fundo tanto das estruturas quanto de algoritmos, quem for pesquisar mais sobre vai ver que estrutura de dados e algoritmos estão interligados e tem bastante assunto teórico sobre. Aprender sobre estrutura de dados ajuda também a modelagem de software melhorando questões de algoritmos e mesmo entendimento de código de software entre outras melhorias que o aprendizado pode trazer.
Outro link interessante sobre estrutura de dados em PHP que vale a pena dar uma olhada: https://medium.com/@rtheunissen/efficient-data-structures-for-php-7-9dda7af674cd


Referências:
  • http://php.net/manual/pt_BR/spl.datastructures.php
  • livro PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP
  • https://www.youtube.com/watch?v=8tXgHtuj2Ko
comments powered by Disqus