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...
如何用 R Markdown 生成每周实验报告
背景 本科时，我主要交作业的报告，写成 HTML 文件，再转 PDF ，追求“花里胡哨”，让别人看起来很“认真”、很“高端”的感觉。用 Prettydoc写完全没问题，网页很容易加入特效。但 HTML 打印输出结果时，相信很多人都会遇到打印不完整的情况。转变为研究生和博士之后，有时依然需要每周给导师写报告。这时候，还像交作业一样给导师交花里胡哨的 HTML...
记一次 Prettydoc 的改造
声明 本文的出发点并不是鼓励去“剽窃” Prettydoc 包的成果，而是给一种比较小代价改造模板的流程介绍。 写文章有两种观点，一种叫天下文章一大抄，一种叫站在巨人的肩上可以看得更远。前者在抄袭的道路上越走越远，后者推陈出新发明出更多很有意思的事。(这里希望夹带一些私货，仅之前在统计之都发表了一篇关于 R Markdown 的文章，却发现各种平台未经允许直接转载，甚至有的转载不附加链接，这里必须澄清一点，不是在我个人博客或是统计之都看到我写的统计文章都属于抄袭，请联系本人，将采用发律手段解决。) 本文希望基于一个创作 R...
基于 R Markdown 的展示模板创建和使用
背景介绍 英语演讲课曾说，幻灯片只是辅助工具，更核心和本质的是演讲者的内容。报告和幻灯片，其本质都是服务于展示知识这个过程，两者有着相通之处，利用 R Markdown 可以特别方便地将一份课程报告转化为课程答辩幻灯片，展示幻灯片填充些内容也就是总结的报告，这四年来，利用两者的转换关系，为我节约了不少时间。 作为排版困难者，我尝试着探索了一些只关注内容的幻灯片和报告的写法，随着四年统计学习，R虽然已经快脱离我的常用语言名单，但我那利用 R Markdown 制作幻灯片和课程报告的经验还是不希望就随着我的不用而消亡。故记录下一些改装模板的经验。本文适合会 R...
“神抽”还是“鬼抽”?炉石发牌员偏好探究
背景介绍 《炉石传说》是一款集换式卡牌游戏，玩家根据自己现有的卡牌组建合适的卡组，驱动随从，施展法术，与对手一决高下。而作为一款卡牌游戏，除了自身收藏卡牌之外，取得胜负最为关键的一点在于，关键时候是否能抽到关键的卡牌。不少玩家吐槽炉石传说可能存在一个发牌员，为了增加玩家的游戏时间，对发牌机制做了控制，以达到鬼抽/神抽的目的。而实际上，炉石暗地里调整各种选牌概率也不是第一次了。例如：著名的竞技场11只剑龙骑术，极大的降低了玩家的用户体验。 笔者学习《实验设计》课程中，便希望能利用上课知识，为了验证网络上一直以来对发牌员偏好的猜测，开始了简单的实验。研究游戏动态过程过于复杂，所以以起手发牌换牌为例，完成一次简单的探究——炉石中的起手发牌规律。 一、实验设计 1.数据说明，为了探究抽牌上手的因素，将因变量确定为以下几类: 名称 数据记作 备注 “上手卡牌顺序” 记为”次序”...
空间多维数据展示--涟漪图
1. 研究问题 1.1研究问题背景 多年来，全国雾霾爆发，在地理空间上是否存在规律？2017年全国数学建模大赛提出给“拍照赚钱”任务定价，数据是否在位置上呈现一些规律？越来越多的研究定位在空间数据之上。 多维数据存在着展示上不直观的特点，数据容易“纠缠在一起”，想看出数据的变化规律、空间分布规律存在一定的障碍，通常人们将多维数据投影到二维上，但数据的“纠缠”仍然是比较难解决的，而展示多维数据的变化规律需要有一种能动态变化可视化手段。在看到水滴产生的涟漪、画画时颜色的相互交融时，突发灵感，提出一种新的可视化图——涟漪图。 1.2研究问题说明 多维分类型数据，分类的展示可以用点图轻松展示，但无法体现出多维分类数据的每一个分类的紧密程度，哪些分类间存在着“纠缠”，以及数据变化的主要方向。总的来说，多维数据是不能简单用每个维度的均值来衡量的，于是需要一种动态化展示的方法。 1.3数据说明 本次作业为了降低采集数据成本，使用2017年全国数学建模大赛的部分数据集，但制作涟漪图的核心在于中心点如何选取，目前采用的是kmeans方法，选取核心点，所以核心数据仅剩下两部分，经度、维度。对任意数据集，都可以使用二维投射，将点放置到二位图像中。 2....
记配置n遍spark多机分布式环境
背景 最近由于论文的关系，设计的算法需要在分布式环境下，测试算法的通信时间通信代价，于是尝试配置了多台机器的分布式环境。由于配置过程较为复杂，其中也遇到许许多多问题，由于各式各样的因素，不得不一直转换不同的环境，完成机器的配置。虽然由于水平不足，犯了许多不必要的配置错误，有的问题看起来比较愚蠢，但为了之后避免踩入相同的坑，也就将这一路以来，不断配置更新的过程写成文章，以方便查找。 配置20遍 最初使用的平台是人大校级计算平台，在这个平台上，可以申请一定数量的机器，然后以科研结果作为经费抵扣。使用此平台的原因是之前有前辈在上面配置过 Spark 环境，而我有一定机会可以直接利用他配置好的成果，然而事情并没有像我想象的那么简单。此时出现了两个主要的问题，其一是该环境并没有真正配置yarn，并不能做到真正的并行；其次实际上此平台的集群是在一个大机器上分割出的小虚拟机组成集群，这样的集群实际上的通信代价是非常低的，这无法体现出我们算法的优势，因此我不得不寻找其他平台。之后就在组里先找了6台服务器，直接利用这6台服务器搭建一个集群，虽然机器数目少一点，但平摊下来，每个机器都比原来的配置要更好。当然事情不会那么顺利，由于我实验操作的数据量极大，我不断试探服务器计算能力的上限，最终这些服务器也难堪重负，纷纷内存耗尽、磁盘耗尽，引发了一系列不好的连锁反应，究其原因是我没有做docker环境隔离（要学的东西还很多）。由于当时论文ddl在即，让我只能在夜间跑代码，完全是不可能完成目标的，因此我不得不使用阿里云下的服务器。之后就搞了16台阿里云服务器，并在上面配置真·分布式环境，此时我已经有了十次左右配置环境的经验，但哪怕如此，又经历了经费不足、神秘bug等等意想不到的问题，但我最终还是勉强完成了论文，初次投稿当然还是被拒了。之后改投论文的过程中，吸取了服务器可能很容易崩，随时可能换机器的现实，尽可能地将许多作业改为了批处理，终于又配置了很多次，最终完成了实验和论文。 分布式环境的成分 HDFS 虽然说使用 Spark...
读取Graph数据的代码
背景 记录读图的一些代码，由于图一般都会储存为稀疏矩阵的形式，否则大图根本无法储存，所以最终返回的都是稀疏矩阵，比较节约空间的是csr matrix。 CSR Matrix and COO Matrix COO Matrix...
一些乱七八糟的图片处理
背景 记录一些摸索图片处理过程中，看到的，和自己研究的图片预处理方法 图片移动 # 给定判断函数的批量图片移动 import shutil import os def...
Kmeans base on Cython
背景 Kmeans 是机器学习比较基础的算法，利用包调用比较容易，未来的算法可以很复杂，但基础都是一样简单的。算法层面尽量写得简单，将优化过程尽量写复杂。由于想使用Cython，先写C++部分，这里需要定义命名空间。头文件代码如下： 代码 KMeans.h #ifndef KMEANS #define KMEANS #include...
整理提取图片始
背景 这一切要从我清理手机开始说起，最大占用手机空间的内容当然是手机上的照片。糟糕的是，将照片传到计算机之后，照片就完全乱了，虽然之前也是一团乱麻。想到之前想存图片当壁纸，存了几万张照片，这次可以总结一下，用python对图片做些简单的分类。所以总的说，目标是尽可能提取高清的图片作为壁纸，必要时需要按风格分一下类。其次是手机上不需要的图片且质量差的，或者是无法打开的照片都清理掉。下面是清理过程中的代码： 简单整理图片的思路与实现 准备部分 #与图像处理相关的包 from PIL import Image import...
Python base skill
标准数据类型 与其他语言十分不一样的是python 封装的几种数据类型 六种数据类型 Number 不用理会浮点型、整数型、为计算带来很多方便，当然不足之处还是运算比较慢，容易不精准计算 String 字符串 从String库提供的字符串处理函数来说，python String相对于其他语言十分的方便和友好...
记配置n遍spark多机分布式环境
背景 最近由于论文的关系，设计的算法需要在分布式环境下，测试算法的通信时间通信代价，于是尝试配置了多台机器的分布式环境。由于配置过程较为复杂，其中也遇到许许多多问题，由于各式各样的因素，不得不一直转换不同的环境，完成机器的配置。虽然由于水平不足，犯了许多不必要的配置错误，有的问题看起来比较愚蠢，但为了之后避免踩入相同的坑，也就将这一路以来，不断配置更新的过程写成文章，以方便查找。 配置20遍 最初使用的平台是人大校级计算平台，在这个平台上，可以申请一定数量的机器，然后以科研结果作为经费抵扣。使用此平台的原因是之前有前辈在上面配置过 Spark 环境，而我有一定机会可以直接利用他配置好的成果，然而事情并没有像我想象的那么简单。此时出现了两个主要的问题，其一是该环境并没有真正配置yarn，并不能做到真正的并行；其次实际上此平台的集群是在一个大机器上分割出的小虚拟机组成集群，这样的集群实际上的通信代价是非常低的，这无法体现出我们算法的优势，因此我不得不寻找其他平台。之后就在组里先找了6台服务器，直接利用这6台服务器搭建一个集群，虽然机器数目少一点，但平摊下来，每个机器都比原来的配置要更好。当然事情不会那么顺利，由于我实验操作的数据量极大，我不断试探服务器计算能力的上限，最终这些服务器也难堪重负，纷纷内存耗尽、磁盘耗尽，引发了一系列不好的连锁反应，究其原因是我没有做docker环境隔离（要学的东西还很多）。由于当时论文ddl在即，让我只能在夜间跑代码，完全是不可能完成目标的，因此我不得不使用阿里云下的服务器。之后就搞了16台阿里云服务器，并在上面配置真·分布式环境，此时我已经有了十次左右配置环境的经验，但哪怕如此，又经历了经费不足、神秘bug等等意想不到的问题，但我最终还是勉强完成了论文，初次投稿当然还是被拒了。之后改投论文的过程中，吸取了服务器可能很容易崩，随时可能换机器的现实，尽可能地将许多作业改为了批处理，终于又配置了很多次，最终完成了实验和论文。 分布式环境的成分 HDFS 虽然说使用 Spark...
Java HelloWorld
Java HelloWorld //Helloworld.java public class HelloWorld{ public static void main(String...
EJB——Ant Demo——simple package
背景 简单的java情况下，使用命令行编译运行一个jar包的demo 目录结构 C:. │ mymanifest │ run.bat │ runjar.bat...