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

背景 这两年来，主要精力集中在使用c++做矩阵计算上，由此总结了一些c++的优化手段，虽然可能几年以后会对现在的水平嗤之以鼻，但至少可以记录一下自己的编程水平增长经历，以下希望随时间持续更新。 所谓代码的优化，个人认为有三个方面：更快，更省，更好看。快指的是时间少，省指的是省空间，好看指代码简洁。这三者有时候会有冲突，而我所追求的则是达到三者的平衡，有时甚至可以兼顾三者，个人的水平毕竟是有限的。对于尚未工作的我来说，更深层次的优化其实掌握得并不多，目前使用的优化，或许也仅限于单机以及平日研究所用。 底层优化 底层优化是我掌握得比较浅薄的方法。其核心在于利用计算机的金字塔物理结构，提高运算效率。CPU运算速度非常快，但数据在外存，也就是磁盘上，而计算通常都是发生在CPU，一个程序，分为计算密集型和io密集型，我通常面对的任务都是计算密集型，所以重点在于充分利用CPU。这里可以存在的优化有： 读写文件优化 通常网上教读写文件的方式是利用fstream，将文件转化为数据流，之后再按照数据类型，一个个地读入和转化数据，这里的优化就可以利用内存和缓存，先将所有的数据读入到内存，之后再进行数据的转换。两种代码如下： int n; ifstream...

读取Graph数据的代码

背景 记录读图的一些代码，由于图一般都会储存为稀疏矩阵的形式，否则大图根本无法储存，所以最终返回的都是稀疏矩阵，比较节约空间的是csr matrix。 CSR Matrix and COO Matrix COO Matrix...

如何提高Eigen效率

背景 为了加速c++的矩阵计算，MKL是比较好的方案，但MKL写代码实在不太友好，其次容易出bug。MKL计算矩阵乘法速度十分快，但其实对代码优化到极致之后，Eigen矩阵计算速度是可以和MKL媲美的。由此，我也对CMake进行了一定的研究。我主要是从知乎Eigen的速度为什么这么快？中学习到的。我仅作为搬运工，并加入一些自己的实际探索。 优化手段 从知乎中总结： 矩阵乘法，若等式左边的变量与右式相乘变量没有关系，则可以使用 A.noalias() 替代 A -mavx 和...

MKL 的坑与教训

背景 为了加速c++，不可避免的需要使用矩阵运算库。最出名的、一般人用的最多的c++矩阵计算库可能是Eigen，从统计处我知道了Armadillo用的也不少。但说到底，python那些包用的最多的也许最后还是MKL。 MKL全称 Intel Math Kernel Library， 是由Intel 公司开发的，专门用于矩阵计算的库。这个库经过我自己的评测，性能远超 Eigen...

Kmeans base on Cython

背景 Kmeans 是机器学习比较基础的算法，利用包调用比较容易，未来的算法可以很复杂，但基础都是一样简单的。算法层面尽量写得简单，将优化过程尽量写复杂。由于想使用Cython，先写C++部分，这里需要定义命名空间。头文件代码如下： 代码 KMeans.h #ifndef KMEANS #define KMEANS #include...

Alias算法

问题描述 O(1)时间内产生离散随机数的方法。 class Alias{ public: double* p; int* h; int*...

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

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

模式匹配之KMP算法

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

C and C++ HelloWorld

第一篇博客 关于 Hello World C #include<stdio.h> int main(){ printf("HelloWorld"); return...

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

NOTE: This markdown cheatsheet is a typography demo for this...