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

Which is faster Map or Set, Count or Find?
Автор -M1, история, 7 дней назад, По-английски

In the recent Div4 contest problem F: My submission1 using map + .find fails on TC 25 (TLE). My submission2 using set + .find fails on TC 33 (TLE). But when I used .count with set it barely passes in C++20 (submission) but gave TLE in C++17 as well as C++23. Why is it so?

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

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

I find this phenomenon intriguing as well. My solution 296722764 passed, even though it doesn't seem significantly different from the TLE-ed ones. Btw, I used contains instead of count or find.

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

set is faster than map because in the implementation of these data structure in Red-black Tree, set uses only key whereas map uses both key and value pair. Both count and find has same time complexity but when used with set or map, count is faster as it directly returns true or false as only one key is present, but if used with multiset count may be slower than find if count of that particular element is high.

Edit: And abt this problem, time complexity also differs by number of time .end() iterator is called when using find and comparing it with another iterator whereas when using count, .end() iterator is not required and compared just as boolean value.

→ Ответить
  • »
    »
    7 дней назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Tell me more about what you think the count() function does and how it is so much faster than find() (hint: the implementation of count is literally return find(v) == end() ? 0 : 1)

    → Ответить
    • »
      »
      »
      7 дней назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      GOING DEEPER

      find() is just implimentation of lower_bound

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

      That's what my doubt is, it makes sense that find would be better in case of multisets or vector

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

      As count() is implemented using find() internally, compiler optimizations make count() faster in practice. count() avoids iterator handling and simplifies the check to a boolean result, allowing compilers to optimize it more aggressively.

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

Seems to be a matter of whether you use int or long long as well. As $$$x$$$ isn't that large, using int is enough to pass on C++17 (though still taking a whopping 3.6s). Ever since that Div1+2 problem A incident I've been pretty mindful to these type optimizations

→ Ответить
  • »
    »
    7 дней назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Maybe that's the issue, will keep this in mind in future contests. Thnx :)

    → Ответить
»
7 дней назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In F .. my map solution was giving TLE , but unordered map passed with around 700ms .. (rare to see unordered_map solutions passing)

→ Ответить