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

151–160 of 181 posts

Re: A neat XOR trick

#151

Post by deathanatos »

jstanley wrote: post #126
mjburgess wrote: post #113

Earlier quoted context omitted.

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.

That's fine, but it's O(n) in the window size whereas the xor trick is O(1).

Part 1 and part 2 are the same, only the window size varies. But within a part, the window size is constant. For most, it should have just meant that, if you hard-coded the window size during part 1, that you need to make it a parameter.

But for both parts, the naïve solution should be O(N * W), where N is the input length, and W is the window size. Like a sibling says, since within a part the window size is fixed, it is acceptable to call it O(N).

Edit: ah, I see what his solution is doing. It is correct. I need to adjust my definition of naïve, I guess. His is O(N * W²). You can still reasonably consider W² constant, though, I think. And he gets to what I would call the "naïve" solution.

(Previously.) ~The "naïve solution" in the OP does not appear to be correct. Or at least, if it does work,~ it appears to do far more computation that it needs to.

The "xor trick" is O(N), too. (There cannot be a more efficient solution, as the entire input must be considered in the worst case. TFA is correct that its final form omits W, though.)

Re: A neat XOR trick

#152

Post by Vt71fcAqt7 »

moloch-hai wrote: post #147
snvzz wrote: post #55

Earlier quoted context omitted.

>RISC-V Doesn't B have a POPCNT? B is mandatory in RVA22.

Can you buy any RISC-V embodiment that implements such an instruction? It seems to be extremely optional.

B is pretty recent, but Sifive p650 will have it

https://www.sifive.com/cores/performance-p650

Heres another:

https://www.andestech.com/en/2022/12/08/andes-technology-unv...

I expect all future Linux cores to have it

Re: A neat XOR trick

#153

Post by [deleted] »

moloch-hai wrote: post #17

The 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.

[deleted]

Re: A neat XOR trick

#154

Post by deathanatos »

mjburgess wrote: post #143
jstanley wrote: post #126

Earlier quoted context omitted.

That's fine, but it's O(n) in the window size whereas the xor trick is O(1).

The window size is always constant in the problem, so it's O(1) There shouldnt be a loop over the window size in solutions to this (particular) problem

TFA's implementation is using a loop over the window size to compare each character to all the other characters, to see if they're unique. So, the article's O(N * W²) is correct, but I agree, the window size is fixed and small; it's fair to boil it down to just O(N).

(I never even considered doing a for loop like that to determine if the window is unique; I just histogram the window, and then check if all the values in the histogram are 1. If yes, unique. If I had been cleverer, I wouldn't rebuild the histogram as the window shifts, but there was no need for that. This is essentially the next solution TFA presents.)

Re: A neat XOR trick

#155

Post by js2 »

adrian_b wrote: post #28
moloch-hai wrote: post #17

The 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.

It is good to remember that the instruction POPCNT was introduced for the first time in the instruction set of a computer by Alan Turing, already in 1949, in Ferranti Mark I (as "sideways add"). Unfortunately few other computers have included it before Cray 1, which made it well known, under the current name.

Sideways add makes a bit of sense for the name of this operation. But I can't figure out why Cray named it "population count." It just seems odd to refer to the set bits as part of a population that you're counting.

Re: A neat XOR trick

#156

Post by deathanatos »

mjburgess wrote: post #106

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); }

If you consider W the window size, and N the input size, this is still O(N * W²), as TFA states. (TFA's implementation is generic over W, yours is constant and essentially -funroll'd in place. But it's the same, for big-O; as you mention in your reply later, you could even make a macro, generic over W.)

Re: A neat XOR trick

#157

Post by deathanatos »

jhoechtl wrote: post #20

> There's no moral to the story, other than "xor is cool" The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.

…a simple histogram (the second proposed solution in TFA) runs "instantly", for both parts.

Part of the meta-game to AoC is knowing that you can limit your answer to only the requirements in the combination of the question and input given. If the naive solution runs fast enough, and is vastly quicker to implement, that's the one you want.

Re: A neat XOR trick

#158

Post by mateo411 »

DannyBee wrote: post #59
TYMorningCoffee wrote: post #54

Earlier quoted context omitted.

I think he meant to use a hash map plus a numOfOnes counter instead of hash set. With a hash map, you don't need to build the entire window every loop. It's only a constant amount of work per iteration, achieving O(N)

Yes. You can slide a hash map and a counter, as we went through below. You can also replace the hash map with a bitmask to store the set. You actually don't need any extra anything at all if you want, as you can just keep a single count because you don't need to look back at old windows, and can keep moving forward to the last non-unique point, making it O(N). I'm sure this being HN, someone will come along and post…

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 char not in hash_set and queue.size() == w:
            # success
            return queue
        if char in hash_set:
            #empty the queue and hash set and start over
            queue = Queue()
            hash_set = HashSet()   
            queue.push(char)
            hash_set.add(char)
  
    # We never found the window of unique characters, so return false
    return False

Re: A neat XOR trick

#159

Post by dubya »

moloch-hai wrote: post #17

The 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.

I never think of POPCNT because it's not a language primitive in any languages I use.

I would do it by storing the product of the counts; divide by the outgoing count before decrementing, multiply by the incoming count after incrementing. If the product is one they're all unique. Scaling should be comparable to POPCNT.

Re: A neat XOR trick

#160

Post by krackers »

mateo411 wrote: post #158
DannyBee wrote: post #59

Earlier quoted context omitted.

Yes. You can slide a hash map and a counter, as we went through below. You can also replace the hash map with a bitmask to store the set. You actually don't need any extra anything at all if you want, as you can just keep a single count because you don't need to look back at old windows, and can keep moving forward to the last non-unique point, making it O(N). I'm sure this being HN, someone will come along and post…

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 even be able to do something boyer-moore-esque if the hashset is instead a hashmap of chars to index. Then you can directly advance your window by how far in the mismatch is, which probably won't affect asymptotic complexity since you still need to remove elements but allows you to do it in bulk rather than one at a time.

Post reply on HN