我的系统的相关信息: 酷睿2双核T6500 gcc(GCC)4.4.1 20090725(红帽4.4.1-2)
使用基本的集合实现,其中存储的每个集合实际上只是存储的集合的字典顺序,您可以对集合操作使用标准位操作,例如并集、交集、elementQ 等。
我的问题是关于确定集合的大小。实现如 Cliquer使用
static int set_bit_count[256]
存储任何给定的可能的 8 位字符串中有多少位,然后算法将一次遍历 8 位来确定集合的大小。
这样我有两个问题:
- 如果寄存器的速度比缓存或 RAM 快 8 倍以上,就会浪费速度。
- 在 64 位机器中,
int
操作并不比unsigned long long int
慢,我认为这是 64 位 CPU 上的标准操作整数。
但我想只使用一个简单的
while(x)
x&=x-1;
++count;
可能会更快,因为所有内容都可以存储在寄存器中。但不利的一面是,除了明显的 8 倍操作次数之外,还能有其他方法吗?
此外, int、uint、unsigned long、unsigned long long
有很多不同的组合,我不知道从哪里开始测试。
你知道关于这个主题的任何文章吗?
您还知道有关此主题的其他问题吗?
您对此有什么见解吗?
您对如何分析此内容有什么建议吗?我从来没有用过gprof。当我使用 time.h 时,我无法获得比一秒更精细的粒度。
如果您这样做,我将非常感激。
最佳答案
最有可能(虽然我现在懒得测试),最快的是
int popcount(unsigned x) {
int count;
#if defined(__GNUC__)
__asm__("popcnt %1,%0" : "=r" (count) : "r" (x));
#elif defined(_MSC_VER)
__asm {
POPCNT x, count
};
#else
/* blah, who cares */
for (count = 0; x; count += x&1, x >>= 1);
#endif
return count;
}
(尽管如果CPU不支持SSE4.2,这会爆炸。)当然,使用编译器的内置内在函数会更好(并且更便携),一般来说我会信任编译器选择最适合当前目标平台的实现。
int popcount(unsigned x);
#if defined(__GNUC__)
# define popcount __builtin_popcount
#elif defined(_MSC_VER)
# define popcount __popcnt
#else
/* fallback implementation */
#fi
关于c - 在 64 位机器上分析 Set 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1925964/