Блог пользователя Naithani

Автор Naithani, история, 4 года назад, По-английски

Hey everyone, I was solving this trie problem. At first, I was trying to solve this using std::unordered_map which causes TLE, but then, I tried using static array, and then it worked fine.

Solution with std::unordered_map: (link) https://pastebin.com/LtLQ47fk

Solution using static array: (link) https://pastebin.com/BUDPhxXk

Is there is any way to optimize the std::unordered_map?

Is there any mistake in the unordered_map solution?

Is there something wrong?

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

You should highlight that this is a binary trie, of course that an unordered map is going to have a huge time/memory constant factor

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But why? unordered_map is similar like an array, right?

    Or there is something different about binary Trie.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      Generally avoid using unordered containers because some tests may intentionally cause collisions and the complexity per operation can become $$$O(n)$$$.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Two main reasons:

      • Vectors of structs are allocated sequentially in memory. When your struct contains an unordered_map, the underlying storage for the map gets allocated elsewhere.

      • Unordered map needs to hash keys and index them into the underlying storage.

      The first one is probably the more important factor here.