Discussion on: Solving Puzzles With High-Performance JavaScript

View post

Possible idea with the jewels thing:

var numJewelsInStones = function(J, S) {
    const jewels = new Uint8Array(8);
    for (let i = 0, l = J.length; i < l;) {
        const j = J.charCodeAt(i++) - 0x41;
        jewels[j >>> 3] |= 1 << (j & 7);
    }
    let myJewels = 0 >>> 0;
    for (let i = 0, l = S.length; i < l;) {
        const j = S.charCodeAt(i++) - 0x41;
        jewels[j >>> 3] & (1 << (j & 7)) && ++myJewels;
    }
    return myJewels;
};

This makes heavy use of CPU caching, so should be quite fast for longer strings.

ZaneHannanAU • May 23 '19 • Edited

Could also use A and B types

var numJewelsInStones = function(J, S) {
    let a = 0|0, b = 0|0, j = 0|0;
    for (let i = 0, l = J.length; i < l;) {
        j = J.charCodeAt(i++);
        if (j < 0x60) a |= 1 << (j - 0x41);
        else b |= 1 << (j - 0x61)
    }
    let myJewels = 0 >>> 0;
    for (let i = 0, l = S.length; i < l;) {
        j = S.charCodeAt(i++);
        if (j < 0x60) a & (1 << (j - 0x41)) && ++myJewels;
        else b & (1 << (j - 0x61)) && ++myJewels;
    }
    return myJewels;
};

This can be done entirely on the stack and registers, so avoids other possible slowdowns related to allocation. Only issue is that of shifting...

ZaneHannanAU • May 23 '19 • Edited

Another, even faster:

var numJewelsInStones = function(J, S) {
    if (!J || !S) return 0; // empty string, fast return
    let a = 0|0, b = 0|0, j = 0|0, i = J.length, l = S.length, myJewels = 0 >>> 0;
    do {
        j = J.charCodeAt(--i);
        if (j < 0x60) a |= 1 << (j - 0x41);
        else b |= 1 << (j - 0x61);
    } while (i);
    do {
        j = S.charCodeAt(--l);
        if (j < 0x60) a & (1 << (j - 0x41)) && ++myJewels;
        else b & (1 << (j - 0x61)) && ++myJewels;
    } while (l);
    return myJewels;
};

This is basically just the fast ASM.js compatible form I guess. Not too sure if it will work though...

Edit: leetcode.com/submissions/detail/23...

tl;dr not as fast

ZaneHannanAU • May 23 '19

A similar thing works perfectly fine in rust, though.

leetcode.com/submissions/detail/23...

impl Solution {
    pub fn num_jewels_in_stones(j: String, s: String) -> i32 {
        let mut m = 0u64;
        for i in j.bytes() {
            m |= 1 << (i - 0x41);
        }
        let mut w = 0i32;
        for i in s.bytes() {
            let g = 1 << (i - 0x41);
            if g & m != 0 { w += 1 };
        }
        w
    }
}

Andrew Healey • May 23 '19

These are all so cool! I’m going to have to pick through them later 👍

Theofanis Despoudis • Oct 22 '19

This is probably because all the optimisations you may do in JS land may be thrown to the bin once it touches native code. I Rust you have more control over the memory layout.