PHPKonf Istanbul PHP Conference 2019 - Call for Papers

The Set class

(No version information available, might only be in Git)

Introduction

A Set is a sequence of unique values. This implementation uses the same hash table as Ds\Map, where values are used as keys and the mapped value is ignored.

Strengths

  • Values can be any type, including objects.
  • Supports array syntax (square brackets).
  • Insertion order is preserved.
  • Automatically frees allocated memory when its size drops low enough.
  • add(), remove() and contains() are all O(1).

Weaknesses

  • Doesn’t support push(), pop(), insert(), shift(), or unshift().
  • get() is O(n) if there are deleted values in the buffer before the accessed index, O(1) otherwise.

Class synopsis

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

Predefined Constants

Ds\Set::MIN_CAPACITY

Table of Contents

add a note add a note

User Contributed Notes 3 notes

up
2
Anonymous
10 months 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
0
rtheunissen at php dot net
5 months ago
Lookups by value are O(1), lookups by index are O(n) if there are deleted values before the index, O(1) otherwise.
up
-4
vdavila dot sm at gmail dot com
1 year ago
I have a question is contains() a O(1)? and why?
To Top