C++ -代码优化

Question

我有个问题：

您将得到一个序列，以字符串的形式显示字符“0”、“1”和“？”只有这样。假设有k‘？’s，那么有2^k的方法来替换每个‘？由‘0’或‘1’，给出2^k不同的0-1序列(0-1序列是只有0和1的序列)。 对于每个0-1序列，将其倒置数定义为按非递减顺序排序所需的最小相邻交换数。在这个问题中，当所有的零发生在所有的零之前时，序列被精确地按非递减的顺序排序。例如，序列11010有5个反转。我们可以按以下步骤进行排序: 11010→→11001→→10101→→01101→→01011→→00111。 查找2^k序列模1000000007 (10^9+7)的反转次数之和。

例如：

输入：？01 ->输出:5 输入：?0？->输出:3

这是我的密码：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <math.h>

using namespace std;



void ProcessSequences(char *input)
{
int c = 0;

/* Count the number of '?' in input sequence
 * 1??0 -> 2
 */
for(int i=0;i<strlen(input);i++)
{
    if(*(input+i) == '?')
    {
        c++;
    }       
}


/* Get all possible combination of '?'
 * 1??0
 * -> ?? 
 * -> 00, 01, 10, 11
 */
int seqLength = pow(2,c);
// Initialize 2D array of integer
int **sequencelist, **allSequences;
sequencelist = new int*[seqLength];
allSequences = new int*[seqLength];
for(int i=0; i<seqLength; i++){
    sequencelist[i] = new int[c];
    allSequences[i] = new int[500000];
}
//end initialize

for(int count = 0; count < seqLength; count++)
{
    int n = 0;
    for(int offset = c-1; offset >= 0; offset--)
    {
        sequencelist[count][n] = ((count & (1 << offset)) >> offset);
        // cout << sequencelist[count][n];
        n++;
    }
    // cout << std::endl;
}   

/* Change '?' in former sequence into all possible bits
 * 1??0 
 * ?? -> 00, 01, 10, 11
 * -> 1000, 1010, 1100, 1110
 */
for(int d = 0; d<seqLength; d++)
{
    int seqCount = 0;
    for(int e = 0; e<strlen(input); e++)
    {
        if(*(input+e) == '1')
        {
            allSequences[d][e] = 1;
        }
        else if(*(input+e) == '0')
        {
            allSequences[d][e] = 0;
        }
        else
        {
            allSequences[d][e] = sequencelist[d][seqCount];
            seqCount++;
        }
    }
}


/* 
 *  Sort each sequences to increasing mode
 * 
 */
// cout<<endl;
int totalNum[seqLength];
for(int i=0; i<seqLength; i++){
    int num = 0;
    for(int j=0; j<strlen(input); j++){
        if(j==strlen(input)-1){
            break;
        }
        if(allSequences[i][j] > allSequences[i][j+1]){
            int temp = allSequences[i][j];
            allSequences[i][j] = allSequences[i][j+1];
            allSequences[i][j+1] = temp;
            num++;
            j = -1;
        }//endif
    }//endfor
    totalNum[i] = num;
}//endfor





/*
 * Sum of all Num of Inversions
 */
int sum = 0;
for(int i=0;i<seqLength;i++){
    sum = sum + totalNum[i];
}


// cout<<"Output: "<<endl;
int out = sum%1000000007;
cout<< out <<endl;


} //end of ProcessSequences method


int main()
{
   // Get Input
   char seq[500000];
   // cout << "Input: "<<endl;
   cin >> seq;

   char *p = &seq[0];

   ProcessSequences(p);
   return 0;
}

结果表明，对于小尺寸的输入是正确的，但对于较大的输入，CPU的时间限制大于1秒。我也被超过了内存大小。如何使它更快、更好地使用内存？我应该使用什么算法，应该使用什么更好的数据结构？，谢谢。

Answer 1

动态规划是可行的。假设您正在向所有序列中添加最后一个字符。

• 如果是1，那么就可以得到XXXXXX1。掉期的数量显然与到目前为止的每一个序列相同。
• 如果是0，那么您需要知道每个序列中已经有多少个。掉期数量将增加每个序列的掉期数量。
• 如果是?，您只需将前面的两种情况加在一起

你需要计算出有多少个序列。对于每一个长度和每一个数目(序列中的数目不能大于序列的长度，自然)。从长度1开始，这是微不足道的，然后再用更长的长度开始。你可以得到很大的数字，所以你应该一直计算模块1000000007。程序不在C++中，但是应该很容易重写(数组应该初始化为0，int为32位，长为64位)。

long Mod(long x)
{
    return x % 1000000007;
}

long Calc(string s)
{
    int len = s.Length;
    long[,] nums = new long[len + 1, len + 1];
    long sum = 0;
    nums[0, 0] = 1;

    for (int i = 0; i < len; ++i)
    {
        if(s[i] == '?')
        {
            sum = Mod(sum * 2);
        }
        for (int j = 0; j <= i; ++j)
        {
            if (s[i] == '0' || s[i] == '?')
            {
                nums[i + 1, j] = Mod(nums[i + 1, j] + nums[i, j]);
                sum = Mod(sum + j * nums[i, j]);
            }

            if (s[i] == '1' || s[i] == '?')
            {
                nums[i + 1, j + 1] = nums[i, j];
            }
        }
    }

    return sum;
}

Optimalization

编写上面的代码是为了尽可能清晰，并展示动态编程方法。您实际上不需要数组[len+1, len+1]。您可以从列i+1中计算列i，并且永远不会返回，因此两列就足够了--旧的和新的。如果深入研究它，您会发现新列的行j仅依赖于旧列的行j和j-1。因此，如果您按照正确的方向实现值(并且不覆盖所需的值)，则可以使用一列。

上面的代码使用64位整数。您确实只需要在j * nums[i, j]中这样做。nums数组包含小于1000000007的数字，32位整数就足够了。即使是2*1000000007也可以适应32位签名的int，我们可以利用它。

我们可以通过嵌套循环而不是循环中的条件来优化代码。也许这是更自然的方法，唯一的缺点是重复代码。

与每次除法一样，%运算符非常昂贵。j * nums[i, j]通常比64位整数的容量小得多，所以我们不必在每一步中都做模块。只需观察实际值，并在需要时应用。Mod(nums[i + 1, j] + nums[i, j])也可以优化，因为nums[i + 1, j] + nums[i, j]总是小于2*1000000007。

最后是优化的代码。我转到了C++，我意识到int和long的含义是不同的，所以要明确如下：

long CalcOpt(string s)
{
    long len = s.length();
    vector<long> nums(len + 1);
    long long sum = 0;
    nums[0] = 1;
    const long mod = 1000000007;

    for (long i = 0; i < len; ++i)
    {
        if (s[i] == '1')
        {
            for (long j = i + 1; j > 0; --j)
            {
                nums[j] = nums[j - 1];
            }
            nums[0] = 0;
        }
        else if (s[i] == '0')
        {
            for (long j = 1; j <= i; ++j)
            {
                sum += (long long)j * nums[j];
                if (sum > std::numeric_limits<long long>::max() / 2) { sum %= mod; }
            }
        }
        else
        {
            sum *= 2;
            if (sum > std::numeric_limits<long long>::max() / 2) { sum %= mod; }
            for (long j = i + 1; j > 0; --j)
            {
                sum += (long long)j * nums[j];
                if (sum > std::numeric_limits<long long>::max() / 2) { sum %= mod; }
                long add = nums[j] + nums[j - 1];
                if (add >= mod) { add -= mod; }
                nums[j] = add;
            }
        }
    }

    return (long)(sum % mod);
}

Simplification

时限还在延长吗？也许有更好的方法来做到这一点。你可以

1. 回到起点，找出不同的数学方法来计算结果。
2. 或者用数学简化实际的解决方案

我走了第二条路。我们在循环中所做的实际上是两个序列的卷积，例如：

0, 0, 0, 1, 4, 6, 4, 1, 0, 0,... and 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,...
0*0 + 0*1 + 0*2 + 1*3 + 4*4 + 6*5 + 4*6 + 1*7 + 0*8...= 80

第一个序列是对称的，第二个序列是线性的。在这种情况下，卷积和可以由第一序列之和= 16 (numSum)和第二序列对应于第一序列中心的数5 (numMult)计算。numSum*numMult = 16*5 = 80。如果我们能够在每一步中更新这些数字，我们就用一个乘法替换整个循环，这似乎是偶然的情况。

如果si == '0‘，那么numSum不会改变，numMult也不会改变。

如果si == '1‘那么numSum不改变，则只有numMult增加1，因为我们将整个序列移动一个位置。

如果si ==‘？我们将原始序列和移位序列相加在一起。numSum乘以2，numMult增量乘以0.5。

0.5表示有点问题，因为它不是全部数字。但我们知道，结果会是整数。幸运的是，在这种情况下，模算法中存在2 (=1/2)整数的反转。它是h= (mod+1)/2，作为提醒，2的反转是这样一个数字，使得h*2=1模模。明智地实现--将numMult乘以2，将numSum除以2更容易，但这只是一个细节，无论如何，我们需要0.5。守则：

long CalcOptSimpl(string s)
{
    long len = s.length();
    long long sum = 0;
    const long mod = 1000000007;
    long numSum = (mod + 1) / 2;
    long long numMult = 0;

    for (long i = 0; i < len; ++i)
    {
        if (s[i] == '1')
        {
            numMult += 2;
        }
        else if (s[i] == '0')
        {
            sum += numSum * numMult;
            if (sum > std::numeric_limits<long long>::max() / 4) { sum %= mod; }
        }
        else
        {
            sum = sum * 2 + numSum * numMult;
            if (sum > std::numeric_limits<long long>::max() / 4) { sum %= mod; }

            numSum = (numSum * 2) % mod;
            numMult++;
        }
    }

    return (long)(sum % mod);
}

我很确定有一些简单的方法来获得这段代码，但我仍然无法看到它。但有时路径是目标:-)

Answer 2

如果一个序列有N个索引为zero[0], zero[1], ... zero[N - 1]的零，那么它的反转数将是(zero[0] + zero[1] + ... + zero[N - 1]) - (N - 1) * N / 2。(你应该能够证明这一点)

例如，11010有两个索引为2和4的零，因此倒置数为2 + 4 - 1 * 2 / 2 = 5。

对于所有2^k序列，可以分别计算两部分的和，然后将它们相加。

1)第一部分是zero[0] + zero[1] + ... + zero[N - 1]。给定序列中的每个0贡献index * 2^k，每个?贡献index * 2^(k-1)

2)第二部分是(N - 1) * N / 2。您可以使用动态编程来计算这个值(也许您应该先在google上了解这一点)。简而言之，使用f[i][j]来使用给定序列的第一个i字符来表示带有j零的序列数。