6 ms·

That's not really a fuller explaination.

• roel_v 7y ago
  What more is there to explain? How is it not immediately obvious that the GP's approach is inferior the the OP's?
  • ww520 7y ago
    It really is not obvious how OP's approach is faster than GP's approach. OP's approach is by sorting which has complexity of O(m * N * logN) where m is the average key length and N is the size of the array. GP's approach with hash lookup has a complexity of O(m * N) where m is the average key length and N is the size of the array. The extra logN term makes OP's approach slower.
    • magicalhippo 7y ago
      Of course, for low values of N the constants dropped from the big-O notation start to matter. For very small values of N and a random-access input, even an O(N^2) approach may be optimal (for each input element, check for equality against previous elements of the input, output if no hit).
      • ww520 7y ago
        Well, when N is small, any complexity analysis is moot.
        • magicalhippo 7y ago
          Yes, but it's easy to forget and still apply it blindly in regimes where it's not really applicable anymore.
    • KirinDave 7y ago
      Many hash tables use tree structures rather than actual key hashing because it turns out that this is usually faster on modern machines. So many hash tables are technically O(n log n) for some high log factor like 32. I've posted what I think is the optimal solution and the research behind it above, if you're curious how to hit O(n) time without brutal constants.
      • ww520 7y ago
        Since the array size is known ahead of time, it's easy to initialize a hash table with an optimal capacity. No need to use fancy tree structure.
        • KirinDave 7y ago
          The size of the table isn't the trick. It's the perfect hash function that you want. If you have that then you've already solved the problem at hand.