Am I the only one bothered that he didn't first optimize the HashSet solution to O(N)? When sliding the window, you increase the counter for the new element, decrease the counter for leaving element, and update for each element how many have their counter set to 1. That makes a bit weaker the case for using popcount, since that actually is O(W/Wordsize), which happens to be O(1) in this case.
Thank you. I was wondering the same thing and I think the article is overfocusing on "cool bit tricks" while this simple approach works just fine.
A neat XOR trick
121–130 of 181 posts
Re: A neat XOR trick
#122Using a bitmap to track letters you've seen is a great idea. But the parity and counting gives me a headache. How about you start with a zero-size window at the start of the string, then iteratively try to grow it by moving the end forward until it's long enough, and if the character added would be a duplicate, moving the start forward until it's no longer a duplicate? Sort of inchworm-style movement.
I am not smart enough to write Rust, so here it is in Java:
private static int run(String input, int windowSize) {
int windowStart = 0; // start at the start
int windowEnd = 0; // the window is initially zero-size
int lettersSeen = 0; // a bitmap of letters we have seen
while (windowEnd - windowStart = input.length()) throw new IllegalArgumentException("No unique window found");
int letterToAdd = 1
This is not quite optimal in terms of bit operations - i mask the bitmap in the inner loop condition, but you could just test letterToRemove against letterToAdd and break if they're the same. I think that's a bit less readable though.Note that although this has two nested loops, they don't both independently range over the whole string, so this is not O(n^2). The outer loop moves windowEnd over the whole string, and the inner one moves windowStart over the whole string bit by bit. Each index visits each position in the string at most once.
Re: A neat XOR trick
#123I've seen this use of constants inside big O notation in leetcode and 'informal' discussions. Is it pedantic to say that O(NM) == O(N) if M is a constant (in this case since it's bound by 26)? Or is this the current and expected usage?
Re: A neat XOR trick
#124Earlier quoted context omitted.
>One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit. You can xor arrays of integers.
Right, but if the universe of possible characters grow much larger than the window size (as it does in many applications), we want a method that only pays in terms of window size, not universe size.
If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!
Re: A neat XOR trick
#125 mask = -1 > 1) & mask);
but with xor we can do it in one less instruction: mask = -1 > 1)) & mask) ^ x;Re: A neat XOR trick
#126Earlier quoted context omitted.
Sure, but now do 11 at a time with a similar algorithm (which was part 2 of the problem).
I've just submitted in order to see the second part, which just says "now look for 14 unique". I dont see the problem here, if you want a notation to express it, a macro for something like, 0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 1 != 0, 2, 3, 4, 5, 6, 7, ... is straightforward, and could be parameterised on the window size.
Re: A neat XOR trick
#127Earlier quoted context omitted.
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 exactl…
My 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.
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.
Re: A neat XOR trick
#128The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.
Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;) But otherwise, yes. I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and f…
Re: A neat XOR trick
#129Earlier quoted context omitted.
the 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.
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. 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…
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.
Re: A neat XOR trick
#130The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.
legend say that popcnt was the "NSA" instruction, was heavily used for cryptographic analysis and that was kept out of common instruction sets for a long time to give NSA an advantage. It is probably just a legend though.
The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC while he was designing the 6600 super and 'suggested' that if he included a popcnt instruction in the ISA, the NSA would certainly look favorably on purchasing some. He did and they did (quite a few). This story is also possibly apocryphal.