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

map против unordered_map.
Автор timur_jalgasbaev, история, 4 недели назад, По-русски

Я думал что unordered_map быстрее чем map в cpp, но до этого случая..: Во вчерашнем соревнований Div3 в задаче D я использовал unordered_map для хранения элементов, думая что это будет быстрее, но кто-то взломал мой код, а моего друг который имел почти такой же код, но использовавший map вместо unordered_map, не смогли взломать. Почему моего кода взломали, ведь unordered_map быстрее чем просто map, не так ли? Я не смог достичь чёткого ответа этому вопросу. Так что прошу от уважаемого сообщества Codeforces, почему так вышло? Заранее спасибо, за ответ.

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

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

Auto comment: topic has been translated by timur_jalgasbaev (original revision, translated revision, compare)

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

unordered_map is basically O(1) for "random" inputs, but since the problemsetters/(people who make hacks) know that people will try using it, they can basically make an input that will "break" the unordered map and make it O(n) per access. Map on the other hand is always O(logn), and so its alot more safe to use.

→ Ответить
»
4 недели назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

I did the exact same thing. This article explains very well why the unordered_map fails and also discusses the solution to avoid such hacks in the future.

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

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

→ Ответить
»
4 недели назад, # |
← Rev. 4   Проголосовать: нравится -19 Проголосовать: не нравится

Using gp_hash_table<int,int>mp works better than unordered_map because in the worst case, gp_hash_table operates in O(1), while unordered_map can degrade to O(n).Therefore, gp_hash_table is a better choise than unordered_map. If you use gp_hash_table, you need to include the following headers:

#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
→ Ответить
  • »
    »
    4 недели назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    The article referenced above says it is even easier to hack than unordered_map.

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

    gp_hash_table can be hacked too.

    You can hack gp_hash_table by constructing a sequence $$$A$$$ that satisfies $$$A_i=65537i$$$.

    Then its time complexity will become $$$O(n)$$$.

    You can use this to prevent it from being hacked:

    struct myhash{
    static uint64_t rand(uint64_t x){
        x^=x<<13;
        x^=x>>7;
        return x^=x<<17;
    }
    size_t operator()(size_t x)const{
        static const uint64_t f_rand=chrono::steady_clock::now().time_since_epoch().count();
        return rand(x+f_rand);
    }
};
__gnu_pbds::gp_hash_table<size_t,size_t,myhash> hashtable;

    UPD: There is a typo in my code, so I fixed it.

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

    I see this for the first time, I haven’t even seen it in other people’s codes, I don’t think it’s optimal

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

Basically the unordered_map hack is that you put a lot of multiples of a special prime that'll make the unordered_map not being able to resize correctly. It'll put all of those numbers in a single "bucket" which is like a normal array, so searching in that array will take $$$O(n)$$$ time, thus causing the operation time to be $$$O(n)$$$. So your complexity goes up to $$$O(n^2)$$$ which is not what you want. To fix this problem you can use a custom hash function as described here, which will make the hash unpredictable so the hashes can't trigger the special prime.

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

You could us mp.reserve(1024); mp.max_load_factor(1); which will make the unordered_map almost as fast as map and faster than map in some cases. you could try resubmitting your code using these two functions

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

you could use mp.reserve(1024); mp.max_load_factor(1); which will make your unordered_map almost as fast as map and in some cases faster than map. you could try to resubmit the code using these two functions

→ Ответить