Skip to content

Fast view into a subarray with an Array-like interface

Notifications You must be signed in to change notification settings

hurrymaplelad/shlyce

Repository files navigation

Shlyce

Fast view into a subarray with an Array-like interface. Assignments to the Shlyce mutate the underlying Array.

Inspired by golang slices.

NPM version Build Status

Examples

const Shlyce = require('shlyce');
const arr = [1,2,3,4,5];
const shlyce = new Shlyce(arr, 1); // Takes O(1) time, no data is copied
shlyce.length === 4;
shlyce[0] === 2;
shlyce[0] = 99; // Mutates the underlying array
arr[1] === 99;

Benchmarks

Shlyce slices in constant time and space, while Array.slice returns a new array, requiring linear time and space to copy. This difference can speed up our code tremendously.

Consider a recursive binary search of N elements:

N=250,000
Shlyce x 21,719 ops/sec ±2.09% (76 runs sampled)
[].slice x 935 ops/sec ±2.63% (71 runs sampled)

N=500,000
Shlyce x 20,628 ops/sec ±1.95% (80 runs sampled)
[].slice x 386 ops/sec ±2.77% (67 runs sampled)

N=1,000,000
Shlyce x 18,481 ops/sec ±1.94% (76 runs sampled)
[].slice x 180 ops/sec ±2.72% (65 runs sampled)
Fastest is Shlyce

Note that a well implemented binary search should run in O(log(n)) time. Using [].slice we only get O(n) time 'cause we're copying half the array for each slice.

About

Fast view into a subarray with an Array-like interface

Resources

Stars

Watchers

Forks

Packages

No packages published