4 ms·

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 asymp

by bsza 4y ago

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.

deleted 4y ago
[deleted]
TreeRingCounter 4y ago
thomasahle 4y ago
You could imagine a much larger character set though. For example you might be interested in a sliding window of unique words instead.
- bsza 4y ago
  Yes, but then the last algorithm runs in the same time as the one before it. Using xor here really only gives you a constant factor improvement (which is still nice!). 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.
  - thomasahle 4y ago
    "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 random access to all of your input data in constant time. But if your input size is `n`, your pointer size must be `log n`. So for standard algorithm analysis to work, you need to allow a word size of at least `log n`.
    - bsza 4y ago
      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 accordingly). In neither of those cases do you get free arbitrary length xor operations. Just like you don't get e.g. free arbitrary length multiplications either. One nice property of xor, however, is that you can parallelize the heck out of it. So you can get arbitrary constant factor improvements by adding a bunch of CPUs.
      - thomasahle 4y ago
        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 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.
        bsza 4y ago
        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.
        4y ago

by bsza 4y ago

deleted 4y ago

[deleted]

TreeRingCounter 4y ago

thomasahle 4y ago

You could imagine a much larger character set though. For example you might be interested in a sliding window of unique words instead.

bsza 4y ago
Yes, but then the last algorithm runs in the same time as the one before it. Using xor here really only gives you a constant factor improvement (which is still nice!). 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.
- thomasahle 4y ago
  "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 random access to all of your input data in constant time. But if your input size is `n`, your pointer size must be `log n`. So for standard algorithm analysis to work, you need to allow a word size of at least `log n`.
  - bsza 4y ago
    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 accordingly). In neither of those cases do you get free arbitrary length xor operations. Just like you don't get e.g. free arbitrary length multiplications either. One nice property of xor, however, is that you can parallelize the heck out of it. So you can get arbitrary constant factor improvements by adding a bunch of CPUs.
    - thomasahle 4y ago
      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 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.
      - bsza 4y ago
        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.
        4y ago