c++ - 这段代码有什么未优化的地方?

标签 c++ optimization

<分区>

我在interviewstreet上写了一个问题的解决方案,这里是问题描述:

https://www.interviewstreet.com/challenges/dashboard/#problem/4e91289c38bfd

这是他们给出的解决方案:

https://gist.github.com/1285119

这是我编写的解决方案:

#include<iostream>
#include <string.h>
using namespace std;
#define LOOKUPTABLESIZE 10000000
int popCount[2*LOOKUPTABLESIZE];
int main()
{
int numberOfTests = 0;
cin >> numberOfTests;

for(int test = 0;test<numberOfTests;test++)
{
    int startingNumber = 0;
    int endingNumber = 0;
    cin >> startingNumber >> endingNumber;

    int numberOf1s = 0;


    for(int number=startingNumber;number<=endingNumber;number++)
    {
        if(number >-LOOKUPTABLESIZE && number < LOOKUPTABLESIZE)
        {
            if(popCount[number+LOOKUPTABLESIZE] != 0)
            {
                numberOf1s += popCount[number+LOOKUPTABLESIZE];
            }
            else
            {
                popCount[number+LOOKUPTABLESIZE] =__builtin_popcount (number);
                numberOf1s += popCount[number+LOOKUPTABLESIZE];
            }
        }
        else
        {
        numberOf1s += __builtin_popcount (number);
        }
    }
    cout << numberOf1s << endl;

}

}

你能指出我的代码有什么问题吗?它只能通过 3/10 的测试。时间限制为 3 秒。

最佳答案

What is unoptimized about this code?

算法。你在循环

for(int number=startingNumber;number<=endingNumber;number++)

计算或查找每个 1 位的数量。这可能需要一段时间。

一个好的算法计算所有数字中1位的数量0 <= k < nO(log n)时间使用一点数学。

Here是一个在十进制扩展中计算 0 的实现,修改以使其计算 1 位应该不难。

关于c++ - 这段代码有什么未优化的地方?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13331730/

相关文章:

optimization - 弱类型会提高性能还是降低性能?

python - 不重叠某些像素的随机矩形

mysql - 非顺序(例如,UUID/GUID)数据如何降低索引性能?

python - scipy.optimize 非线性约束

c - SIMD 值得吗?有更好的选择吗?

c++ - 在 .rs 资源文件 C++ 控制台中使用参数

c++ - symbian 的 sqlite db2 错误

c++ - 持有对 Derived 的引用的基类

c++ - 尽管循环次数减半,但循环速度并不快?

c++ - 使用 repeat 将 Boost Spirit Qi 存储到 std::vector 中会导致模棱两可的类模板实例化