Skip to content

Instantly share code, notes, and snippets.

@Piterden
Forked from ChALkeR/array-10e6x100-search.js
Last active March 31, 2022 04:09
Show Gist options
  • Save Piterden/dc805f524f7cf1faf447d3ae7c08f666 to your computer and use it in GitHub Desktop.
Save Piterden/dc805f524f7cf1faf447d3ae7c08f666 to your computer and use it in GitHub Desktop.
const count = 10e6
const length = 100
console.time('generate')
const chars = Array(52).fill().map((_, i) => String.fromCharCode(i < 26 ? i + 65 : i + 71))
const char = () => chars[Math.random() * chars.length | 0]
const triplets = chars.flatMap(a => chars.flatMap(b => chars.flatMap(c => [a, b, c].join(''))))
const triplet = () => triplets[Math.random() * triplets.length | 0]
const main = Array(Math.floor(length / 3)).fill(0)
const tail = Array(length - main.length * 3).fill(0)
const word = () => [main.map(triplet).join(''), tail.map(char).join('')].join('')
const pool = []
for (let i = 0; i < count; i++) pool.push(word())
console.timeEnd('generate')
console.time('sort')
pool.sort()
console.timeEnd('sort')
if (typeof process !== 'undefined') console.log(`${process.memoryUsage().rss / 2**20} MiB`)
const query = (q) => {
let pos = count / 2 | 0, delta = count / 4, res
while (res = q(pos)) {
if (res < 0) pos -= delta | 0 || 1
if (res > 0) pos += delta | 0 || 1
if (pos < 0 || pos >= count) return null
delta /= 2
}
return pos
}
const binary = (prefix) => {
console.time(`binary ${prefix}`)
const compare = (str) => (str < prefix) ? +1 : str.startsWith(prefix) ? 0 : -1
const first = query((pos) => {
const curr = compare(pool[pos])
return (curr > 0 || pos === 0) ? curr : (compare(pool[pos - 1]) - 1)
})
const last = query((pos) => {
const curr = compare(pool[pos])
return (curr < 0 || pos + 1 === count) ? curr : (compare(pool[pos + 1]) + 1)
})
if (first === null || last === null) return 0
const result = pool.slice(first, last + 1)
console.timeEnd(`binary ${prefix}`)
return result
}
const filter = (prefix) => {
console.time(`filter ${prefix}`)
const result = pool.filter((i) => i.startsWith(prefix))
console.timeEnd(`filter ${prefix}`)
return result
}
const search = (prefix) => {
const bin = binary(prefix)
const sim = filter(prefix)
return {bin, sim}
}
console.log(search('AAA'))
console.log(search('AAB'))
console.log(search('AAC'))
console.log(search('AAD'))
console.log(search('AAE'))
console.log(search('AB'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment