101–110 of 181 posts
Then a friend solved it with regular expressions, but I found a sicker regex. After all, that's what regexes are about.
https://mobile.twitter.com/erikcorry/status/1600524753596456...
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. This could happen if we are instead interested in a window of unique words in a long document. Amazingly there is still a solution based on XOR! It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things. Basically each word is hashed to three…
You can xor arrays of integers.
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. This could happen if we are instead interested in a window of unique words in a long document. Amazingly there is still a solution based on XOR! It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things. Basically each word is hashed to three…
This article’s technique can definitely expand into dynamically allocated bitsets.
Edit - actually it should be possible to update the count incrementally, so it should still be O(N) I think.
W cannot be larger than the size of the character set, so even the first algorithm runs in O(N) time. It's a cool trick, but it didn't make the algorithm asymptotically more efficient as the OP suggests.
You could imagine a much larger character set though. For example you might be interested in a sliding window of unique words instead.
Reminds me of the problem “find the only missing number in a scrambled list of 1..n”. You can get an “O(n)” solution using xor, but once bit size becomes a concern, there are less hacky solutions that are just as fast.
Ie, it's undeniable that the final program works much faster, but the article should really be called "a smarter memoization trick."
int main(void) {
char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg";
for (
c = data;
!((c[1] != c[0]) &&
((c[2] != c[1]) && (c[2] != c[0])) &&
((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0])));
c++
);
printf("%ld", c-data+4);
}Earlier quoted context omitted.
Bit operations are fast, branches are slow.
Well, yes, but most of these branches can be if-converted into conditional moves anyway if you want. So they are data dependencies and not control ones. There are still some control ones. Beyond that, let me be super clear: Imagine the following six versions: 1. One window at a time processing. No early exit, no bit munging. 2. One window at a time processing. No early exit, bit munging. 3. One window at a time proce…
You could roll your own perfect hash, but you would end up with a solution that looks almost identical to TFA. If you use a stdlib hash, you are going to be chasing pointers all over memory to do a single insert / lookup. De-referencing a single pointer not in cache costs 50 - 100 clock cycles on a modern system. By the time you do one insert, TFA will have XOR'd at least 32 chars into its bit mask. And your cache won't be as nice as in TFA, slowing you down even more.
Given the two scenarios: 1) bit munging, no early return 2) hash lookup, early return
I would guess scenario 1 wins until word size gets above ~256. And obviously, we can add an early return to scenario 1 to make it unquestionably the fastest.
I may be missing something, but isnt the obvious answer just to scan-and-compare 4 chars/time ? (Noting that != is XOR). int main(void) { char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg"; for ( c = data; !((c[1] != c[0]) && ((c[2] != c[1]) && (c[2] != c[0])) && ((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0]))); c++ ); printf("%ld", c-data+4); }
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. This could happen if we are instead interested in a window of unique words in a long document. Amazingly there is still a solution based on XOR! It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things. Basically each word is hashed to three…
>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.
Something about seeing fun bit tricks solving higher level problems is exciting. As someone who writes higher level software in general using golang/rust/python to solve "boring business" problems, seeing someone using XORs to accomplish something feels like leaving my house and going camping for the weekend.