我刚才查看了源代码，但不幸的是（除非我弄错了），它们似乎没有为特定位块提供
const & unsigned long 的原地访问。如果有的话，您可以执行模板递归，并有效比较每个
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（OP中原始的6000000）
块对块900000
模板递归730000
编译g++-std = c ++ 11-Wall-g-O3 test.cpp
运行时间：
std :: bitset 700000（OP中的740000）
块对块470000
模板递归530000
C++11代码：
#include <iostream>
#include <bitset>
#include <algorithm>
#include <time.h>
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;
}
};
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)
{
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);
}
};
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;
}
};
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);
}
};
int main()
{
srand(0);
const int BITSET_SIZE = 4096;
std::cout << "Constructing..." << std::endl;
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;
}
to_ullong将不得不检查每个检查中移位后的值是否适合unsigned long long，从而创建相当多的开销。我怀疑它不会更快，尽管只有基准测试才能证明这一点。 - Daniel Freyoperator<。 - Daniel Frey