A classe Set

    (PECL ds >= 1.0.0)

    Introdução

    Um Set é uma sequência de valores únicos. Esta implementação usa a mesma tabela de hash que Ds\Map, onde os valores são usados como chaves e o valor mapeado é ignorado.

    Pontos Fortes

    • Os valores podem ser de qualquer tipo, incluindo objetos.
    • Suporta a sintaxe de array (colchetes).
    • A ordem de inserção é preservada.
    • Libera automaticamente a memória alocada quando seu tamanho fica baixo o suficiente.
    • add(), remove() e contains() são todos O(1).

    Pontos Fracos

    • Não suporta push(), pop(), insert(), shift() ou unshift().
    • get() é O(n) se houver valores excluídos no buffer antes do índice acessado, O(1) caso contrário.

    Resumo da classe

    class Ds\Set implements Ds\Collection, ArrayAccess {
    /* Constantes */
    const int MIN_CAPACITY = 16;
    /* Métodos */
    public add(mixed ...$values): void
    public allocate(int $capacity): void
    public capacity(): int
    public clear(): void
    public contains(mixed ...$values): bool
    public copy(): Ds\Set
    public diff(Ds\Set $set): Ds\Set
    public filter(callable $callback = ?): Ds\Set
    public first(): mixed
    public get(int $index): mixed
    public intersect(Ds\Set $set): Ds\Set
    public isEmpty(): bool
    public join(string $glue = ?): string
    public last(): mixed
    public map(callable $callback): Ds\Set
    public merge(mixed $values): Ds\Set
    public reduce(callable $callback, mixed $initial = ?): mixed
    public remove(mixed ...$values): void
    public reverse(): void
    public reversed(): Ds\Set
    public slice(int $index, int $length = ?): Ds\Set
    public sort(callable $comparator = ?): void
    public sorted(callable $comparator = ?): Ds\Set
    public sum(): int|float
    public toArray(): array
    public union(Ds\Set $set): Ds\Set
    public xor(Ds\Set $set): Ds\Set
    }

    Constantes pré-definidas

    Ds\Set::MIN_CAPACITY

    Registro de Alterações

    Versão Descrição
    PECL ds 1.3.0 A classe agora implementa ArrayAccess.
    PECL ds 1.2.7 Adicionado o método Ds\Set::map().

    Índice

    Melhore Esta Página

    Aprenda Como Melhorar Esta Página • Envie uma Solicitação de Modificação • Reporte um Problema
    ＋adicione uma nota

    Notas Enviadas por Usuários (em inglês) 2 notes

    up
    19
    Anonymous
    6 years ago
    Lookup for a Set should be O(1). This is true for sets and hashtables (eg maps) in any language.

    The way this is possible is that sets store values differently than arrays.

    In an array values are stored sequentially based on what their place is in the array and where that array is in memory, so to find your item you need to scan through the array sequentially to find your item (unless it's a sorted array, then you can use binary search at O(logn)).

    Sets declare a block of memory, like an array, but instead of putting items in memory in sequence, like an array, they determine the index of the item to add by running the item through a hash function (essentially a function that takes in an object and returns an evenly distributed, very large random number), and then modulousing the result of that hash function by the size of the memory block they have.

    So, when you call contains($needle, $mySetHaystack), php will take $needle, and feed it into a hashfunction, which will return a big number like 9283472378, then it takes the length of $mySetHaystack (let's say 31), and does 9283472378 % 31 = 28, so it checks the 28th index of $mySetHaystack to see if $needle is there. Everything in this list of operations is independent of the size of $mySetHaystack, hence the perf being O(1).

    If a hash function returns the same value for two different items (a hash collision, which totally happens), or if the modulo of that value is the same, then an array of values is stored in the set at that index. Since sets don't allow duplicate values, this happens rarely and is negligible from a perf perspective.

    You should check out the wikipedia page on hash tables (similar to sets), as there are lots of pictures that will make this concept easier to understand.
    up
    7
    Sbastien
    2 years ago
    One nice thing is the type-awarness. array_unique() lose values (whatever flag), while Ds\Set keep them.

    <?php

    $array     = [true, false, null, '', 0, '0', 123, '123'];
    var_dump(array_unique($array));
    var_dump(new \Ds\Set($array));

    /*

    Gives :

    array(4) {
    [0]=> bool(true)
    [1]=> bool(false)
    [4]=> int(0)
    [6]=> int(123)
    }
    object(Ds\Set)#1 (8) {
    [0]=> bool(true)
    [1]=> bool(false)
    [2]=> NULL
    [3]=> string(0) ""
    [4]=> int(0)
    [5]=> string(1) "0"
    [6]=> int(123)
    [7]=> string(3) "123"
    }

    */
    ＋adicione uma nota
    To Top