C++ 程序员倾向于使用 std::string 类来表示字符串。虽然实现方式可能有所不同，但 std::string 的每个实例可能使用 32 个字节。虽然这不是很大的内存量，但加起来还是会很大。
在 Node.js 运行时中，作为构建工具的一部分，有一个函数可以预先计算所有 16 位整数的字符串表示形式，后跟逗号。
std::vector<std::string> precompute_string() {
size_t size = 1 << 16;
std::vector<std::string> code_table(size);
for (size_t i = 0; i < size; ++i) {
code_table[i] = std::to_string(i) + ',';
}
return code_table;
}
|
如何改进呢？
我们可以创建一个由字符串 "0,1,2,...,65535, "组成的单个字符串缓冲区，并记录字符串中的偏移量，这样就可以快速定位给定值的位置。 例如，给定整数 500，我想立即得到子串 "500, "的位置。 我需要两个偏移量：当前值的偏移量和下一个值的偏移量。
唯一字符串只需要 382106 字节，虽然数量不少，但比 std::string 实例数组所需的 2 兆字节少了好几倍。
在 C++ 中，您可以按如下方式编写代码。为简单起见，我们可以自己编写整数转字符串例程。
std::pair<std::array<char, 382106>,
std::array<uint32_t, 65537>> precompute_string_fast() {
std::array<char, 382106> str;
std::array<uint32_t, 65537> off;
off[0] = 0;
char *p = &str[0];
constexpr auto const_int_to_str =
[](uint16_t value, char *s) -> uint32_t {
uint32_t index = 0;
do {
s[index++] = '0' + (value % 10);
value /= 10;
} while (value != 0);
for (uint32_t i = 0; i < index / 2; ++i) {
char temp = s[i];
s[i] = s[index - i - 1];
s[index - i - 1] = temp;
}
s[index] = ',';
return index + 1;
};
for (int i = 0; i < 65536; ++i) {
size_t offset = const_int_to_str(i, p);
p += offset;
off[i + 1] = off[i] + offset;
}
return {str, off};
}
|
实际上，我们并不需要存储偏移量。 我们可以非常经济地在运行中计算它们。 不过，这需要花费一些精力，除非内存紧张，否则最好还是计算偏移量，因为它们只需要 256 KB。
我编写了一个基准测试来查看预先计算数据需要多长时间。在我的 M2 MacBook 上，我得到了以下数字：
std::string 数组 0.57 毫秒 一个大字符串+偏移量 0.26 毫秒 |
尽可能将所有数据放在一起。