charm/vector

A Vector implementation optimized for O(1) performance in operations like random access reads, pop(), push(), shift() and unshift().

2.0.1 2024-05-28 11:48 UTC

Requires (Dev)

• phpunit/phpunit: ^9.5

MIT

• Frode Børli

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.