c++程序优化

2024-04-25 15:24:01
开发
26

一.问题带入：

最近在做一道用归并排列的排序的题，它是这样的：

输入n个数字a[i]，输出这些数字的第 k 小的数。最小的数是第 0 小。

刚开始，我以为这就是一道普普通通的排序题，于是：

#include<bits/stdc++.h>
using namespace std;
int a[50000005],b[50000005];
void mergesort(int l,int r){
	if(l>=r) return;
	int mid=(l+r)/2;
	mergesort(1,mid);
	mergesort(mid+1,r);
	int i=l,j=mid+1;
	int k=l;
	while(i<=mid&&j<=r){
		if(a[i]<a[j]) b[k++]=a[i++];
		else b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++];
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
	int n,k;cin>>n>>k;
	for(int i=0;i<n;i++){
		a[i]=read();
	}
	mergesort(0,n-1);
	cout<<a[k-1];
	return 0;
}

可是：

当我重新看这道题时，才发现了这个条件：

本题最多设计输入5000W个数字，需注意读入优化。

那，该怎么优化读入呢？

二.快速读入

对于cin输入来说，通常输入1000W个数字需要1s的时间，而scanf的输入效率比cin快约2-3倍，但依旧不够快。而众所周知，字符的输入速度比数字要快很多，所以我们可以先以字符的形式读入再转换成数字形式。

代码：

long long read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){//判断是否是数字字符（多用于判断空格和负号）
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){//将字符转换成数字
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

在经过排列的优化以及快读之后，上面那道题的正确代码就变成了这样：

#include<bits/stdc++.h>
using namespace std;
int a[5000010],n,k;
long long read(){//快读
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void f(int l,int r) {/排列
	if(l>=r){
		cout<<a[r];
		return;	
	} 
	int s=a[l],p=l;
	for(int i=l;i<=r;i++)if(a[i]<s)swap(a[++p],a[i]);
	swap(a[l],a[p]);
	if(p<k)	f(p+1,r);
	else f(l,p);
}
int main() {
	n=read(),k=read();
	for(int i=0; i<n; i++) a[i]=read();
	f(0,n-1);
	return 0;
}

三.其他优化方法：

当然c++它也有自带的优化方法，现在我就来讲解一下我们最常用的几种：

1.优化函数：

我们可以通过c++自带的优化函数进行优化，以下是我从各大网站上找来的各种优化函数：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma Gcc optinize("o1")
#pragma Gcc optinize("o2")
#pragma Gcc optinize("o3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize(1)
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#pragma GCC target("avx")

2.万能头文件：

在平常的编程中，我们也可以通过使用万能头文件降低复杂度。平常我们编程时经常需要这样：

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
using namespace std;
int main(){

    return 0;
}

但是用了万能头文件之后就变成了这样：

#include<bits/stdc++.h>
using namespace std;
int main(){

    return 0;
}

注：但是并不是所有OI竞赛都支持使用,所以还是不太推荐在竞赛上使用。

3.常量：

如果要存储一个在程序中不会改变的量，可以用常量来定义，比如：

const long long x=10000000000;
const int N=1000000;
int a[N];
const double esp=1e-6;

4.寄存器变量：

register 是 C++ 中的一个关键字，用于请求编译器将变量存储在寄存器中，以便提高访问速度。然而，在现代编译器中，通常不需要使用 register 关键字，因为编译器会自动进行优化。实际上，C++17 标准甚至已经移除了对 register 关键字的强制性要求。

使用 register 声明变量时与运用别的变量不同，它的语法如下：

register int myRegisterVariable;

在c++中，可以使用不同的方法啊呼出各种变量的纸。

输出整数：

int myInt =100000;
std::cout<<"Integer:"<<myInt<<std::endl;

输出浮点数:

float myFloat=3.14f;
std::cout<<"Float: "<<myFloat<<std::endl;

输出双精度浮点数:

double myDouble=2.718;
std::cout<<"Double: "<<myDouble<<std::endl;

输出字符:

char myChar='S';
std::cout<<"Character:"<<myChar<<std::endl;

输出字符串:

std::string myStrin ="Hello, World!";
std::cout<<"String:"<<myString<<std::endl;

四.总结

虽然这些优化可以帮助我们更好的做题，但是像#pragma GCC optimize(1)这样的优化函数在正式考试或比赛中是不能使用的。如果有超时的地方，那就证明自己的功力还不足，要继续努力。

感谢各位大佬的阅读！

原文地址:https://blog.csdn.net/Archie28/article/details/138072610 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1783396530171023360.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部