别见笑, 一个基础 C/C++ 问题

[dragonLinux]

1。如shusheng所说，开个数组，事先把个数先写到数组中，我想这应该是所有面试人想要的答案，当然除了我，因为我并不完全觉得。
2。如 老兵新手 所说，就是移位计算。但是我想用汇编写，当然也可以用C写，就是不知道编译器能不能优化好，如果优化好了，我觉得这个方案是最快的。

 

[dragonLinux]

int ct[256] = { 0, 1, 1, 2...}; /* 我把后面的省略了*/

inline int counter_bit(unsigned char input)
{
return ct[input];

}
从指令数上算，这个实现已经不可能再快了，但是这个实现的不好的地方就是要访问内存次数多一些，第一次取ct地址到寄存器，第二次根据基地址加偏移，再读一次内存得到结果。
当然，我不想排除有从 L1cache, L2cache得到结果的可能性。这当然也就意味着，你读了很多次，才会提高cache命中率。

 

[老兵新手]

我的题目是求一个整数里为 1 的 bits 的个数. 总不能写一个 2^32 的数组吧?
移位的话用一循环就成:
sum=0;
for (int i=0; i<32; i++) {
sum += a & 0x01;
a >>= 1;
}
目标程序应该是很简单的.

 

[dragonLinux]

啊，如果是整数的话，似乎没什么办法了，不过似乎此题没什么特别意义了!
另外就是我强调的是访存次数，因为即使是DDR，现在的速度还是bottleneck,所以在risc处理器上，老兵新手的程序很可能比我说的快，如果全都在寄存器上操作的话，因为循环较少为8或者4或者不用循环，纯顺序结构，可以纯计算指令数来当 作时间消费，而且实际上肯定会更快，因为处理器的pipeline.
现在的itanium有128个寄存器，所以会更快。

 

[shusheng]

1) 整数也可以拆成4个byte来查表。或者8个4bit的数来查0-15的表。不过拆分也费工夫。
2）如果是x86，有循环移位到标志位的指令，然后加标志们就行了。可以用汇编省下判断的指令。

 

[dragonLinux]

最初由 shusheng 发布
1) 整数也可以拆成4个byte来查表。或者8个4bit的数来查0-15的表。不过拆分也费工夫。
2）如果是x86，有循环移位到标志位的指令，然后加标志们就行了。可以用汇编省下判断的指令。

1)有道理，拆分时间可以忽略不记了，相对于内存存取，因为寄存器移位1,2个指令周期肯定搞定了，可内存存取可不止20,30指令周期，cpu越快会越多。

 

[老兵新手]

各位对一个不能一次装入的 huge 的 hash 表, 怎么能高效的查询基本数据, 有何高见?

 

[dragonLinux]

最初由 老兵新手 发布
各位对一个不能一次装入的 huge 的 hash 表, 怎么能高效的查询基本数据, 有何高见?

没明白，请举个例子。你的意思是说这个hash表会边查询边添加，删除？

 

[老兵新手]

有一个巨大的表格式数据. 各位认为怎么组织能获得最快的查询?
我用 hash 表组织它们, 但对这个巨大的数据库, hash 表也巨大. 组织好后,查询时, 我们得到 hash 值后, 需要 load hash 表到 memory 里先. 但 hash 表太大, 不能一次全部装入, 如果每次都分别装入一部分, 速度就慢了.

另外大家有听说排序 hash 表的吗?

 

[dragonLinux]

最初由 老兵新手 发布
有一个巨大的表格式数据. 各位认为怎么组织能获得最快的查询?
我用 hash 表组织它们, 但对这个巨大的数据库, hash 表也巨大. 组织好后,查询时, 我们得到 hash 值后, 需要 load hash 表到 memory 里先. 但 hash 表太大, 不能一次全部装入, 如果每次都分别装入一部分, 速度就慢了.

另外大家有听说排序 hash 表的吗?

这相当于数据库的索引都不能全部装入内存，可能数据库方面会有些解决方案吧。分级hash?
排序 hash 表是？

 

[老兵新手]

最初由 dragonLinux 发布

这相当于数据库的索引都不能全部装入内存，可能数据库方面会有些解决方案吧。分级hash?
排序 hash 表是？

The question is how to solve the problem which memory cannot hold the whole hash table?

The following question is how to sort a hash table? (strange question?)

 

[dragonLinux]

最初由 老兵新手 发布


The question is how to solve the problem which memory cannot hold the whole hash table?

The following question is how to sort a hash table? (strange question?)

a little strange!
if a hash table is not sort, how to use hash value to get the hash table item?

 

[dragonLinux]

static __inline uint32_t
bitcount32(uint32_t x)
{

x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);
x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);
x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);
x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);
x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);
return (x);
}

最近看代码时,发现在linux, bsd中有一些答案,应该说是最合理和最快的了,应该比上面的用数组索引实现快,因为完全x可以在寄存器中操作.