Burunduk1's blog

By Burunduk1, history, 4 years ago, In English

TL 12 107676717 -- unordered_map<int, int> cnt (TL = 2s)
TL 18 107676732 -- unordered_map<int, int> cnt(n) (works 46ms on 12th test)
OK 107676952 -- sort (works 77ms and 66ms on 12th and 18th tests)

What's going on?) I have no access to tests and can not repeat this effect locally (both windows:g++, linux:g++)

UPD:
107679200 rehash(100 + gen() % 10000) gives OK in 670 ms, which is still too slow
107679288 rehash(100 + gen() % 10000) + reserve gives OK in 100 ms, which is strange but acceptable.

PS:
This comment says "anti-hash test". I also have only this idea.
This comment gives more precise answer.
In future of course i will just use my own hash-table with no such faults.

PPS:

Both constructor(x) and rehash(x) seems to set bucket_count to minimal prime $$$\ge$$$ x, so we can still use unordered_map in one of two following ways:

mt19937 gen(time(NULL));
unordered_map<int, int> cnt;
cnt.rehash(n + gen() % n);
mt19937 gen(time(NULL));
unordered_map<int, int> cnt(n + gen() % n);
  • Vote: I like it
  • +38
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I guess the reason is the same as the submissions shared on this blog and this blog?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Locally I can't repeat this either, but if you run this code in the custom invocation, you can see the number of buckets for specific $$$n$$$. And since std::hash for integers is an identity function, it's not hard to create tests when all values hash(k) % bucket_count are the same.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    std::hash for integers is an identity function

    Wow! So easy. Thank you.