所以本质上你正在做的是:
k_0 = h_1 mod s
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s
..
k_n = k_(n-1) + h_2 mod s
根据溢出问题(如果大小小于2 ** 64
,则不应与原始数据不同),这种方法可能会更快(虽然难以并行化):
uint64_t h_one = hash[0];
uint64_t h_two = hash[1];
k_hash[0] = h_one % size;
for ( int i=1; i<k; ++i )
{
(uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two ) % size;
}
请注意,根据您使用的优化标志,您的编译器可能已经达到了这种形式。
当然,这仅消除了一次乘法。如果您想消除或减少取模操作,我猜您可以基于
h_two%size
和
h_1%size
预先确定必须显式调用
%size
的步骤,就像这样:
uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
step = (size-(h_one))/(h_two)-1;
for ( int i=1; i<k; ++i )
{
(uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two );
if(i==step)
{
k_hash[i] %= size;
}
}
请注意,我不确定这个公式是否正确(没有测试过),它更多是一个概念。这将在很大程度上取决于您的分支预测有多好(以及错误预测对性能的影响有多大)。此外,只有在步长较大时才可能有帮助。
编辑:或者更简单(并且可能具有相同的性能)-感谢Mystical:
uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
for ( int i=1; i<k; ++i )
{
(uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two );
if(k_hash[i] > size)
{
k_hash[i] -= size;
}
}