PHPerKaigi 2024

はじめに

Efficient data structures for PHP 7, provided as an alternative to the array.

See » this blog post for benchmarks, discussion and frequently asked questions.

add a note

User Contributed Notes 1 note

up
9
immemosol
2 years ago
A summary of the namespace.

Known big O notations

ClassName | add | contains | get | hasKey | insert | pop | push | put | remove | set | shift | unshift |
Vector | _ | ? | O(1) | _ | O(n) | O(1) | O(1) | _ | O(n) | O(1) | O(n) | O(n) |
Stack | _ | _ | _ | _ | _ | ? | _ | _ | _ | _ | _ | _ |
Set | O(1) | O(1) | O(n OR 1) | _ | _ | _ | _ | _ | O(1) | _ | _ | _ |
Queue | _ | _ | _ | _ | _ | ? | ? | _ | _ | _ | _ | _ |
PriorityQueue | _ | _ | _ | _ | _ | ? | ? | _ | _ | _ | _ | _ |
Map | _ | _ | O(1) | O(1) | _ | _ | _ | O(1) | O(1) | _ | _ | _ |
Deque | _ | ? | O(1) | ? | ? | O(1) | O(1) | _ | ? | O(1) | O(1) | O(1) |

? = method is available and big O is unknown.
_ = method is unavailable, although comparable behavior could be available
For example: `$object[] = '';` as an alternative to `$object->push('');`.

Except for PriorityQueue, all other classes
(Deque, Map, Queue, Set, Stack, Vector) implement ArrayAccess,

Main:
- interface Sequence: Collection + ArrayAccess
- interface Collection: Traversable, Countable, JsonSerializable
- Vector: Sequential structure, low memory usage
- Stack: Destructive Iteration; LIFO (Last In, First Out)
note: can only access the item at the top of the stack
- Set: Hashable, Unique Values
- Queue: Destructive Iteration; FIFO (First In, First Out)
note: can only access the item at the front of the stack
- PriorityQueue: Destructive Iteration; FIFO + Priority
Like Queue but priority determines order first, FIFO when equal priority
- Map: Hashable, Key Value Sequence (like array in comparable context)
memory usage: like array, clears memory more often
note: can use objects as keys, but that inhibits array conversion
- Deque: Double Ended Queue, low memory usage
note: buffer capacity must be ^2 (a power of 2)

Supporting:
- interface Hashable: allows objects to be used as keys (`->hash()` & `->equals()`, falls back to `spl_object_hash()`)
- class Pair: JsonSerializable, Key Value Pair, used by Map
- and some more.
To Top