如何提高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) O(1) 稳定 插入排序 O(n) O(1) 稳定 希尔排序 O(1) 不稳定 堆排序 O(nlogn) O(nlogn) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(n)...

模式匹配之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; }