Самый быстрый способ сравнить биты (<оператор на битах)?

Question

Какой самый оптимизированный способ реализовать оператор < для 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; 
} 

Когда я говорю «самый оптимизированный способ» Я ищу для реализаций с помощью битовых операций и метапрограммирования трюки (и тому подобное).

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

Answer 1

Очевидная оптимизация будет

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, но это длинный снимок.

Answer 2

Как насчет проверки наивысшего бита 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.

Answer 3

Я просто посмотрел на исходный код, но, к сожалению (если, надеюсь, я не ошибаюсь), они, похоже, не дают вам доступ на месте к const & unsigned long для конкретного блока бит. Если бы они это сделали, вы могли бы выполнить рекурсию шаблона и эффективно сравнить каждый unsigned long, а не каждый бит в unsigned long.

В конце концов, если A < B, то не только должны быть каждый из наиболее значимых бит a <= b, также каждый из наиболее значимых блоков A[i] <= B[i].

Ненавижу говорить об этом, но я бы, скорее всего, применил рекурсию на C++ 11's std::array. Если у вас есть доступ к блокам, вы можете сделать рекурсивную функцию шаблона, чтобы сделать это довольно легко (и, как я уверен, вы знаете, так как вы просите метапрограммирование), дайте компилятору отличный шанс оптимизировать.

В целом, не большой ответ, но это то, что я буду делать.

Отличный вопрос, кстати.

===========

EDIT

Это должно раз в три подхода: один с наиболее актуальным upvotes, стратегия блока я описал, и шаблон рекурсивной вариант. Я заполняю вектор битами, а затем сортирую несколько раз с использованием указанного функтора компаратора.

Счастливый взлом!

Выход на моем компьютере:

 
RUNTIMES: 
compiled g++ -std=c++11 -Wall -g test.cpp 
    std::bitset   4530000 (6000000 original in OP) 
    Block-by-block  900000 
    Template recursive 730000 

compiled g++ -std=c++11 -Wall -g -O3 test.cpp 
RUNTIMES: 
    std::bitset   700000 (740000 original in OP) 
    Block-by-block  470000 
    Template recursive 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; 
} 

Answer 4

Хотя вы говорите, набор бит, не вы на самом деле говорите о произвольной точности целого числа без знака сравнение. Если да, то вы, вероятно, не собираетесь делать лучше, чем обертывать GMP.

С их сайта:

GMP тщательно разработан, чтобы быть как можно быстрее, как для небольших операндов и огромных операндов. Скорость достигается с использованием полных слов в качестве базового арифметического типа с использованием быстрых алгоритмов с 0 оптимизируемым ассемблерным кодом для наиболее распространенных внутренних циклов для большого количества процессоров и общим упором на скорость.

Рассмотрим their integer functions

Answer 5

Если вы готовы принять решение, если изменения STL BitSet вы можете использовать

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(); 
} 

компилятор бросает ненужную ветвь, если расстояние