Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A neat XOR trick

mattkeeter.com

Post reply on HN
Print view View original

161–170 of 181 posts

Re: A neat XOR trick

#161

Post by krackers »

jvanderbot wrote: post #85

This is also essentially the trick applied in Kadane's Algorithm for the "maximum contiguous sum" search, albeit using masks to "undo" the set-of-characters check whereas Kadane's uses subtraction to "undo" the addition for maximum sum check. https://www.geeksforgeeks.org/largest-sum-contiguous-subarra...

Kadane's algorithm (whose name sounds cooler than what it does) doesn't do any masks, it basically just keeps extending the window until the sum becomes negative at which point it starts a new window.

Re: A neat XOR trick

#162

Post by twic »

nerpderp82 wrote: post #150
twic wrote: post #122

This seems a bit overcomplicated to me. Using 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…

I asked ChatGPT for a Rust port, https://play.rust-lang.org/?version=stable&mode=debug&editio... I had to make zero changes, it appears to work.

Although input.chars().nth() is not good - because of how strings work in Rust, that has to iterate over the string, rather than indexing directly, so O(n) rather than O(1). I think the idiomatic efficient translation would be to use a CharIndices iterator to track each end of the window.

Re: A neat XOR trick

#163

Post by thomasahle »

bsza wrote: post #136
thomasahle wrote: post #111

Earlier quoted context omitted.

"Bit tricks" are worth a factor `log n`. Let me explain: If you have an array of `n` integers in {0,1}, and you want to count the number of 1s, you need `n` time. But if you have an array of `n` bits, with bit level operations you can do `n/W` time, where `W` is your word size. We often have W=32, 64 or 256 on some architectures, but you may still argue it's just a constant. The thing is that we usually saw you have…

You're using n as a parameter of the machine's specs, which is a big no-no. You can't just come up with a bigger machine for each consecutive value of n. If that were allowed, all algorithms would trivially be O(1). We usually assume the pointer size to be infinite (e.g. RAM machine), to avoid having to deal with access time. But if we don't, then it must be a constant size (and we have to adjust the big O formulas a…

Perhaps we are both right. I usually think of the Word RAM Model in which W is assumed to be at least logn. See https://en.m.wikipedia.org/wiki/Word_RAM#Model

This is a nice model because you don't have to assume things like "infinite pointer sizes", and because the algorithms that work well in practice (such as using bit tricks) also work well in the theory.

If you don't work in the word ram model you also wouldn't be able to do things like hash maps with constant time queries, since that requires a hash function which can't be computed in O(1) bit operations.

Re: A neat XOR trick

#164

Post by mateo411 »

krackers wrote: post #160
mateo411 wrote: post #158

Earlier quoted context omitted.

I think you can use a queue of size w. Something like this... this is psuedo code. You iterate through the string once. You pop an element off of the queue at most once. In this implementation you might add it to the queue twice. def find_uniq_window(long_string, w): queue = Queue() hash_set = Hashset() for char in long_string: if queue.size() == w: old_char = queue.pop() hash_set.remove(old_char) queue.push(char) if…

Instead of a queue, you could just use two indices/pointers to the start and end of the current window. Also I think on `char in hash_set` you'd want to advance the start of the window until uniqueness is restored, rather than moving start to the end. E.g. if the string is "abac", when you get to the second "a", instead of restarting the window at the second "a" you want to instead move the start to "b". You might ev…

Yes, you are right about advancing the start of the window until uniqueness is restored. So, basically just advance it by 1.

You could definitely use two indexes instead of a queue, and using indexes over an array will be faster than using a queue.

Re: A neat XOR trick

#165

Post by krackers »

dukoid wrote: post #53

FTR: This can be done with "only" two loops (opposed to the "naive" 3 in the article) -- without any extra data structures. It's sufficient to keep track of how many characters have been unique so far. For each "new" character, check whether it's different from all of them. If so, increase count. Otherwise, reset count to the distance to the match. def main(): count = 1 for i in range(1, len(SIGNAL)): for j in range(…

I think you can also speed this up by incrementing i to the next candidate window end (increment by window_length - count). I.e. given "abcdefggqwertyu", if your previous window was "[abcdefg]" and you see that "g" conflicted so you reset count to 0, the next possible window is "[gqwerty]". So you don't have go through the intermediate windows like "[efgqgq]" because you know that count can never be 4 within there.

Edit: I think your solution already effectively does this, it's just that because you maintain invariant that the window always contains unique chars to avoid any additional datastructure, once the window start gets reset to "[g]" it needs to build back up the intermediate state one char a time to works it way back up to [gqwerty]. So the best case is approximately linear if count gets reset often, worst case is O(NW). The method I was thinking of directly tests the next window starting from its endpoint backwards, to do this you need a hashet. I think that would achieve on best case O(N/W) effectively sublinear, worst case is still O(NW) though.

Re: A neat XOR trick

#166

Post by dmurray »

WJW wrote: post #21
n4r9 wrote: post #6

Earlier quoted context omitted.

Arguably day 11 part 2 is such a "lanternfish" problem, although it essentially tells you to watch out for it.

I definitely ran into that. I read "impractically large number" and thought "well the language I'm using has arbitrary size integers so I should be fine". So, I changed the code from 20 iterations to 10000 iterations and suddenly all 16 GB of my RAM was filled with Santa's worry counters.

Worse, I ported my solution to use BigInt and then found that was neither necessary nor sufficient.

Re: A neat XOR trick

#167

Post by ribit »

opk wrote: post #8
ribit wrote: post #5

One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)

I assume the author is realigning to get only one bit for each letter. This relies on having an alphabet of 26 characters where 26 is less than the 32 available in a u32. In most real-world problems, you need to allow for the full ASCII or Unicode range and this wouldn't be possible. Using codepoints directly, there is overlap. 'f' ^ 'd' will give you the same bit pattern as 'b'. You could keep an xor value for each…

You are right. Total brainfart on my side. I skimmed the article too fast and completely misunderstood the approach.

Re: A neat XOR trick

#168

Post by gpderetta »

_a_a_a_ wrote: post #142
kjs3 wrote: post #130

Earlier quoted context omitted.

The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers. The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC wh…

> The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing Ok. Why?????????????? @gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.

Oh right! Hacker's Delight might be where I read the story, and likely I misremember the details.

Re: A neat XOR trick

#169

Post by bsza »

thomasahle wrote: post #163
bsza wrote: post #136

Earlier quoted context omitted.

You're using n as a parameter of the machine's specs, which is a big no-no. You can't just come up with a bigger machine for each consecutive value of n. If that were allowed, all algorithms would trivially be O(1). We usually assume the pointer size to be infinite (e.g. RAM machine), to avoid having to deal with access time. But if we don't, then it must be a constant size (and we have to adjust the big O formulas a…

Perhaps we are both right. I usually think of the Word RAM Model in which W is assumed to be at least logn. See https://en.m.wikipedia.org/wiki/Word_RAM#Model This is a nice model because you don't have to assume things like "infinite pointer sizes", and because the algorithms that work well in practice (such as using bit tricks) also work well in the theory. If you don't work in the word ram model you also wouldn't…

We're still at O(N * W) time. It might be possible to implement xor using only +, - and bit shifts (though I'm not seeing any obvious way to do so), but count_ones stays a bottleneck; I'm pretty sure you can't do that in O(1) even on a word RAM machine.

Not to mention, a machine where addition takes O(1) time is a massive cheat - at least definitely not what most people have in mind when talking about computational complexity. AFAIK, O(...) usually means "on a classic RAM machine" unless otherwise stated. With hash maps/sets, it really depends on what is expected to grow. Bigger input size doesn't always mean bigger keys.

Post reply on HN