Эффективный контейнер для бит

Question

У меня есть битовый массив, который может быть очень плотным в одних частях и очень редким в других. Массив может достигать 2 ** 32 бит. Я превращаю его в набор кортежей, содержащих смещение и длину, чтобы сделать его более эффективным для работы в памяти. Тем не менее, это иногда менее эффективно с такими вещами, как 10101010100011. Есть какие-нибудь идеи о хорошем способе хранения этого в памяти?

Answer 1

Если я правильно понимаю, вы используете кортежи (offset, length) для представления последовательностей в 1 бит? Если это так, лучшим подходом будет использование прогонов упакованных битовых полей. Для плотных областей вы получаете хороший эффективный массив, а в неплотных областях - подразумеваемые нули. Например, в C ++ представление может выглядеть следующим образом:

// The map key is the offset; the vector's length gives you the length
std::map<unsigned int, std::vector<uint32_t> >

Поиск будет состоять в том, чтобы найти ключ перед позицией бита и посмотреть, падает ли бит в его векторе. Если это так, используйте значение из вектора. В противном случае верните 0. Например:

typedef std::map<unsigned int, std::vector<uint32_t> > bitmap; // for convenience
typedef std::vector<uint32_t> bitfield; // also convenience

bool get_bit(const bitmap &bm, unsigned int idx) {
  unsigned int offset = idx / 32;
  bitmap::const_iterator it = bm.upper_bound(offset);

  // bm is the element /after/ the one we want
  if (it == bm.begin()) {
    // but it's the first, so we don't have the target element
    return false;
  }

  it--;

  // make offset be relative to this element start
  offset -= it.first;
  // does our bit fall within this element?
  if (offset >= it.second.size())
    return false; // nope

  unsigned long bf = it.second[offset];
  // extract the bit of interest
  return (bf & (1 << (offset % 32))) != 0;
}

Answer 2

Это помогло бы узнать больше. Под «очень разреженным / плотным» вы подразумеваете миллионы последовательных нулей / единиц или локальные (как локальные?) Пропорции 0, очень близкие к 0 или 1? Преобладает та или иная ценность? Существуют ли какие-либо шаблоны, которые могут сделать эффективное кодирование длин серий? Как вы будете использовать эту структуру данных? (Произвольный доступ? Какое распределение индексов доступа? К огромным частям никогда или очень редко обращаются?)

Я могу только догадываться, что вы не собираетесь случайным образом получать доступ и изменять все 4 миллиарда бит со скоростью миллиардов бит в секунду. Если он не является феноменально разреженным / плотным на локальном уровне (например, любые миллионы последовательных битов, вероятно, будут одинаковыми, за исключением 5 или 10 бит) или полон крупномасштабных повторений или шаблонов, я догадываюсь, что выбор структуры данных зависит больше о том, как используется массив, чем о характере данных.

Answer 3

Сколько из них вы собираетесь хранить в памяти одновременно?

Насколько я вижу, 2 ** 32 бита = 512 Мб, только половина гигабайта, что в наши дни не очень много памяти. У вас есть что-нибудь лучше?

Предполагая, что на вашем сервере достаточно оперативной памяти, выделите все это при запуске, а затем сохраните его в памяти, поток обработки сети может выполнять всего несколько инструкций в постоянном времени - он должен справляться с любой рабочей нагрузкой.

Answer 4

Проверьте исходный код бизона . Посмотрите на реализацию бисета. Он предоставляет несколько разновидностей реализаций для работы с битовыми массивами различной плотности.

Answer 5

Как структурировать вещи, будет зависеть от того, какие у вас данные. Для представления больших объемов данных вам понадобятся длинные нули или единицы. Это избавило бы от необходимости представлять его заново. Если это не так, и у вас примерно одинаковое количество единиц и нулей, вам лучше использовать всю память.

Это может помочь воспринимать это как проблему сжатия. Чтобы сжатие было эффективным, должен быть шаблон (или ограниченный набор элементов, используемых из всего пространства) и неравномерное распределение, чтобы сжатие работало. Если все элементы используются и распределены равномерно, сжатие сделать сложно или может занять больше места, чем фактические данные.

Если есть только серии нулей и единиц (более одного), использование смещения и длины может иметь некоторый смысл. Если есть противоречивые прогоны, вы можете просто скопировать биты в виде битового массива, где у вас есть смещение, длина и значения.

Насколько это эффективно, зависит от того, есть ли у вас большие пробеги единиц или нулей. Вы должны быть осторожны, чтобы убедиться, что вы не используете больше памяти для повторного представления вашей памяти, а просто используете саму память (т.е. вы используете больше памяти для представления памяти, чем просто помещаете ее в память).