Skip to content

Instantly share code, notes, and snippets.

@ChALkeR
Last active March 31, 2022 04:07
Show Gist options
  • Save ChALkeR/2b7414c4a037d8b4f65c6fca2d4e3d28 to your computer and use it in GitHub Desktop.
Save ChALkeR/2b7414c4a037d8b4f65c6fca2d4e3d28 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 search = (prefix) => {
console.time('search')
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
console.timeEnd('search')
return { first, last, count: last - first + 1 }
}
console.log(search('Tst'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment