Shuf.js

/*
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
*/
function shuf(datasetSource, sampleSize) {
 const output = fillBaseSample(datasetSource, sampleSize)

 return randomizeOutputFromDataset(datasetSource, output)
}

/**
 * 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
 */
function fillBaseSample(datasetSource, sampleSize) {
 let filledIndexes = []
 let output = new Array(sampleSize)

 // Spread data out filling the array
 while (true) {
 const iterator = datasetSource.next()
 if (iterator.done) break

 let insertTo = Math.floor(Math.random() * output.length)
 while (filledIndexes.includes(insertTo)) {
 insertTo++
 if (insertTo === output.length) {
 insertTo = 0
 }
 }
 output[insertTo] = {
 value: iterator.value
 }

 filledIndexes = [...filledIndexes, insertTo]

 if (filledIndexes.length === sampleSize) {
 break
 }
 }

 if (filledIndexes.length < output.length) {
 // Not a large enough dataset to fill the sample - trim empty values
 output = output.filter((_, i) => filledIndexes.includes(i))
 }

 return output.map((o) => o.value)
}

/**
 * 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
 */
function randomizeOutputFromDataset(datasetSource, output) {
 const newOutput = [...output]
 let readSoFar = output.length

 while (true) {
 const iterator = datasetSource.next()
 if (iterator.done) break
 readSoFar++

 const insertTo = Math.floor(Math.random() * readSoFar)
 if (insertTo < newOutput.length) {
 newOutput[insertTo] = iterator.value
 }
 }

 return newOutput
}

// Example

/**
 * 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)
 }
}

// const source = generateRandomData(1000)
// const result = shuf(source, 10)

export { shuf, generateRandomData }