0

我们有两个 N 位数（0< N< 100000）。我们必须对这些数字执行 q 次查询（0< q<500000）。查询可以有以下三种类型：

  • set_a idx x：将 A[idx] 设置为 x，其中 0 <= idx < N，其中 A[idx] 是 A 的第 idx 个最低有效位。

  • set_b idx x：将 B[idx] 设置为 x，其中 0 <= idx < N。

  • get_c idx：打印C[idx]，其中C=A+B，0<=idx

现在，我已尽我所能优化代码。

  • 首先，我尝试为 a、b 和 c 使用一个 int 数组。对于每次更新，我计算 c 并在查询时返回第 i 位。这该死的慢。仅清除 4/11 测试用例。

  • 我转而使用布尔数组。它比 int 数组方法快大约 2 倍。清除 7/11 测试用例。

  • 接下来，我发现我不需要计算 c 来计算 A+B 的第 idx 位。我将从 idx 向右扫描 A 和 B，直到找到 a[i]=b[i]=0 或 a[i]=b[i]=1。如果 a[i]=b[i]=0，那么我只需从初始进位 =0 开始向左加到第 idx 位。如果 a[i]=b[i]=1，那么我只需从初始进位 =1 开始向左加到第 idx 位。这更快，但只清除了 8/11 测试用例。

  • 然后，我想通了一次，我到达位置 i，a[i]=b[i]=0 或 a[i]=b[i]=1，然后我不需要加到第 idx 个位置。如果a[i]=b[i]=0，那么答案是(a[idx]+b[idx])%2，如果a[i]=b[i]=1，那么答案是(a[ idx]+b[idx]+1)%2。它快了大约 40%，但仍然只清除了 8/11 的测试用例。

现在我的问题是如何处理这 3 个“硬”测试用例？我不知道它们是什么，但程序需要> 3 秒才能解决问题。

这是代码：http: //ideone.com/LopZf

4

2 回答 2

0

这是一个看起来有点像您的算法的解决方案。我用字节来演示它，但当然你可以使用 32 位字轻松优化算法（我想你的机器现在有 64 位算术）。

void setbit( unsigned char*x,unsigned int idx,unsigned int bit)
{
   unsigned int digitIndex = idx>>3;
   unsigned int bitIndex = idx & 7;
   if( ((x[digitIndex]>>bitIndex)&1) ^ bit) x[digitIndex]^=(1u<<bitIndex);
}
unsigned int getbit(unsigned char *a,unsigned char *b,unsigned int idx)
{
   unsigned int digitIndex = idx>>3;
   unsigned int bitIndex = idx & 7;
   unsigned int c = a[digitIndex]+b[digitIndex];
   unsigned int bit = (c>>bitIndex) & 1;
   /* a zero bit on the right will absorb a carry, let's check if any */
   if( (c^(c+1))>>bitIndex )
   {
      /* none, we must check if there's a carry propagating from the right digits */
      for(;digitIndex-- > 0;)
      {
         c=a[digitIndex]+b[digitIndex];
         if( c > 255 ) return bit^1; /* yes, a carry */
         if( c < 255 ) return bit;   /* no carry possible, a zero bit will absorb it */
      }
   }
   return bit;
}

如果您发现任何神秘的东西，请问。编辑：哎呀，我颠倒了零位条件......

于 2012-06-29T21:43:14.390 回答
0

一种可能的优化是替换

(a[pos]+b[pos]+carry)%2

和

a[pos]^b[pos]^carry

XOR 运算符 (^) 执行模 2 加法，从而不需要可能昂贵的 mod 操作 (%)。根据语言和编译器的不同，编译器可能会在执行 2 次幂的 mod 时为您进行优化。但是由于您正在进行微优化，因此只需进行简单的更改即可消除对在后面为您进行的优化的依赖场景。

http://en.wikipedia.org/wiki/Exclusive_or

这只是一个很容易提出的建议。正如其他人所建议的那样，使用压缩整数来表示您的位数组也可能会改善您的代码可能是最坏情况的测试。这将是最高有效位的 get_c 函数，对于所有其他位置，A 或 B（但不是两者）都为 1，需要扫描每个位位置到最低有效位以确定进位。如果您对位使用压缩整数，则所需操作的数量只有大约 1/32（假设为 32 位整数）。然而，使用压缩整数比使用简单的布尔数组（它实际上可能只是一个字节数组）要复杂一些。

C/C++ 位数组或位向量

将位数组转换为 uint 或类似的打包值

http://en.wikipedia.org/wiki/Bit_array

在 Stackoverflow 和网络上还有很多其他示例可以将整数用作位数组。

于 2012-05-15T15:32:24.363 回答