3 ms·

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, de

by mihaic 4y ago

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.

DannyBee 4y ago
You don't even have to do this. If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)
- TYMorningCoffee 4y ago
  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)
  - DannyBee 4y ago
    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 how to do this. I already got caught out once by trying to code it too fast so not gonna do it ;)
    - mateo411 4y ago
      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
      - krackers 4y ago
        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.
        mateo411 4y ago
        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.
kevinwang 4y ago
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.
- SquareWheel 4y ago
  Without the cool bit trick, would it be worth publishing the article at all? I found it a novel approach to explore.
mpawelski 4y ago
You are right. The algorithm you described is very similar to this XOR one. However, I did some benchmarks[0] and non-XOR version was 40% slower to XOR version when compiled with target-cpu=native. Unfortunately, without `target-cpu=native` the xor version was 40% slower and plain old arrays won! [0]: https://github.com/mpawelski/adventofcode2022_day06/blob/master/benches/bench_day06.rs https://github.com/mpawelski/adventofcode2022_day06/blob/mas...

by mihaic 4y ago

DannyBee 4y ago

You don't even have to do this. If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)

TYMorningCoffee 4y ago
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)
- DannyBee 4y ago
  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 how to do this. I already got caught out once by trying to code it too fast so not gonna do it ;)
  - mateo411 4y ago
    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
    - krackers 4y ago
      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.
      - mateo411 4y ago
        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.

kevinwang 4y ago

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.

SquareWheel 4y ago
Without the cool bit trick, would it be worth publishing the article at all? I found it a novel approach to explore.

mpawelski 4y ago

You are right. The algorithm you described is very similar to this XOR one. However, I did some benchmarks[0] and non-XOR version was 40% slower to XOR version when compiled with target-cpu=native. Unfortunately, without `target-cpu=native` the xor version was 40% slower and plain old arrays won! [0]: https://github.com/mpawelski/adventofcode2022_day06/blob/master/benches/bench_day06.rs https://github.com/mpawelski/adventofcode2022_day06/blob/mas...