2021-05-20 15:28:25 +01:00
|
|
|
/*
|
|
|
|
|
Given a data set of an unknown size,
|
|
|
|
|
Get a random sample in a random order
|
|
|
|
|
It's used in data analytics, often as a way to get a small random sample from a data lake or warehouse, or from a large CSV file
|
|
|
|
|
*/
|
2021-05-21 16:47:22 +01:00
|
|
|
function shuf (datasetSource, sampleSize) {
|
|
|
|
|
const output = fillBaseSample(datasetSource, sampleSize)
|
2021-05-20 15:28:25 +01:00
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
return randomizeOutputFromDataset(datasetSource, output)
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Fills the output if possible, with the minimum number of values
|
|
|
|
|
* @param {Iterable.<T>} datasetSource The iterable source of data
|
|
|
|
|
* @param {number} sampleSize The size of the sample to extract from the dataset
|
|
|
|
|
* @returns {Array.<T>} The random sample, as an array
|
|
|
|
|
* @template T
|
|
|
|
|
*/
|
2021-05-21 16:47:22 +01:00
|
|
|
function fillBaseSample (datasetSource, sampleSize) {
|
|
|
|
|
let filledIndexes = []
|
|
|
|
|
let output = new Array(sampleSize)
|
2021-05-20 15:28:25 +01:00
|
|
|
|
|
|
|
|
// Spread data out filling the array
|
|
|
|
|
while (true) {
|
2021-05-21 16:47:22 +01:00
|
|
|
const iterator = datasetSource.next()
|
|
|
|
|
if (iterator.done) break
|
2021-05-20 15:28:25 +01:00
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
let insertTo = Math.floor(Math.random() * output.length)
|
2021-05-20 15:28:25 +01:00
|
|
|
while (filledIndexes.includes(insertTo)) {
|
2021-05-21 16:47:22 +01:00
|
|
|
insertTo++
|
2021-05-20 15:28:25 +01:00
|
|
|
if (insertTo === output.length) {
|
2021-05-21 16:47:22 +01:00
|
|
|
insertTo = 0
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
output[insertTo] = {
|
2021-05-21 16:47:22 +01:00
|
|
|
value: iterator.value
|
|
|
|
|
}
|
2021-05-20 15:28:25 +01:00
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
filledIndexes = [...filledIndexes, insertTo]
|
2021-05-20 15:28:25 +01:00
|
|
|
|
|
|
|
|
if (filledIndexes.length === sampleSize) {
|
2021-05-21 16:47:22 +01:00
|
|
|
break
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (filledIndexes.length < output.length) {
|
|
|
|
|
// Not a large enough dataset to fill the sample - trim empty values
|
2021-05-21 16:47:22 +01:00
|
|
|
output = output.filter((_, i) => filledIndexes.includes(i))
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
return output.map((o) => o.value)
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Replaces values in the output randomly with new ones from the dataset
|
|
|
|
|
* @param {Iterable.<T>} datasetSource The iterable source of data
|
|
|
|
|
* @param {Array.<T>} output The output so far, filled with data
|
|
|
|
|
* @returns {Array.<T>} The random sample, as an array
|
|
|
|
|
* @template T
|
|
|
|
|
*/
|
2021-05-21 16:47:22 +01:00
|
|
|
function randomizeOutputFromDataset (datasetSource, output) {
|
|
|
|
|
const newOutput = [...output]
|
|
|
|
|
let readSoFar = output.length
|
2021-05-20 15:28:25 +01:00
|
|
|
|
|
|
|
|
while (true) {
|
2021-05-21 16:47:22 +01:00
|
|
|
const iterator = datasetSource.next()
|
|
|
|
|
if (iterator.done) break
|
|
|
|
|
readSoFar++
|
2021-05-20 15:28:25 +01:00
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
const insertTo = Math.floor(Math.random() * readSoFar)
|
2021-05-20 15:28:25 +01:00
|
|
|
if (insertTo < newOutput.length) {
|
2021-05-21 16:47:22 +01:00
|
|
|
newOutput[insertTo] = iterator.value
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-05-21 16:47:22 +01:00
|
|
|
return newOutput
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
|
|
|
|
|
2021-10-10 17:00:21 +02:00
|
|
|
// Example
|
2021-05-20 15:28:25 +01:00
|
|
|
|
2021-10-10 17:00:21 +02:00
|
|
|
/**
|
|
|
|
|
* Generates a random range of data, with values between 0 and 2^31 - 1
|
|
|
|
|
* @param {number} length The number of data items to generate
|
|
|
|
|
* @returns {Iterable<number>} Random iterable data
|
|
|
|
|
*/
|
|
|
|
|
function * generateRandomData (length) {
|
|
|
|
|
const maxValue = Math.pow(2, 31) - 1
|
|
|
|
|
for (let i = 0; i < length; i++) {
|
|
|
|
|
yield Math.floor(Math.random() * maxValue)
|
|
|
|
|
}
|
2021-05-20 15:28:25 +01:00
|
|
|
}
|
2021-10-10 17:00:21 +02:00
|
|
|
|
|
|
|
|
// const source = generateRandomData(1000)
|
|
|
|
|
// const result = shuf(source, 10)
|
|
|
|
|
|
|
|
|
|
export { shuf, generateRandomData }
|
