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,虽然要几天适应,但不用太久又能很熟练地使用。 图的存储...

论文阅读|图上的自监督学习——对比学习论文解读

前言 ​ 本文将围绕最近的一些在图上自监督学习的工作,对其中“Contrastive Learning”的内容进行一些解读,并包括一些自监督学习的思路。 ​ 首先,介绍一篇2020的综述《Self-supervised Learning: Generative or Contrastive》,其内容覆盖了CV、NLP、Graph三个方向自监督学习的成果。而本文会将主要目光放在Graph上的自监督学习。 ​ 文章将自监督学习主要分为三类:Generative、Contrastive、Adversarial(Generative-Contrastive)。目前,个人认为大部分Graph研究的目光都集中在Contrstive Learning上。个人拙见,原因可能与图学习的任务有关,图学习的任务主要集中在分类上(节点分类、图分类),对比学习天然会比生成学习更适用于分类任务,所以或许当生成满足某种性质的随机图任务成为主流之后,生成式模型就会成为主流。而对抗式(Adversarial)的学习,则会在生成式学习、对比式学习都达到瓶颈时,得到更好的发展。目前,在图领域,并未看到Adversarial Learning有惊人表现的文章。 ​ 当笔者初识自监督学习时,通过他人的介绍,仅理解为了一种利用自身性质,标注更多标签的一种手段,但随着论文阅读的增加,对自监督本质的理解越来越迷惑。个人理解,其实任意挖掘对象之间联系、探索不同对象共同本质的方法,都或多或少算是自监督学习的思想。原始的监督学习、无监督学习,都被目所能及的一切所约束住,无法泛化,导致任务效果无法提升,正是因为自监督探索的是更本质的联系,而不是表像的结果,所以其效果通常出乎意料的好。自监督学习的前两类方法,其核心想法其实都是想去探索事物的本质。 ​ 本文重点将放在Contrastive Learning的发展脉络上,对于Generative Learning将只结合《Self-supervised Learning: Generative or Contrastive》介绍一些粗浅的理解。 Generative Self-Supervised Learning 综述中主要介绍了四类基于生成式的自监督模型,最后一类是前三类模型的混合版,而在图学习领域,使用的比较多的应该是第三种,即AE的方法,在后文总结表格中有所体现,这里也就不对混合型生成模型进行描述了。 Auto-Regressive (AR)...

如何提高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...

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; }