Блог пользователя Ahnaf.Shahriar.Asif

std::bitset vs manual bitmask ? which is better ?

Автор Ahnaf.Shahriar.Asif, история, 5 лет назад, По-английски

Recently, I learned Bitmask DP and used only a variable to see if some block was visited or not. But now I want to do it using std::bitset. Will it be more or less efficient than the first one ? If yes or no, why ? I'm just confused. I think bitset should be fine. and I want to use it because it is easy to use.What's your opinion ? thanks in advance.

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

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

quite obviously, using a primitive data type like long will be more efficient. But the problem is, what if you want to represent a bitmask that has more than 64 bits?

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

    :( . Yah . I think it is not possible using bitset :'(

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

    quite obviously, using a primitive data type like long will be more efficient.

    Actually gcc's standard lib implementation is specialised for short bitset and uses one long instead of array of longs, so they may be close to the same (but of course, it may still be not true, I have not measured that)

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

I think int is easier to use for bitmask dp because it is easier to store and loop through all possible states. The main use for bitset I have seen is when you have an O(n2) dp solution and are looking for an extra speed boost to squeeze it in the time limit. Definitely a cool trick that makes problem setters sad/apologetic when it works.

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

If an integer has enough bits it will most likely be at least as fast as a bitset. If you need more bits than that for a bitmask DP it's probably not going to work out anyway unless you're doing memoization where only a small number of states are actually needed. Bitsets are useful for quickly performing operations on a large number of bits, such as logical operations, counting set bits, and bitshifting. As far as I know they aren't very useful for bitmask DPs.

→ Ответить