array go brrr
Instant array operations
insert O(1)
remove O(1)
access O(1)
memory O(N)
Elegant API (Entire algorithms can be expressed in few lines of code)
// validate matching parens
Brrr.from('((()))()()(())()')
.to((stack, paren) =>
paren === '('
? stack.prepend(paren)
: stack.first === '('
? stack.tail()
: stack.append(paren)
)
.isEmpty()
Unoptimal array solutions are as efficient as optimal ones
Try it out at the playground
Structure
const array = new Brrr().insertLeft(-2, -1).insertRight(0, 1, 2, 3, 4);
{
left: [ -1, -1, -2 ],
right: [ 0, 1, 2, 3, 4 ]
}
array.items => [-2, -1, 0, 1, 2, 3, 4]
Indexing is guaranteed without the need of reordering thanks to simple arithmetics:
- [Symbol(-0), 3, 2, 1, 0] // left
+ [4, 5, 6, 7, 8] // right
[0] -> 0 - 4 = -4 => 0 // -
[1] -> 1 - 4 = -3 => 1 // -
[2] -> 2 - 4 = -2 => 2 // -
[3] -> 3 - 4 = -1 -> 3 // -
[4] -> 4 - 4 = 0 => 4 // +
[5] -> 5 - 4 = 1 => 5 // +
[6] -> 6 - 4 = 2 => 6 // +
[7] -> 7 - 4 = 3 => 7 // +
[8] -> 8 - 4 = 4 => 8 // +
[0, 1, 2, 3, 4, 5, 6, 7, 8]
Comparison for N = 200 000 (runned on MacBook Pro M1 chip laptop)
Benchmark
N = 200 000
brrrArray.get middle (once)
ok ~118 μs (0 s + 118333 ns)
regularArray.get middle (once)
ok ~54 μs (0 s + 54292 ns)
brrrArray.get random
ok ~7.49 ms (0 s + 7489583 ns)
regularArray.get random
ok ~7.45 ms (0 s + 7449834 ns)
brrrArray.push
ok ~7.96 ms (0 s + 7960417 ns)
regularArray.push
ok ~5.28 ms (0 s + 5283917 ns)
brrrArray.pop
ok ~8.93 ms (0 s + 8927333 ns)
regularArray.pop
ok ~2.15 ms (0 s + 2145750 ns)
brrrArray.shift 🚀
ok ~72 ms (0 s + 72263500 ns)
regularArray.shift 🐌
ok ~4.97 s (4 s + 973667083 ns)
brrrArray.unshift 🚀
ok ~5.53 ms (0 s + 5534333 ns)
regularArray.unshift 🐌
ok ~4.59 s (4 s + 588392875 ns)
all benchmarks completed
ok ~9.68 s (9 s + 679287250 ns)