为大无符号整数分配内存的有效方法

Question

我写了一个 C++ class 用于包含最多 10^5 个十进制数字的大无符号整数，它有一个 BASE = 10^9 和 std::vector<long long> 里面存储实际数字 -

例如 754564575693573452 存储为

std::vector<long long> number = {693573452, 754564575}

在构造函数中，我调整此向量的大小以始终包含一些固定数量的 long long 数字，假设它是 10^5，因此两个大单位的一次加法最多可以有 10^6 数字（在 BASE = 10^1 数字系统中是 9 * 10^6 位），乘法也类似...

所以所有算术运算的速度都提高了 9 倍，但这仅在对大数进行少量计算时才注意到，对于大量计算的情况，性能会降低，这是因为 class设计，我的构造函数和默认构造函数总是调用resize函数，就像我之前说的，这是线性时间例程。

void Big_uint::read_num_str(const std::string& num_str)
{
    // reading from num_str to number
}

Big_uint::Big_uint(const std::string& num_str = "0")
{
    number.resize( 1000000 );
    read_num_str(num_str);  
}

Big_uint::Big_uint(const long long& num)
{
    number.resize( 1000000 );
    char buff[ 20 ];
    _itoa_s(static_cast<int>(num), buff, 10);
    std::string s = buff;
    read_num_str(s);    
}

所有的算术运算都是这样实现的

Big_uint operator + (const Big_uint& left, const Big_uint& right)
{
    Big_uint res; // resize() called here to initialize a vector
    // add algorithm
    return res; 
}

Big_uint operator * (const Big_uint& left, const Big_uint& right)
{
    Big_uint res; // resize() called here to initialize a vector

    // some multiplication algorithm here (currently only naive O(n^2) implemented)

    return res; 
}

因此，它们变得效率低下。

如何根据运算符重载中的输入来初始化矢量？

我不想将运算符重载更改为成员函数，如 add, mul, div 并向它们传递 3 个参数，其中第三个参数是 res - 预分配的零初始化 Big_uint 来存储二元运算的结果。

Answer 1

您不应该以这种方式预分配存储空间。根本不要预分配。在每次操作中，您（大约）知道结果的大小。对于 add，它是输入大小的最大值加一。对于 mul，它是输入大小的总和。始终尝试只分配必要的 space 来容纳号码。

所以，默认构造函数根本不应该分配。每个其他构造函数都应检查输入的大小，并分配必要的 space。运营商应该（保守地）估计必要的 space，并相应地进行分配。

旁注：您应该使用基数 2^32 而不是 10^9（或 64 位机器上的 2^64）：它的内存消耗略少，性能会好得多。

旁注 2：sizeof(long long) 通常为 8，因此如果您只在其中存储小于 10^9 的数字，则会浪费内存。

为大无符号整数分配内存的有效方法

Efficient way of allocating memory for big unsigned integer

c++

optimization

performance

biginteger