Skip to content

Instantly share code, notes, and snippets.

@ChALkeR

ChALkeR/array-10e6x100-search.js Secret

Last active March 31, 2022 04:07
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ChALkeR/2b7414c4a037d8b4f65c6fca2d4e3d28 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ChALkeR/2b7414c4a037d8b4f65c6fca2d4e3d28 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. ChALkeR revised this gist Jun 28, 2020. 1 changed file with 9 additions and 16 deletions.
    25 changes: 9 additions & 16 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,30 +1,23 @@
    const count = 10e6
    const length = 100

    const codes = Array(52).fill().map((_, i) => i < 26 ? i + 65 : i + 71)
    const chars = codes.map(code => String.fromCharCode(code))
    const code = () => codes[Math.random() * codes.length | 0]
    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]
    let word
    if (typeof Buffer !== 'undefined') {
    const tmp = Buffer.alloc(length)
    word = () => tmp.map(code).toString()
    } else {
    const tmp = Array(length).fill(0)
    word = () => tmp.map(char).join('')
    }

    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 = []
    console.time('generate')
    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`)
    if (typeof process !== 'undefined') console.log(`${process.memoryUsage().rss / 2**20} MiB`)

    const query = (q) => {
    let pos = count / 2 | 0, delta = count / 4, res
    @@ -52,4 +45,4 @@ const search = (prefix) => {
    return { first, last, count: last - first + 1 }
    }

    console.log(search('Tst'))
    console.log(search('Tst'))
  2. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -36,7 +36,6 @@ const query = (q) => {
    }
    return pos
    }

    const search = (prefix) => {
    console.time('search')
    const compare = (str) => (str < prefix) ? +1 : str.startsWith(prefix) ? 0 : -1
    @@ -47,10 +46,10 @@ const search = (prefix) => {
    const last = query((pos) => {
    const curr = compare(pool[pos])
    return (curr < 0 || pos + 1 === count) ? curr : (compare(pool[pos + 1]) + 1)
    }, first)
    })
    if (first === null || last === null) return 0
    console.timeEnd('search')
    return { first, last, count: last - first + 1 }
    }

    console.log(search('Tst'))
    console.log(search('Tst'))
  3. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 7 additions and 10 deletions.
    17 changes: 7 additions & 10 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -39,21 +39,18 @@ const query = (q) => {

    const search = (prefix) => {
    console.time('search')
    const compare = (str) => (str < prefix) ? +1 : str.startsWith(prefix) ? 0 : -1
    const first = query((pos) => {
    if (pool[pos] < prefix) return +1
    if (pos - 1 < 0) return pool[pos].startsWith(prefix) ? 0 : -1
    if (pool[pos - 1] >= prefix) return -1
    return 0
    const curr = compare(pool[pos])
    return (curr > 0 || pos === 0) ? curr : (compare(pool[pos - 1]) - 1)
    })
    const last = query((pos) => {
    if (pool[pos] >= prefix && !pool[pos].startsWith(prefix)) return -1
    if (pos + 1 >= count) return pool[pos].startsWith(prefix) ? 0 : +1
    if (pool[pos + 1] < prefix || pool[pos + 1].startsWith(prefix)) return +1
    return 0
    })
    const curr = compare(pool[pos])
    return (curr < 0 || pos + 1 === count) ? curr : (compare(pool[pos + 1]) + 1)
    }, first)
    if (first === null || last === null) return 0
    console.timeEnd('search')
    return last - first + 1
    return { first, last, count: last - first + 1 }
    }

    console.log(search('Tst'))
  4. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 7 additions and 7 deletions.
    14 changes: 7 additions & 7 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,17 +1,17 @@
    const count = 10e6
    const length = 100

    const char = () => {
    const l = Math.random() * 52 | 0
    return l < 26 ? l + 65 : l + 71
    }
    const codes = Array(52).fill().map((_, i) => i < 26 ? i + 65 : i + 71)
    const chars = codes.map(code => String.fromCharCode(code))
    const code = () => codes[Math.random() * codes.length | 0]
    const char = () => chars[Math.random() * chars.length | 0]
    let word
    if (typeof Buffer !== 'undefined') {
    const tmp = Buffer.alloc(length)
    word = () => tmp.map(char).toString()
    word = () => tmp.map(code).toString()
    } else {
    const tmp = Array(length).fill(0)
    word = () => tmp.map(() => String.fromCharCode(char())).join('')
    word = () => tmp.map(char).join('')
    }

    const pool = []
    @@ -56,4 +56,4 @@ const search = (prefix) => {
    return last - first + 1
    }

    console.log(search('Tst'))
    console.log(search('Tst'))
  5. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 1 addition and 2 deletions.
    3 changes: 1 addition & 2 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,12 +1,11 @@
    const count = 10e6
    const length = 100

    let word

    const char = () => {
    const l = Math.random() * 52 | 0
    return l < 26 ? l + 65 : l + 71
    }
    let word
    if (typeof Buffer !== 'undefined') {
    const tmp = Buffer.alloc(length)
    word = () => tmp.map(char).toString()
  6. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 12 additions and 5 deletions.
    17 changes: 12 additions & 5 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,12 +1,19 @@
    const count = 10e6
    const length = 100

    const letter = () => {
    let word

    const char = () => {
    const l = Math.random() * 52 | 0
    return String.fromCharCode(l < 26 ? l + 65 : l + 71)
    return l < 26 ? l + 65 : l + 71
    }
    if (typeof Buffer !== 'undefined') {
    const tmp = Buffer.alloc(length)
    word = () => tmp.map(char).toString()
    } else {
    const tmp = Array(length).fill(0)
    word = () => tmp.map(() => String.fromCharCode(char())).join('')
    }

    const word = () => Array(length).fill().map(letter).join('')

    const pool = []
    console.time('generate')
    @@ -50,4 +57,4 @@ const search = (prefix) => {
    return last - first + 1
    }

    console.log(search('Tst'))
    console.log(search('Tst'))
  7. ChALkeR revised this gist Jun 27, 2020. 1 changed file with 1 addition and 5 deletions.
    6 changes: 1 addition & 5 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -6,11 +6,7 @@ const letter = () => {
    return String.fromCharCode(l < 26 ? l + 65 : l + 71)
    }

    const word = () => {
    const arr = []
    for (let i = 0; i < length; i++) arr.push(letter())
    return arr.join('')
    }
    const word = () => Array(length).fill().map(letter).join('')

    const pool = []
    console.time('generate')
  8. ChALkeR revised this gist Jun 26, 2020. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -37,21 +37,21 @@ const query = (q) => {

    const search = (prefix) => {
    console.time('search')
    const start = query((pos) => {
    const first = query((pos) => {
    if (pool[pos] < prefix) return +1
    if (pos - 1 < 0) return pool[pos].startsWith(prefix) ? 0 : -1
    if (pool[pos - 1] >= prefix) return -1
    return 0
    })
    const end = query((pos) => {
    const last = query((pos) => {
    if (pool[pos] >= prefix && !pool[pos].startsWith(prefix)) return -1
    if (pos + 1 >= count) return pool[pos].startsWith(prefix) ? 0 : +1
    if (pool[pos + 1] < prefix || pool[pos + 1].startsWith(prefix)) return +1
    return 0
    })
    if (start === null || end === null) return 0
    if (first === null || last === null) return 0
    console.timeEnd('search')
    return end - start + 1
    return last - first + 1
    }

    console.log(search('Tst'))
    console.log(search('Tst'))
  9. ChALkeR revised this gist Jun 26, 2020. 1 changed file with 3 additions and 2 deletions.
    5 changes: 3 additions & 2 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -21,7 +21,8 @@ console.time('sort')
    pool.sort()
    console.timeEnd('sort')

    console.log(`${process.memoryUsage().rss / 2**20} MiB`)
    if (typeof process !== 'undefined')
    console.log(`${process.memoryUsage().rss / 2**20} MiB`)

    const query = (q) => {
    let pos = count / 2 | 0, delta = count / 4, res
    @@ -53,4 +54,4 @@ const search = (prefix) => {
    return end - start + 1
    }

    search('AA')
    console.log(search('Tst'))
  10. ChALkeR created this gist Jun 26, 2020.
    56 changes: 56 additions & 0 deletions array-10e6x100-search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,56 @@
    const count = 10e6
    const length = 100

    const letter = () => {
    const l = Math.random() * 52 | 0
    return String.fromCharCode(l < 26 ? l + 65 : l + 71)
    }

    const word = () => {
    const arr = []
    for (let i = 0; i < length; i++) arr.push(letter())
    return arr.join('')
    }

    const pool = []
    console.time('generate')
    for (let i = 0; i < count; i++) pool.push(word())
    console.timeEnd('generate')

    console.time('sort')
    pool.sort()
    console.timeEnd('sort')

    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 start = query((pos) => {
    if (pool[pos] < prefix) return +1
    if (pos - 1 < 0) return pool[pos].startsWith(prefix) ? 0 : -1
    if (pool[pos - 1] >= prefix) return -1
    return 0
    })
    const end = query((pos) => {
    if (pool[pos] >= prefix && !pool[pos].startsWith(prefix)) return -1
    if (pos + 1 >= count) return pool[pos].startsWith(prefix) ? 0 : +1
    if (pool[pos + 1] < prefix || pool[pos + 1].startsWith(prefix)) return +1
    return 0
    })
    if (start === null || end === null) return 0
    console.timeEnd('search')
    return end - start + 1
    }

    search('AA')