charm / vector
A Vector implementation optimized for O(1) performance in operations like random access reads, pop(), push(), shift() and unshift().
Requires (Dev)
- phpunit/phpunit: ^9.5
This package is auto-updated.
Last update: 2024-10-28 12:39:21 UTC
README
A fast and memory efficient vector implementation with O(1) performance for operations like prepend, append, shift, unshift and random access.
The underlying data structure is memory effient and much faster than using operations such
as array_shift
and array_unshift
on arrays.
This vector class leverages the PHP 7 "packed arrays" to implement a vector with very high performance for the operations a Vector is greatest at - while at the same time providing instantaneous access to every item in the vector.
Performance and memory usage
Memory usage is about identical to the PHP array memory usage. The Ds\Vector
PECL library
has a slightly lower memory footprint, but is much slower for some operations.
With 10K items
Implementation | Append | Shift | Unshift |
---|---|---|---|
PHP arrays | 0.00144 s | 0.27727 s | 0.41853 s |
Ds\Vector PECL library | 0.00127 s | 0.03683 s | 0.03862 s |
Charm\Vector | 0.00440 s | 0.00180 s | 0.00239 s |
With 50K items
Implementation | Append | Shift | Unshift |
---|---|---|---|
PHP arrays | 0.01462 s | 7.70034 s | 26.3000 s |
Ds\Vector PECL library | 0.00668 s | 0.98372 s | 0.90171 s |
Charm\Vector | 0.03284 s | 0.01046 s | 0.01632 s |
Vector
The Vector data structure is a memory efficient alternative for queues and stacks. It is faster and more memory efficient than linked lists and share the following O(1) performance characteristics:
- Prepending
- Appending
- Shift out item from the bottom
- Pop item from the top
Better than linked list:
- Random access to item number n is O(1).
Same scalability O(n) as a linked list but probably a little slower:
- Removing the n'th item.
Worse than a linked list with O(n) vs O(1):
- Removing an item from a doubly linked list where you already have a reference to the item simply involves modifying some pointer references.
- A Vector will require moving all the items by one offset using the
array_splice
function.
Full test coverage
The unit tests should cover most (if not all) variations of using the vector.