4 ms·
OR wouldn't work with a sliding window since it can't be inverted? This should work: init bit mask and count of bits to 0 for each new char: old = bit
by rep_lodsb 4y ago
OR wouldn't work with a sliding window since it can't be inverted?
This should work:
init bit mask and count of bits to 0
for each new char:
old = bit mask
bit mask = bit mask XOR old char
if bitmask > old then count++ else count--
old = bit mask
bit mask = bit mask XOR new char
if bitmask > old then count++ else count--
if count == window length: return match
The idea is that each XOR will always set or clear exactly one bit, so we can maintain a count of set bits.
But if there is a POPCNT instruction it would probably be faster to use it.
- DannyBee 4y agoMy guess is, it’s still faster to just check whether hashset.insert returns false. Since most windows are not unique early exit will likely beat faster processing.
- dahfizz 4y agoI doubt the hashmap would beat the XOR method from the article. Hashmaps means allocations, and it means hashing. Hashing is going to be at least as much work as XORing a couple values in the mask. Hashmaps also means chasing pointers all over memory and ruining your cache. You can add an early return to the OPs XOR method by just checking if the char is already in the bit mask. This will be faster if the word size is large.
- DannyBee 4y agothe domain/range is fixed, so you don't have to allocate, actually, because you can have a fixed sized table and perfect hash :) That said, I agree you can make the bit munging faster in the end, i'm just saying i don't think the speed up is anywhere near the improvement from early-exiting.
- rep_lodsb 4y agoEven if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop. If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.
- dahfizz 4y ago> Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. This is known as a perfect hash[1]. knowing that you will never have collisions does allow for a faster implementation. The hash map can be backed by an array which will never need to be resized, and you don't have to fiddle with linked lists to chain collisions. You're correct though, that this is something you will have to implement yourself. Library hashmaps are going to trade performance for general usefulness. [1] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function
- gpderetta 4y agoFor small windows it is possible that an early exit might be counterproductive as it exercises the branch predictor. One would have to test ti see where the cutoff is, but often doing extra work is faster. Edit: but this is discussed elsethread. A fixed size run also helps with vectorization.
- meindnoch 4y agoYou can combine the two XORs: new_mask = old_mask XOR old_char XOR new_char count += signum(new_mask - old_mask) Where signum(x) = (x > 0) - (x < 0)