Самый быстрый способ сравнить битовые наборы (<оператор на битовых наборах)?
Каков наиболее оптимизированный способ реализации < оператор для std::bitset соответствует сравнению целочисленного представления без знака (оно должно работать для наборов битов more than 64 bits)
Тривиальная реализация будет:
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
for (int i = N-1; i >= 0; i--) {
if (x[i] && !y[i]) return false;
if (!x[i] && y[i]) return true;
}
return false;
}
Когда я говорю "наиболее оптимизированный способ", я ищу реализации, использующие побитовые операции и приемы метапрограммирования (и тому подобное).
РЕДАКТИРОВАТЬ: Я думаю, что я нашел хитрость: метапрограммирование шаблонов для рекурсии во время компиляции и правильного сдвига битов, чтобы сравнивать наборы битов как несколько длинных целых чисел без знака. Но нет четкого представления о том, как это сделать...
9 ответов
Очевидная оптимизация будет
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
for (int i = N-1; i >= 0; i--) {
if (x[i] ^ y[i]) return y[i];
}
return false;
}
Кроме этого, должно быть совершенно невозможно использовать большее количество битов на тест, поскольку не существует стандартного способа доступа к ним. Вы могли бы оценить x.to_string() < y.to_string() и надеюсь на оба to_string() и сравнение строк должно быть оптимизировано лучше, чем побитовый доступ к bitset, но это длинный выстрел.
Если вы готовы принять решение при изменении набора битов STL, вы можете использовать
template<int n>
bool compare(bitset<n>& l, bitset<n>& r){
if(n > 64){
typedef array<long, (n/64)> AsArray;
return *reinterpret_cast<AsArray*>(&l)
< *reinterpret_cast<AsArray*>(&r);
}//else
return l.to_ulong() < r.to_ulong();
}
компилятор выбрасывает ненужную ветвь
Я только что посмотрел на исходный код, но, к сожалению (если, надеюсь, я не ошибаюсь), они, кажется, не дают вам доступ на месте к const & unsigned long для конкретного блока битов. Если они это сделали, то вы можете выполнить рекурсию шаблона и эффективно сравнить каждый unsigned long а не каждый бит без знака.
В конце концов, если A < Bто не только должен каждый из самых значимых битов a <= bтакже каждый из наиболее значимых блоков A[i] <= B[i],
Ненавижу это говорить, но я бы, наверное, свернул свой собственный, используя рекурсию на C++11 std::array, Если у вас есть доступ к блокам, то вы можете сделать шаблонную рекурсивную функцию, чтобы сделать это довольно легко (и, как я уверен, вы знаете, так как вы запрашиваете метапрограммирование), дайте компилятору отличный шанс для оптимизации.
В общем, не очень хороший ответ, но я бы так и сделал.
Отличный вопрос, кстати.
===========
РЕДАКТИРОВАТЬ
Для этого нужно использовать три подхода: тот, который имеет самые последние отзывы, стратегию блоков, которую я описал, и шаблонный рекурсивный вариант. Я заполняю вектор битовыми наборами, а затем повторно сортирую, используя указанный функтор компаратора.
Счастливого взлома!
Вывод на мой компьютер:
Runtimes:
скомпилированный g++ -std= C++11 -Wall -g test.cpp
std::bitset 4530000 (6000000 оригинал в OP)
Блок за блоком 900000
Шаблон рекурсивный 730000
скомпилированный g++ -std= C++11 -Wall -g -O3 test.cpp
Runtimes:
std::bitset 700000 (740000 оригинал в OP)
Блок за блоком 470000
Шаблон рекурсивный 530000Код C++11:
#include <iostream>
#include <bitset>
#include <algorithm>
#include <time.h>
/* Existing answer. Note that I've flipped the order of bit significance to match my own */
template<std::size_t N>
class BitByBitComparator
{
public:
bool operator()(const std::bitset<N>& x, const std::bitset<N>& y) const
{
for (int i = 0; i < N; ++i) {
if (x[i] ^ y[i]) return y[i];
}
return false;
}
};
/* New simple bit set class (note: mostly untested). Also note bad
design: should only allow read access via immutable facade. */
template<std::size_t N>
class SimpleBitSet
{
public:
static const int BLOCK_SIZE = 64;
static const int LOG_BLOCK_SIZE = 6;
static constexpr int NUM_BLOCKS = N >> LOG_BLOCK_SIZE;
std::array<unsigned long int, NUM_BLOCKS> allBlocks;
SimpleBitSet()
{
allBlocks.fill(0);
}
void addItem(int itemIndex)
{
// TODO: can do faster
int blockIndex = itemIndex >> LOG_BLOCK_SIZE;
unsigned long int & block = allBlocks[blockIndex];
int indexWithinBlock = itemIndex % BLOCK_SIZE;
block |= (0x8000000000000000 >> indexWithinBlock);
}
bool getItem(int itemIndex) const
{
int blockIndex = itemIndex >> LOG_BLOCK_SIZE;
unsigned long int block = allBlocks[blockIndex];
int indexWithinBlock = itemIndex % BLOCK_SIZE;
return bool((block << indexWithinBlock) & 0x8000000000000000);
}
};
/* New comparator type 1: block-by-block. */
template<std::size_t N>
class BlockByBlockComparator
{
public:
bool operator()(const SimpleBitSet<N>& x, const SimpleBitSet<N>& y) const
{
return ArrayCompare(x.allBlocks, y.allBlocks);
}
template <std::size_t S>
bool ArrayCompare(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
{
for (int i=0; i<S; ++i)
{
unsigned long int lhsBlock = lhs[i];
unsigned long int rhsBlock = rhs[i];
if (lhsBlock < rhsBlock) return true;
if (lhsBlock > rhsBlock) return false;
}
return false;
}
};
/* New comparator type 2: template recursive block-by-block. */
template <std::size_t I, std::size_t S>
class TemplateRecursiveArrayCompare;
template <std::size_t S>
class TemplateRecursiveArrayCompare<S, S>
{
public:
bool operator()(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
{
return false;
}
};
template <std::size_t I, std::size_t S>
class TemplateRecursiveArrayCompare
{
public:
bool operator()(const std::array<unsigned long int, S> & lhs, const std::array<unsigned long int, S> & rhs) const
{
unsigned long int lhsBlock = lhs[I];
unsigned long int rhsBlock = rhs[I];
if (lhsBlock < rhsBlock) return true;
if (lhsBlock > rhsBlock) return false;
return TemplateRecursiveArrayCompare<I+1, S>()(lhs, rhs);
}
};
template<std::size_t N>
class TemplateRecursiveBlockByBlockComparator
{
public:
bool operator()(const SimpleBitSet<N>& x, const SimpleBitSet<N>& y) const
{
return TemplateRecursiveArrayCompare<x.NUM_BLOCKS, x.NUM_BLOCKS>()(x.allBlocks, y.allBlocks);
}
};
/* Construction, timing, and verification code */
int main()
{
srand(0);
const int BITSET_SIZE = 4096;
std::cout << "Constructing..." << std::endl;
// Fill a vector with random bitsets
const int NUMBER_TO_PROCESS = 10000;
const int SAMPLES_TO_FILL = BITSET_SIZE;
std::vector<std::bitset<BITSET_SIZE> > allBitSets(NUMBER_TO_PROCESS);
std::vector<SimpleBitSet<BITSET_SIZE> > allSimpleBitSets(NUMBER_TO_PROCESS);
for (int k=0; k<NUMBER_TO_PROCESS; ++k)
{
std::bitset<BITSET_SIZE> bs;
SimpleBitSet<BITSET_SIZE> homemadeBs;
for (int j=0; j<SAMPLES_TO_FILL; ++j)
{
int indexToAdd = rand()%BITSET_SIZE;
bs[indexToAdd] = true;
homemadeBs.addItem(indexToAdd);
}
allBitSets[k] = bs;
allSimpleBitSets[k] = homemadeBs;
}
clock_t t1,t2,t3,t4;
t1=clock();
std::cout << "Sorting using bit-by-bit compare and std::bitset..." << std::endl;
const int NUMBER_REPS = 100;
for (int rep = 0; rep<NUMBER_REPS; ++rep)
{
auto tempCopy = allBitSets;
std::sort(tempCopy.begin(), tempCopy.end(), BitByBitComparator<BITSET_SIZE>());
}
t2=clock();
std::cout << "Sorting block-by-block using SimpleBitSet..." << std::endl;
for (int rep = 0; rep<NUMBER_REPS; ++rep)
{
auto tempCopy = allSimpleBitSets;
std::sort(tempCopy.begin(), tempCopy.end(), BlockByBlockComparator<BITSET_SIZE>());
}
t3=clock();
std::cout << "Sorting block-by-block w/ template recursion using SimpleBitSet..." << std::endl;
for (int rep = 0; rep<NUMBER_REPS; ++rep)
{
auto tempCopy = allSimpleBitSets;
std::sort(tempCopy.begin(), tempCopy.end(), TemplateRecursiveBlockByBlockComparator<BITSET_SIZE>());
}
t4=clock();
std::cout << std::endl << "RUNTIMES:" << std::endl;
std::cout << "\tstd::bitset \t" << t2-t1 << std::endl;
std::cout << "\tBlock-by-block \t" << t3-t2 << std::endl;
std::cout << "\tTemplate recursive \t" << t4-t3 << std::endl;
std::cout << std::endl;
std::cout << "Checking result... ";
std::sort(allBitSets.begin(), allBitSets.end(), BitByBitComparator<BITSET_SIZE>());
auto copy = allSimpleBitSets;
std::sort(allSimpleBitSets.begin(), allSimpleBitSets.end(), BlockByBlockComparator<BITSET_SIZE>());
std::sort(copy.begin(), copy.end(), TemplateRecursiveBlockByBlockComparator<BITSET_SIZE>());
for (int k=0; k<NUMBER_TO_PROCESS; ++k)
{
auto stdBitSet = allBitSets[k];
auto blockBitSet = allSimpleBitSets[k];
auto tempRecBlockBitSet = allSimpleBitSets[k];
for (int j=0; j<BITSET_SIZE; ++j)
if (stdBitSet[j] != blockBitSet.getItem(j) || blockBitSet.getItem(j) != tempRecBlockBitSet.getItem(j))
std::cerr << "error: sorted order does not match" << std::endl;
}
std::cout << "success" << std::endl;
return 0;
}
Хотя вы говорите, что бит установлен, разве вы не говорите о произвольной точности сравнения целых чисел без знака? Если это так, то вы, вероятно, не сможете легко добиться большего успеха, чем упаковка GMP.
С их сайта:
GMP тщательно спроектирован, чтобы быть максимально быстрым, как для маленьких операндов, так и для больших операндов. Скорость достигается за счет использования полных слов в качестве основного арифметического типа, использования быстрых алгоритмов, высоко оптимизированного кода сборки для наиболее распространенных внутренних циклов для большого количества процессоров и общего акцента на скорости.
Рассмотрим их целочисленные функции
Как насчет проверки старшего бита XOR?
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
return y[fls(x^y)]
}
int fls(const std::bitset<N>& n) {
// find the last set bit
}
Некоторые идеи для fps можно найти здесь http://uwfsucks.blogspot.be/2007/07/fls-implementation.html.
Ну, есть старое доброе memcmp, Это хрупкий в том смысле, что это зависит от реализации std::bitset, И поэтому может быть непригодным. Но разумно предположить, что шаблон создает непрозрачный массив ints. И не имеет других бухгалтерских полей.
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{
int cmp = std::memcmp(&x, &y, sizeof(x));
return (cmp < 0);
}
Это будет однозначно определять порядок для bitsets. Но это может быть не человеческий интуитивный порядок. Это зависит от того, какие биты используются для какого набора элементов индекса. Например, индекс 0 может быть младшим битом первого 32-разрядного целого числа. Или это может быть младший бит первого 8-битного байта.
Я настоятельно рекомендую модульные тесты, чтобы убедиться, что это действительно работает, как он используется.;->
Базовая реализация bitset использует uint64 практически во всех 64-битных процессорах, компиляторах и т. д., так как есть только один разумный способ написать реализацию класса с заданным интерфейсом, который упрощает разработку «портативного» хака. .
Итак, предполагая, что вам просто нужен «очевидный» эффективный способ сделать это, и ваш код не будет использоваться для управления ядерным арсеналом, прекрасно зная, что это аннулирует вашу гарантию, бла-бла-бла, вот код, который вы ищете:
template <int N> bool operator<(const bitset<N> & a, const bitset<N> & b) {
const uint64_t * p = (const uint64_t *)(&a);
const uint64_t * q = (const uint64_t *)(&b);
const uint64_t * r = p;
int i= (sizeof(bitset<N>)-1)/sizeof(uint64_t);
for (p+=i, q+=i; (p>=r) && (*p==*q); --p, --q) {}
return *p<*q;
}
В основном приводите к массиву uint64 и сравнивайте элемент за элементом в обратном порядке, пока не найдете несоответствие.
Также будьте осторожны, это предполагает порядок байтов x86-64.
Я знаю, что это немного старый вопрос, но если вы знаете максимальный размер битового набора, вы можете создать что-то вроде этого:
class Bitset{
vector<bitset<64>> bits;
/*
* operators that you need
*/
};
Это позволяет вам использовать каждый из bitsets<64> к unsigned long longдля быстрого сравнения. Если вы хотите перейти к конкретному биту (чтобы изменить его или что-то еще), вы можете сделатьbits[id / 64][id % 64]
Выполнение побитового сравнения только в том случае, если два набора битов уже различны, дает некоторое повышение производительности:
template<std::size_t N>
bool operator<(const std::bitset<N>& x, const std::bitset<N>& y)
{ if (x == y)
return false;
….
}