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

Замена логического массива массивом множеств размерностью в 8 раз меньше
Автор Jovfer, 13 лет назад, По-русски

Тип bool (boolean итп в различных языках программирования) требует по сути 8 бит на одно значение. Соответственно и время работы с таким массивом неоправданно возрастает. В делфи проблема решалась например так type MyBoolean = array [0 .. (maxn div 256)] of set of byte; с последующей проверкой (i mod 256) in (MyBoolVAR[i div 256]) . Все это работает за приемлемое время и расходует нужный объем памяти. Вопрос в следующем: как реализовать что-либо подобное в с/с++ ? Пробовал bitset, set, просто работал с побитовыми сдвигами над unsigned char. Добивался желаемого расхода памяти (~ 1 бит / логическое значение), но время работы оставляло желать лучшего...

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

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

vector < bool >

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

    Та еще сокрость у него.

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

      Мне хватало всегда. На spoj.pl код вообще начинает работать быстрее если bool-массивы заменить на vector < bool > . Если тестят под виндой может он и тормозит, я не знаю.

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

Можно примерно так же как и делали в дельфи:

const int MAXN = 1000000;
unsigned int h[(MAXN>>5)+1];

bool is_set(int x){
	return h[x>>5]&(1<<(x&31));
}

void set(int x){
	h[x>>5]|=1<<(x&31);
}
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да делал так уже. (ну с точностью до выбора базового типа). Время не понравилось. + вопрос с обнулением висит. Обнулять полностью вручную — опять же время.

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

      А как вы обнуляеете массив булов? Тоже самое, нет?

      memset'ом можно к слову.

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

        Пользовался тем что при описании и ручном задании первых элементов, остальные (для которых нет явного указания значения) обнуляются. bool a[n]={0}; Про мемсет в курсе). Хотя что из этих двух способов быстрее не выяснял — в самом начале изучения языка сложилось впечатление что по времени работы варианты равнозначны.

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

      Почему-то я не верю, что это медленно. Ну не может это работать медленно — быстрее же просто нельзя

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

        Пожалуй с таким аргументом сложно спорить.

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

      ну с точностью до выбора базового типа

      Базовый тип в этом вопросе важен. Например, если использовать unsigned char, полученный код будет примерно на 10% медленее.

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

Какзалось бы битсет работает за относительно адекватное время, правда размер там надо задать до компиляции

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

Оффтоп: А разве в паскале set of byte занимает не 256 бит? Тогда ведь можно div 256 сразу делать.

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

    спасибо за поправку, конечно же div / mod 256. ну или сдвиги на 8.

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

Я правильно понимаю что выбирать приходится только между bitset, vector<bool> и ручной работой с побитовыми операциями? Если так, был бы весьма благодарен за сравнение вариантов.

→ Ответить