Skip to content

Instantly share code, notes, and snippets.

@FergusInLondon
Last active April 28, 2019 23:38
Show Gist options
  • Save FergusInLondon/d09e1f4535a9f8069b680c0fb7a0bd37 to your computer and use it in GitHub Desktop.
Save FergusInLondon/d09e1f4535a9f8069b680c0fb7a0bd37 to your computer and use it in GitHub Desktop.
Processing Sequential Data w/ "*Sliding Windows*"
/**
* A (very over-engineered, yet still impressively scruffy) implementation of a
* Sliding Window (adjacent, overlapping, and buffered.) for the processing of
* sequential data.
*
* Written very hurriedly one evening, to support a blog post.
*
* @param {array} data
* @param {int|Number} width
* @param {array?} accumulator
*/
function SlidingWindow(data, width, accumulator = []) {
/* Helper Method: a very hacky way of cloning a given variable. */
const clone = (object) => {
return JSON.parse(JSON.stringify(object));
}
let buffer = new Buffer(width);
buffer.setFromArray(data);
const AdjacentWindowSlider = (callback) => {
return (buffer.length() < 1) ?
// If there's no data available, just return the pre-defined accumulator
accumulator :
// Otherwise, clone accumulator, calculate the number of steps, and iterate through
((acc, windowCount) => {
for(let i=0; i < windowCount; i++) {
acc = callback({
window : data.slice(i*width, ((i*width)+width)),
current: i, acc, windowCount
})
}
return acc;
})(clone(accumulator), Math.ceil( data.length / width ));
};
const OverlappingWindowSlider = (callback) => {
return (buffer.length() < 1) ?
// If there's no data available, just return the pre-defined accumulator
accumulator :
// Otherwise, clone accumulator, calculate the number of steps, and iterate through
((acc, windowCount) => {
for(let i = 0; i < windowCount; i++) {
acc = callback({
window : data.slice(i, (i+width)),
current: i, acc, windowCount
});
}
return acc;
})(clone(accumulator), Math.ceil((data.length - (width - 1))));
};
const BufferedOverlappingWindowSlider = () => {
const buffer = new Buffer(width);
buffer.setFromArray(data);
return (dataPoint) => {
buffer.push(dataPoint);
return buffer.getArray();
};
};
const BufferedAdjacentWindowSlider = () => {
const buffer = new Buffer(width);
buffer.setFromArray(AdjacentWindowSlider(({window, acc}) => {
acc.push(window);
return acc;
}).pop())
return (dataPoint) => {
buffer.rotatingPush(dataPoint);
return buffer.getArray();
}
}
return {
AdjacentWindowSlider,
BufferedAdjacentWindowSlider,
OverlappingWindowSlider,
BufferedOverlappingWindowSlider
};
}
/**
* A very primitive Buffer implementation; essentially a wrapper around an array.
* This is just used for some helper methods - facilitiating functionality such
* as rotating pushes and limits.
*
* @param {int|Number} size
*/
function Buffer(size) {
let data = [];
let len = 0;
return {
/* Push to the array, ensure that the limit isn't breached. */
push: (val) => {
if (data.length >= size) {
data.shift();
}
pushCount++;
len = data.push(val);
},
/* Rotating Push: i.e clear the buffer when the limit is reached, and then
start again. */
rotatingPush: (val) => {
if (len >= width) {
data = [];
}
data.push(val)
pushCount++;
len = data.length;
return this;
},
/* Return the last element pushed to the buffer; if a number is specified
- i.e `n` - then it will return up to `n` elements. */
last: (n = 1) => {
return (n > data.length)
? data
: data.slice(Math.abs(n) * -1);
},
/* Return the length of the buffer. */
length: () => {
return data.length
},
/* Provides access to the underlying array. */
getArray: () => {
return data;
},
/* Initialises the buffer from a primitive array. */
setFromArray: (arr) => {
data = (arr.length >= size)
? arr.slice(size * -1)
: arr;
len = data.length
},
}
};
const {
OverlappingWindowSlider,
AdjacentWindowSlider,
BufferedOverlappingWindowSlider,
BufferedAdjacentWindowSlider
} = new SlidingWindow([1,2,3,4,5,8,9,3,9,4,5,2,6,1,], 3);
const randomNumber = (min, max) => {
return Number.parseFloat(
Math.random() * (max - min) - min
).toPrecision(2);
}
const demonstrationFunction = ({acc, window}) => {
acc.push(window);
return acc;
};
const averagingFunction = ({acc, window}) => {
acc.push( window.reduce((accumulator, val) => accumulator + val, 0) / window.length );
return acc;
}
console.log("--- Overlapping Window Sliding:");
console.log(OverlappingWindowSlider(demonstrationFunction));
console.log("--- Smoothing Average (Overlapping): ")
console.log(OverlappingWindowSlider(averagingFunction))
console.log("\n--- Buffered Overlapping Window Sliding:");
const bufferedOverlap = BufferedOverlappingWindowSlider();
for (let i = 6; i < 15; i++) {
console.log(bufferedOverlap(i));
}
console.log("\n--- Smoothing Average (Buffered Overlap):");
for (let i = 6; i < 20; i++) {
let window = bufferedOverlap(Math.abs(randomNumber(5,30)));
let average = window.reduce( (acc, val) => acc + val, 0) / window.length
console.log(
"[%s] => %d", window.join(", "),
Number.parseFloat(average).toPrecision(2)
);
}
console.log("\n--- Adjacent Window Sliding:");
console.log(AdjacentWindowSlider(demonstrationFunction));
console.log("--- Smoothing Average (Adjacent): ")
console.log(AdjacentWindowSlider(averagingFunction))
console.log("\n--- Buffered Adjacent Window Sliding:");
const bufferedAdjacent = BufferedAdjacentWindowSlider();
for (let i = 6; i < 15; i++) {
console.log(bufferedAdjacent(i));
}
console.log("\n--- Smoothing Average (Buffered Adjacent):");
for (let i = 6; i < 20; i++) {
let window = bufferedAdjacent(Math.abs(randomNumber(5,30)));
let average = window.reduce( (acc, val) => acc + val, 0) / window.length
console.log(
"[%s] => %d", window.join(", "),
Number.parseFloat(average).toPrecision(2)
);
}
@FergusInLondon
Copy link
Author

--- Overlapping Window Sliding:
[ [ 1, 2, 3 ],
  [ 2, 3, 4 ],
  [ 3, 4, 5 ],
  [ 4, 5, 8 ],
  [ 5, 8, 9 ],
  [ 8, 9, 3 ],
  [ 9, 3, 9 ],
  [ 3, 9, 4 ],
  [ 9, 4, 5 ],
  [ 4, 5, 2 ],
  [ 5, 2, 6 ],
  [ 2, 6, 1 ] ]

--- Smoothing Average (Overlapping): 
[ 2,
  3,
  4,
  5.666666666666667,
  7.333333333333333,
  6.666666666666667,
  7,
  5.333333333333333,
  6,
  3.6666666666666665,
  4.333333333333333,
  3 ]

--- Buffered Overlapping Window Sliding:
[ 6, 1, 6 ]
[ 1, 6, 7 ]
[ 6, 7, 8 ]
[ 7, 8, 9 ]
[ 8, 9, 10 ]
[ 9, 10, 11 ]
[ 10, 11, 12 ]
[ 11, 12, 13 ]
[ 12, 13, 14 ]

--- Smoothing Average (Buffered Overlap):
[13, 14, 10] => 12
[14, 10, 2.1] => 8.7
[10, 2.1, 2.9] => 5
[2.1, 2.9, 11] => 5.3
[2.9, 11, 6.6] => 6.8
[11, 6.6, 3.7] => 7.1
[6.6, 3.7, 0.073] => 3.5
[3.7, 0.073, 1.8] => 1.9
[0.073, 1.8, 8.3] => 3.4
[1.8, 8.3, 16] => 8.7
[8.3, 16, 4.3] => 9.5
[16, 4.3, 13] => 11
[4.3, 13, 1.6] => 6.3
[13, 1.6, 0.92] => 5.2

--- Adjacent Window Sliding:
[ [ 1, 2, 3 ], [ 4, 5, 8 ], [ 9, 3, 9 ], [ 4, 5, 2 ], [ 6, 1 ] ]

--- Smoothing Average (Adjacent): 
[ 2, 5.666666666666667, 7, 3.6666666666666665, 3.5 ]

--- Buffered Adjacent Window Sliding:
[ 6, 1, 6 ]
[ 7 ]
[ 7, 8 ]
[ 7, 8, 9 ]
[ 10 ]
[ 10, 11 ]
[ 10, 11, 12 ]
[ 13 ]
[ 13, 14 ]

--- Smoothing Average (Buffered Adjacent):
[13, 14, 12] => 13
[19] => 19
[19, 6.5] => 13
[19, 6.5, 10] => 12
[6.1] => 6.1
[6.1, 16] => 11
[6.1, 16, 9] => 10
[17] => 17
[17, 0.84] => 8.9
[17, 0.84, 11] => 9.6
[2.5] => 2.5
[2.5, 6.8] => 4.7
[2.5, 6.8, 14] => 7.8
[17] => 17

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment