SunshinePHP 2019

Класс Set

(Информация о версии неизвестна, возможно, только в SVN)

Введение

Set - это последовательность уникальных значений. Реализация использует ту же хеш-таблицу, что и Ds\Map, в которой значения используются в качестве ключей, а связанные значения игнорируются.

Сильные стороны

  • Значения могут быть любого типа, включая объекты.
  • Поддерживает синтаксис массива (квадратные скобки).
  • Сохраняется порядок вставки.
  • Автоматически высвобождает память, когда количество элементов значительно уменьшается.
  • add(), remove() и contains() имеют сложность O(1).

Слабые стороны

  • Не поддерживает push(), pop(), insert(), shift() и unshift().
  • get() имеет сложность O(n), если есть удаленные значения в буфере, до значения, к которому происходит доступ. Иначе O(1).

Обзор классов

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

Предопределенные константы

Ds\Set::MIN_CAPACITY

Содержание

  • Ds\Set::add — Добавляет значения в набор
  • Ds\Set::allocate — Выделяет память под указанную вместимость
  • Ds\Set::capacity — Возвращает текущую вместимость
  • Ds\Set::clear — Удаляет все значения из коллекции
  • Ds\Set::__construct — Создает новый экземпляр класса
  • Ds\Set::contains — Проверяет, содержится ли в коллекции заданные значения
  • Ds\Set::copy — Возвращает поверхностную копию коллекции
  • Ds\Set::count — Возвращает количество элементов коллекции
  • Ds\Set::diff — Создает новый набор с элементами, которых нет в другом наборе
  • Ds\Set::filter — Создает новый список из элементов, выбранных с помощью заданной callback-функции
  • Ds\Set::first — Возвращает первый элемент коллекции
  • Ds\Set::get — Возвращает значение по индексу
  • Ds\Set::intersect — Создает новый набор, созданный пересечением с другим набором
  • Ds\Set::isEmpty — Проверяет, пуста ли коллекция
  • Ds\Set::join — Склеивает все значения в строку
  • Ds\Set::jsonSerialize — Возвращает коллекцию в JSON-представлении
  • Ds\Set::last — Возвращает последнее значение коллекции
  • Ds\Set::merge — Возвращает результат добавления всех заданных значений в набор
  • Ds\Set::reduce — Уменьшает коллекцию до одного значения, используя callback-функцию
  • Ds\Set::remove — Удаляет все заданные значения из набора
  • Ds\Set::reverse — Переворачивает текущую коллекцию
  • Ds\Set::reversed — Возвращает перевернутую копию коллекции
  • Ds\Set::slice — Возвращает поднабор из заданного диапазона
  • Ds\Set::sort — Сортирует коллекцию
  • Ds\Set::sorted — Возвращает отсортированную по значению копию коллекции
  • Ds\Set::sum — Возвращает сумму всех значений коллекции
  • Ds\Set::toArray — Преобразует коллекцию в массив (array)
  • Ds\Set::union — Создает новый набор из элементов текущего и переданного наборов
  • Ds\Set::xor — Создает новый набор из значений, которые есть в одном из наборов, но не в обоих одновременно
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