优化基于查询的搜索

Question

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

• set_a idx x:将Aidx设置为x，其中0 <= idx < N，其中Aidx是A.
• set_b idx中最不重要的一点: Set Bidx to x，0 <= idx < N.
• get_c idx: Print Cidx，where C=A+B和0<=idx

现在，我已经尽可能地优化了代码。

首先，我尝试为a、b和c使用int数组，每次更新时，我计算c并在查询时返回ith位。太慢了。只清除4/11测试用例。

• i转到使用布尔数组。它比int数组方法快2倍左右。清除了7/11 testcases.

• Next，，我想我不需要计算c来计算idx的第四位A+B，我只会从idx向右扫描A和B，直到我找到ai=bi=0或ai=bi=1为止。如果是ai=bi=0，那么我就把它加到从初始carry=0开始的idx第四位。如果是testcases.

• Then，，那么我就往左加到idx的第四位，从初始的carry=1开始。这是更快的，但是只清除了8/11的ai=bi=1，我计算出一次，我到达i，ai=bi=0或ai=bi=1位置，那么我不需要加到idx的第四个位置。如果是ai=bi=0，那么答案是(aidx+bidx)%2，如果是ai=bi=1，则答案是(aidx+bidx+1)%2。它大约快了40%，但仍然只清除了8/11的测试用例。

。

现在我的问题是，怎样才能把这三个“艰难”的测试案例降下来？我不知道他们是什么，但程序需要>3秒来解决问题。

下面是代码：http://ideone.com/LopZf

Answer 1

一种可能的优化方法是替换

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

使用

a[pos]^b[pos]^carry

XOR运算符(^)执行加法模2，因此可能需要昂贵的mod操作(%)。根据语言和编译器的不同，编译器可能会在执行功率为2的模块时为您进行优化。但是，由于您是在进行微优化，这是一个简单的更改，它消除了对后台为您进行的优化的依赖。

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

这只是一个简单的建议。正如其他人所建议的那样，使用打包的ints来表示您的位数组可能还会改进您的代码可能是最糟糕的测试。这将是最重要位的get_c函数，对于所有其他位置，A或B(但不是两者)都是1，需要扫描每个位位置到最不重要的位以确定进位。如果您正在为您的位使用打包的ints，那么只需要大约1/32的操作(假设32位ints)。然而，使用打包的ints要比使用简单的布尔数组(它很可能只是一个字节数组)要复杂一些。

C/C++ Bit Array or Bit Vector

Convert bit array to uint or similar packed value

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

在Stackoverflow和net上还有很多其他示例，用于将ints当作位数组使用。

Answer 2

这是一个看起来有点像你的算法的解决方案。我用字节来演示它，但是当然您可以使用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;
}

如果你发现什么神秘的东西，就问吧。编辑:哎呀，我倒了零位条件.