2019-2020 领悟的优化 基于c++

背景 这两年来,主要精力集中在使用c++做矩阵计算上,由此总结了一些c++的优化手段,虽然可能几年以后会对现在的水平嗤之以鼻,但至少可以记录一下自己的编程水平增长经历,以下希望随时间持续更新。 所谓代码的优化,个人认为有三个方面:更快,更省,更好看。快指的是时间少,省指的是省空间,好看指代码简洁。这三者有时候会有冲突,而我所追求的则是达到三者的平衡,有时甚至可以兼顾三者,个人的水平毕竟是有限的。对于尚未工作的我来说,更深层次的优化其实掌握得并不多,目前使用的优化,或许也仅限于单机以及平日研究所用。 底层优化 底层优化是我掌握得比较浅薄的方法。其核心在于利用计算机的金字塔物理结构,提高运算效率。CPU运算速度非常快,但数据在外存,也就是磁盘上,而计算通常都是发生在CPU,一个程序,分为计算密集型和io密集型,我通常面对的任务都是计算密集型,所以重点在于充分利用CPU。这里可以存在的优化有: 读写文件优化 通常网上教读写文件的方式是利用fstream,将文件转化为数据流,之后再按照数据类型,一个个地读入和转化数据,这里的优化就可以利用内存和缓存,先将所有的数据读入到内存,之后再进行数据的转换。两种代码如下: int n; ifstream infile(path); infile>>n; int n; ifstream fin(path,std::ios::binary); std::vector<char> buff=vector<char>(fin.seekg(0,ios::end).tellg()); fin.seekg(0,ios::beg).read(&buff[0],static_cast<std::streamsize>(buff.size())); fin.close(); stringstream infile; std::copy(buff.begin(),buff.end(),std::ostream_iterator<char>(infile)); infile>>n; std::vector<char>().swap(buff);//释放内存 减少cache miss 减少cache miss,其核心想法就是,当CPU在计算的时候,需要的变量都在内存里。这件事其实对人脑也适用,例如大部分人其实都不太能一心两用,更不必说反复切换。如果编写了一分钟c++代码,又迅速切换到python,再迅速切换到java,这样有可能会造成用法的混乱,但是要是一个月都在编写c++,那么这个月写c++都是比较通畅的,再切换python,虽然要几天适应,但不用太久又能很熟练地使用。 图的存储...

读取Graph数据的代码

背景 记录读图的一些代码,由于图一般都会储存为稀疏矩阵的形式,否则大图根本无法储存,所以最终返回的都是稀疏矩阵,比较节约空间的是csr matrix。 CSR Matrix and COO Matrix COO Matrix 比较容易理解。从图的角度出发其实就是将每条边都存下来。 要想压缩数据,无论什么方法,其实都是在合并同类项。COO Matrix有什么好压缩的呢?单个顶点出发的边可以将它们的顶点合并,用一个数表示。最终也就得到了CSR Matrix。 CSR Matrix可以理解为,先对顶点都预先编号为0-V,那么只需要记录一下,每个顶点有多少出边和出边的位置即可。CSR Matrix由三个数组构成:offsets、edges、values。有时候,offsets 在某些函数输入会拆分为 PointerB 和 PointE,意思也很简单,即某顶点开始时,已经记录边的数量,和此顶点结束时,会记录边的数量。至于 edges 记录的是边的终点,values 记录边的权重。对 CSR Matrix理解的程度决定了,你能对矩阵计算所沉浸的深度,利用CSR进行图的访问和计算是非常方便的,要使有机会写到 MKL 矩阵运算库的解析,会有更深的理解。 Python 部分...

如何提高Eigen效率

背景 为了加速c++的矩阵计算,MKL是比较好的方案,但MKL写代码实在不太友好,其次容易出bug。MKL计算矩阵乘法速度十分快,但其实对代码优化到极致之后,Eigen矩阵计算速度是可以和MKL媲美的。由此,我也对CMake进行了一定的研究。我主要是从知乎Eigen的速度为什么这么快?中学习到的。我仅作为搬运工,并加入一些自己的实际探索。 优化手段 从知乎中总结: 矩阵乘法,若等式左边的变量与右式相乘变量没有关系,则可以使用 A.noalias() 替代 A -mavx 和 -mfma 两个参数, 若对g++ 编译而言, -O3 可以在编译上优化 写 CMakefile 并链接矩阵加速库 MKL 、 Blas 、Lapack 。 这些都是比较容易实现达到的优化方法。主要讲一下利用MKL优化。 参考资料 [1] https://www.zhihu.com/question/28571059

MKL 的坑与教训

背景 为了加速c++,不可避免的需要使用矩阵运算库。最出名的、一般人用的最多的c++矩阵计算库可能是Eigen,从统计处我知道了Armadillo用的也不少。但说到底,python那些包用的最多的也许最后还是MKL。 MKL全称 Intel Math Kernel Library, 是由Intel 公司开发的,专门用于矩阵计算的库。这个库经过我自己的评测,性能远超 Eigen 和Armadillo,毕竟Eigen 和Armadillo属于开源库,下载方便,但功能其实远不够完善。MKL其实不算免费使用的库,学生可以申请,之所以重新开始写这篇文章,正是因为一年前,我申请的linsence过期了。逼于无奈,我必须另辟蹊径,重新安装和配置这个库。过期的根本原因是MKL的特殊编译器icc过期,但本身MKL的库是可以下只含有MKL部分的版本,方法是选择单独下载 Intel® Math Kernel Library,这里需要下载对应系统的MKL文件,当注册之后,Intel会自动发送可用的lisense到邮箱,这里就不做展示。于我而言,为了方便本地测试,和服务器运行代码,我既配置了MAC的版本也配置了linux的版本,MAC版本的配置相对简单,下载dmg文件后,根据提示安装即可。 使用parallel_studio的配置要稍显简单,只需要在得到license之后,按照安装步骤来即可,麻烦的是得到安装软件的license。只有短期需求时,比较推荐的做法是注册学生账号,以学生身份使用并安装parallel_stduio,结果也许会是license的过期,那时若对MKL仍抱有好感,只需重读此文即可。 编译和配置 安装完成后,会有产生目录:/opt/intel/,一般会有下面几个重要的文件夹: compilers_and_libraries compilers_and_libraries_20XX compilers_and_libraries_20XX.X.XXX mkl 这些就是MKL安装和链接的库和关键。为了在g++编译的时候找到这些库的位置并连接上,需要使用以下的语句: source /opt/intel/mkl/bin/mklvars.sh intel64 source /opt/intel/bin/compilervars.sh intel64...

Kmeans base on Cython

背景 Kmeans 是机器学习比较基础的算法,利用包调用比较容易,未来的算法可以很复杂,但基础都是一样简单的。算法层面尽量写得简单,将优化过程尽量写复杂。由于想使用Cython,先写C++部分,这里需要定义命名空间。头文件代码如下: 代码 KMeans.h #ifndef KMEANS #define KMEANS #include <iostream> #include <Eigen/Dense> using namespace std; using namespace Eigen; namespace cluster { class Kmeans{ public: size_t n_cluster; int max_iter; double...

Alias算法

问题描述 O(1)时间内产生离散随机数的方法。 class Alias{ public: double* p; int* h; int* map1; int* map2; int n; Alias(vector<pair<int, double> > pi){ double sum = 0; n = pi.size(); stack<int> small; stack<int> big;...

各式排序算法及其c语言实现

问题描述 排序算法可以说是算法的一个基础,这里在我水平范围内进行总结和归纳,并给出我自己实现的源码。 以下,归纳基于比较的排序方法,因此,其运行时间上限基本都是O(nlog(n)) 时间对比 排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性 冒泡排序 \(O(n^2)\) O(n) \(O(n^2)\) O(1) 稳定 插入排序 \(O(n^2)\) O(n) \(O(n^2)\) O(1) 稳定 希尔排序 \(O(nlogn)~O(n^2)\) \(O(n^{1.3})\) \(O(n^2)\) O(1) 不稳定 堆排序 \(O(nlogn)\)...

模式匹配之KMP算法

#问题描述 模式匹配:字串的定位操作通常被称为串的模式匹配 最简单的模式匹配方式:从主串S的第pos个字符起和模式的第一个字符比较之,若相等,则继续逐个比较后续字符;否则从主串S的下一个字符起再重新和模式的字符比较之。依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式T中第一个字符相等的字符在主串中的序号,否则称匹配失败。 模式匹配的改进算法 D.E.Knuth 、V.R.Pratt 和 J.H.Morris同时发现,其算法的本质改变在于:每当一趟匹配过程中出现字符比较不等时,不需要回溯指针,而是利用已经得到的部分匹配结果将模式向右移动尽可能远的一段距离后,继续进行比较。 在此不对算法本身做太多阐述,网上有很多说明,仅仅是,完成我自己在理解此算法之后,写出相应的代码。 求next与nextval与匹配 #include<stdio.h> #include<string.h> #include<malloc.h> #include<memory.h> #include<time.h> void Next1(char *pattern, int next[]){ int length=strlen(pattern); *(next)=0; *(next+1)=1; for(int i=2;i<length;i++){ int aim=i-1; while(pattern[i-1]!=pattern[next[aim]-1]){ aim=next[aim]-1;...

C and C++ HelloWorld

第一篇博客 关于 Hello World C #include<stdio.h> int main(){ printf("HelloWorld"); return 0; } C++ #include<iostream> using namespace std; int main(){ cout<<"HelloWorld"<<endl; }

For Example of very Long Title Would Be Typography Elements in One

NOTE: This markdown cheatsheet is a typography demo for this theme. Check out this post to learn more about this markdown usage when you want to get started with this...