数组<int, SIZE> t
如前所述,使用 C++17,您可以使用 constexpr
vector<int> countBits(int num) {
static constexpr int SIZE = 100000;
static constexpr array<int, SIZE> t {[]() constexpr {
constexpr uint32_t size = SIZE;
array<int, size> v{};
for (int i = 0; i < size; i++)
v[i] = v[i>>1] + (i & 1); // or simply v[i] = __builtin_popcount(i);
return v;}()};
vector<int> v(t.begin(), t.begin() + num + 1);
return v;
}
但是,您将不得不使用 c++ 数组类型。
整数 t[大小]
如果您真的想使用 C 数组int [SIZE]
,则不同于array<int, SIZE>
使用以下技巧:
声明一个全局数组,然后在 main 中计算值以在编译时创建静态数组:
int w[100000] = {0};
vector<int> countBits(int num) {
vector<int> v(w, w + num + 1);
return v;
}
int main(void) {
for (int i = 0; i < 100000; i++)
w[i] = __builtin_popcount(i);
}
结果
运行时的输出(确实很糟糕):
OK ( 591 cycles) 0,1,1, -> 0,1,1,
OK ( 453 cycles) 0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK ( 455 cycles) 0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...
constexpr 数组的平均输出:
OK ( 1 cycles) 0,1,1, -> 0,1,1,
OK ( 2 cycles) 0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK ( 24 cycles) 0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...
第二种方法的平均输出(由于我们摆脱了 C++ 数组的开销,所以速度稍快):
OK ( 0 cycles) 0,1,1, -> 0,1,1,
OK ( 1 cycles) 0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK ( 23 cycles) 0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...
基准
我的基准测试是:
#include <vector>
#include <string>
#include <cstdint>
#include <array>
#include <iostream>
#include <ctime>
#include <iterator>
#include <sstream>
using namespace std;
vector<int> nums = {2, 5};
vector<vector<int>> expected = {{0,1,1}, {0,1,1,2,1,2}}; // feel free to add more tests
for (int i = 0; i < expected.size(); i++) {
clock_t start = clock();
vector<int> res = countBits(nums[i]);
double elapsedTime = (clock() - start);
printf("%s \033[30m(%4.0lf cycles)\033[0m\t %s -> %s\n", (expected[i] == res) ? "\033[34mOK" : "\033[31mKO", elapsedTime, toString(res).c_str(), toString(expected[i]).c_str());
}