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/

相关文章:

c++ - 在 C++ 代码中构建错误

c++ - int 转换——给我奇怪的数字

c++ - 将 RAII 与 C++ 流和 STL 容器一起使用?

.NET运行时优化服务

ios - 如何在 AIR IOS 上优化大尺寸 jpeg? (AS3)

java - 三元运算符是否比 Java 中的 "if"条件快

c++ - memcpy() 可以用来更改 "const"成员数据吗?

c++ - omp 最大减少与索引的存储

assembly - RMW 指令对现代 x86 是否有害?

c++ - VS 是否优化了相同类型的转换?