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

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

ImplementationAppendShiftUnshift
PHP arrays0.00144 s0.27727 s0.41853 s
Ds\Vector PECL library0.00127 s0.03683 s0.03862 s
Charm\Vector0.00440 s0.00180 s0.00239 s

With 50K items

ImplementationAppendShiftUnshift
PHP arrays0.01462 s7.70034 s26.3000 s
Ds\Vector PECL library0.00668 s0.98372 s0.90171 s
Charm\Vector0.03284 s0.01046 s0.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.