對應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;
}
當我說「最優化的方式：」我期待使用按位運算和元編程技巧（之類的）的實現。
編輯：我認爲我已經找到了技巧：模板元編程爲編譯時遞歸和正確的bitshift爲了比較bitsets作爲幾個無符號的長整型。但沒有清楚的想法如何做...
明顯的優化將是
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更好，但這是一個長鏡頭。
@dyp誰知道。這是一個性能問題，所以最終你必須對它進行基準測試。它可能隨每個編譯器版本而改變。如果考慮「小」比特集，也可以使用'to_ullong'專門爲<= 64比特，但我想這個問題的精神更像是幾百比特。 –
+1對於其尺寸的解決方案，很難做得更好。有關模板遞歸版本，請參閱下文。 – user
請注意，即使'的std :: bitset的
如何檢查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。
好主意，除了負運算符沒有爲位集定義... – Vincent
問題：優化'fls'需要內部訪問bitset，就像原始問題一樣。 –
我只是看了看源代碼，但不幸的是（除非，希望我錯了），他們似乎並沒有讓你就位訪問特定位塊的const & unsigned long。如果他們這樣做了，那麼你可以執行模板遞歸，並且有效地比較每個unsigned long而不是無符號長整數中的每一位。
畢竟，如果A < B，那麼不僅應該每個最高有效位a <= b，也是每個最重要的塊A[i] <= B[i]。
我討厭這麼說，但我可能會用C++ 11的std::array遞歸遞歸。如果你有權訪問這些塊，那麼你可以做一個模板遞歸函數來做到這一點很容易（因爲你確實知道你知道元編程），所以給編譯器一個很好的機會來優化。
總而言之，這不是一個好的答案，但那就是我會做的。順便說一下，這是一個很好的問題。
===========
這應該時間三種方法：將一個使用最新的upvotes，我描述區塊策略和模板遞歸變種。我用bitsets填充矢量，然後使用指定的比較器函子重複排序。
快樂黑客！
輸出我的電腦上：
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;
}
雖然你說的位設置，你不是真的在談論任意精度的無符號整數比較。如果是這樣，那麼你可能不會輕鬆做得更好，然後包裝GMP。
從他們的網站：
GMP經過精心設計，以儘可能快的，既爲小 操作數和巨大的操作數。速度是通過使用 fullwords作爲基本算術類型來實現，通過使用快速算法，與 用於爲 很多CPU的最常見的內環高度優化彙編代碼，並通過一般的強調速度。
如果你願意採用的解決方案，如果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();
}
編譯器會引發的，如果離開
關於你的想法無關分支使用正確的bitshift：這將創建大量的中間對象，並且to_ullong將必須檢查移位後的值是否適合每個檢查的「無符號long long」，從而創建相當的s頭頂上。我懷疑它會更快，但只有基準可以證明這一點。 –
複製std :: bitset的代碼，重命名它，給它一種訪問某個單詞的方法。 –
@brianbeuning如果你正在複製代碼，你可以簡單地提供一個可以訪問內部的'operator <'。 –