在 C++ 中添加 int 数据类型和自定义 class 数据类型以获得更高的性能

Question

我自己制作了 class long_number 来进行比 long long int 更大的数字的数学运算（用于素数目的等）。现在我正在测试添加并比较以下代码的速度：

#include <iostream>
#include <cmath>
#include <vector>
#include <typeinfo>
#include <string>
//#include "long_number.h" the header is below
#include <chrono>

using namespace std;
using namespace ln;

typedef long long int Te;
typedef long_number Se;

int main()
{

    // Start measuring time
    
    vector<Te> numbers;
    string s = "";
    for(int i=1;i<15;i++)
    {
        s.append(to_string(i));
        numbers.push_back(stoll(s));
    }
    auto begin = std::chrono::high_resolution_clock::now();
    Te sum=0; 
    for(int k=0;k<=5000;k++)
    {
        sum=0;
    for(int j=1;j<=7;j++)
    for(int i =0;i<numbers.size();i++)
        sum +=numbers[i];
    }
    cout << "Sum " <<sum <<endl;
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    printf("Time measured: %.6f seconds.\n", elapsed.count() * 1e-9);

    vector<Se> numbers2;
    string se;
    for(int i=1;i<15;i++)
    {
        se.append(to_string(i));
        numbers2.push_back((Se)stoll(se));
    }
    begin = std::chrono::high_resolution_clock::now();
    Se sum2=0;
    for(int k=0;k<=5000;k++)
    {
        sum2=0;
    for(int j=1;j<=7;j++)
    for(int i =0;i<numbers2.size();i++)
        sum2 += numbers2[i];
    }
    cout << "Sum " <<sum2 <<endl;
    end = std::chrono::high_resolution_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
     printf("Time measured: %.6f seconds.\n", elapsed.count() * 1e-9);
    return 0;
}

使用 g++ main.cpp -Wall -O3 -std=c++17 -o 程序打印以下结果：

Sum 8729267916327544355
Time measured: 0.000474 seconds.
Sum 8729267916327544355
Time measured: 0.677444 seconds.

你可以看到，int加法大约快了1000倍。我的 class long_number 如下：

#include <iostream>
#include <cmath>
#include <vector>
#include <typeinfo>
#include <string>


using namespace std; 

namespace ln
{
//stores long integers in vector, 0th position means 10^0 -> reversed order, using for operation of huge nubers overnight 
class long_number
{
private:

public:
vector<unsigned int> numero = {};//every component store one digit of the number
unsigned int size = 0;//size of the numero - how many digit has the number

long_number() {};//default constructor


void zero_check()//checks and remuves zero digits from the left of the number
{
    while(numero[numero.size()-1]==0&&numero.size()>=2)
    {
        numero.pop_back();
        size--;
    }
    size = numero.size();
}


operator unsigned int() const //conversion form long_number to int
{  
    //cout << "typecast operator unsigned int() used" << endl;
    unsigned int num=0;
    for(unsigned int i=0;i<size;i++)
        num += numero[i]*pow(10.,i);
    return num;
}       


template<typename numb>
long_number(numb a)//constructor
{
    string b = to_string(a);
    read(b);
}

long_number(const long_number& a)//copy constructor
{
    numero = a.numero;
    size = a.numero.size();
}

int ssize() const
{
    return (this->numero).size();
}


void set_size(int i)
{
    (this->numero).resize(i);
}
void get (ostream& out) const;//historic function to print the long_number
void read(string input); //historic function to declare long_number
vector <unsigned int> get_numero() const //not necessary cauz all is public
{
    return numero;
}
void set_numero(int num,int pos)
{
numero[pos]=num;
}





long_number& operator+=(const long_number& b)//defined by the binary operator +
{
    long_number a= *this;
    *this = (a + b);
    return *this;
}



template <typename numb>
long_number& operator=( numb b)// I don't know why is this here
{
    string s = to_string(b);
    this->read(s);
    return *this;

}


~long_number(){}//destructor

//this is here to get acces inside the operators to another operators
//it should work also without this according to
//https://www.learncpp.com/cpp-tutorial/9-2a-overloading-operators-using-normal-functions/
//because all is public but it doesnt
friend long_number operator + ( const long_number&,const  long_number&);

};

long_number operator+ (const long_number& a, const long_number& b)//sum of two long_numbers
{   
    long_number res;
    int ten = 10;
    int a_size=a.get_numero().size();//size of number a
    int b_size=b.get_numero().size();//size of number b
    res.set_size(max(a_size,b_size)+1);
    int rest = 0; //stores the rest when adding over ten
    for(int i=0;i<min(a_size,b_size);i++)//part where both numbers have digits
    {
        res.set_numero((a.get_numero()[i]+(b.get_numero())[i]+rest)%ten,i);//sum of digits,
        rest=((a.get_numero())[i]+(b.get_numero())[i]+rest)/ten;// rest is saving suming over 10

    }
    if(a_size>b_size)//to find which number is greater
    for(int i=min(a_size,b_size);i<a_size;i++)//part where one numbers has no digit -> is less
    {
        //res.get_numero().push_back((a.get_numero()[i]+rest)%10);//set zero at the higher positions of the smallest number
        res.set_numero((a.get_numero()[i]+rest)%ten,i);
        rest=((a.get_numero())[i]+rest)/ten;
    }   
    else
    for(int i=min(a_size,b_size);i<b_size;i++)
    {
        //res.get_numero().push_back(((b.get_numero())[i]+rest)%10);
        res.set_numero(((b.get_numero())[i]+rest)%ten,i);
        rest=((b.get_numero())[i]+rest)/ten;
    }
    if(rest!=0)//if the result has more digit than the greatest partner
    {
        //res.get_numero().push_back(rest);
        res.set_numero(rest,max(a_size,b_size));
    }
    if((res.numero[(res.numero).size()-1])==0)//reduces zero digit from left if possible
        (res.numero).erase((res.numero).end()-1);
    
return res;
}

ostream& operator<< (ostream& out, const long_number& num)//output of the number
{
    for(int i=(num.numero).size()-1;i>=0;i--)
    {
        out << (num.numero)[i];
    }
    return out;
}

void long_number::read(string input)
{
    //if(this->numero)
        this->numero.erase(this->numero.cbegin(),this->numero.cend());
    string s;
    if(typeid (input)== typeid (string))
        string s = input;
    else
        ;
    //string s = to_string(input);
    for(int i=input.size()-1;i>=0;i--)
        (this->numero).push_back(input[i]-'0');
    this->size = (this->numero).size();
}

void long_number::get(ostream& out) const
{
    for(int i=(this->numero).size()-1;i>=0;i--)
    {
        out << (this->numero)[i];
    }
    //out << endl;
}
}

我知道有更快的求和算法，但我使用的是标准的逐位求和，但我没想到差异会这么大。速度真的是算法给定的吗？与标准数据类型相比，可以达到的最大速度是多少？在我的代码中是否有任何可以更好地优化以加速代码执行的地方？或者我可以在编译器命令中使用更多标志以获得更高的性能吗？

真的很感谢每一个帮助让我前进的人！！！弗兰克

Answer 1

您的 long_number operator+ 可以通过消除 get_numero() 中向量的多个副本轻松改进。

你真的不需要复制你的向量然后询问它的大小。只需为您的 class.

提供一个 size() 方法

类似地，实现 operator [] 以直接访问单个数字，而不是 (a.get_numero())[i]（同样，在对它进行索引之前复制整个向量）。

增加的时间是原来的 1,000 倍 - 很多！但是，预计会出现大约 100 次 - 只需计算您有多少步来代替简单的 add 指令

在 C++ 中添加 int 数据类型和自定义 class 数据类型以获得更高的性能

Addition between int datatypes and custom class datatypes in c++ to get higher performance

c++

performance

addition

unsigned-long-long-int