Mysterious story: TL 12 → TL 18 → OK

Revision en6, by Burunduk1, 2021-02-18 09:53:07

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++)

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.

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.


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);
Tags tl, optimization, c++


  Rev. Lang. By When Δ Comment
en6 English Burunduk1 2021-02-18 09:53:07 125
en5 English Burunduk1 2021-02-17 13:44:10 241 Tiny change: 'ing way:\n~~~~~\nm' -> 'ing way:\n\n\n~~~~~\nm'
en4 English Burunduk1 2021-02-17 13:22:33 229 Tiny change: 'his idea. \n[This co' -> 'his idea. <br>\n[This co'
en3 English Burunduk1 2021-02-17 13:17:51 427
en2 English Burunduk1 2021-02-17 13:11:20 261 Tiny change: 'x:g++)\n\nUPD: \n\n`rehash(' -> 'x:g++)\n\n**UPD:** <br>\n`rehash('
en1 English Burunduk1 2021-02-17 12:45:15 414 Initial revision (published)