硬币问题(凑零钱) 动态规划

infinity = 9999
def coin_change(coins, a):
    dp = []
    '''初始化过程'''
    dp.append(0)
    min_amount = min(coins)
    for i in range(1, min_amount):
        dp.append(infinity);
    
    '''动态规划自底向上方法计算过程'''
    for i in range(min_amount, a + 1):
        min_count = infinity
        for c_j in coins:
            if i >= c_j and dp[i - c_j] + 1 < min_count:
                min_count = dp[i - c_j] + 1
        dp.append(min_count)
    return dp[a]

时间复杂度分析:求最小硬币面值(\(O(n)\))和初始化dp数组( \( O(1) \) )可以忽略不计,动态规划过程中有两层循环,外层最多执行a次,内层最多执行n次,因此该算法最坏的时间复杂度的 \( O(an) \)

空间复杂度分析 :dp数组所占用的空间为 \(O(a) \)

矩阵连乘

\(A_{n×p}\)和\(B_{p×m}\) 是两个矩阵,这两个矩阵进行相乘的乘法次数为n×p×m。那么考虑一共有N个矩阵进行连续乘法的时候,求最优的乘法次序,使得乘法的次数最少,前提是矩阵乘法满足结合律。

穷举法:所有乘法次序为(N-1)!种,代价太大。

贪心策略:容易观察,矩阵维度 n p p m 变为 n m ,如果p较大的会带来较大的乘法开销,所以我们希望在顺次确定第一步乘法是,贪心地优先消去最大的那个p。

如何确定该贪心策略是否是正确的,举个反例?

。上面是一个反例,这种贪心主要面对当一个最大维度周围是次大或者次次大维度时,造成一步的乘法次数剧增。因此这种贪心策略不满足最优条件。

逆向地思考问题,最优结构的乘法次序总有最后两个矩阵之间进行,可以这两个矩阵将原始矩阵序列划分为,两个子矩阵序列,那么这两个子矩阵序列的乘法序列也应该是最优的,否则与前提矛盾。因此这样思考,矩阵连乘存在最优子结构特性

具有最优子结构特性,那么就动态规划三步走。

最简单的方法,第一步:暴力搜索(通常是用递归来实现),遍历所有的可能,但是对于这个问题,最终的结果是各个步骤的累加,因此在暴力搜素中掺杂了回溯的思想。(自顶向下)

第二步,带有备忘录的暴力搜索,暴力搜索生成树中存在大量的重复子树,可以将已经计算的结果存下来,下次遇到直接取就可以了。 (自顶向下)

第三部,动态规划法(四个步骤) (自底向上)

  • 定义dp数组,这里用cost[i,j],表示矩阵i到矩阵j的最优的乘法次序的代价
  • 写出dp数组包含的最优子结构的递推关系
  • 确定问题的初始条件以及边界条件
  • 自底向上开始计算结果

算法课学习心得

首先明确数据结构在不同层面的意义。

数据结构可以理解为逻辑数据结构以及物理数据结构

逻辑数据结构例如数组,链表,二叉树层面上的逻辑结构,可以在纸面上画出来的结构

以二叉树这个逻辑结构为例子,在代码中用何种物理存储空间对二叉树进行建模就是物理数据结构。

例如,可以用数组物理结构对二叉树进行存储,同时利用数组下标以及以2为基础的乘除运算以及对数运算判断双亲,孩子节点以及树高等。

也可以用链表物理结构对二叉树进行存储,每个节点保存自身数据,左孩子指针以及右孩子指针。

当然逻辑结构对应dd不同物理结构在特定场景下效率各不相同。

Window 10 下 pytorch 安装(CUDA加速)

本人设备情况:Window10操作系统,显卡GTX750Ti(2G),另一张显卡HD 6570 (2G)。

A卡用来接显示器,N卡用来计算。两张显卡驱动都成功安装,没有发生冲突的情况。

首先是按照第一篇参考文献中的内容下载与显卡驱动版本,与操作系统类型以及位数(32/64) 匹配 的CUDA,然后进行安装,下载地址见参考文献2,N卡是否支持CUDA加速以及算力的查询见参考文献3。

第二部安装CUdnn,具体需要到参考文献4中进行下载,可能需要注册然后填写一个问卷。注意下载与CUDA版本匹配的Cudnn,然后将下载的内容解压到Cuda安装目录下的一个地方。

第三步安装pytorch,到参考文献5安装pytorch各项都匹配的pytorch,这里我用主流的conda工具进行安装。

建议安装在conda的虚拟环境之中

验证安装是否成功:

如何在jupyter notebook中对安装了pytorch的虚拟环境使用呢?

直接在anaconda 根用户中安装,nb_conda,基本上就可以了。

如果还不可以的话,再于装cuda加速pytorch的虚拟环境中安装ipykernel,就可以了。

references:

CUDA Toolkit 与 Pytorch 安装过程的一些坑

首先区别显卡驱动和CUDA Toolkit, 首先显卡做为一个硬件,需要驱动软件,才能保障显卡的基本正常工作。

在显卡驱动安装完成的基础上,再安装CUDA Toolkit 才能支持并行计算。但是显卡驱动版本和CUDA Toolkit版本之间是有要求的。

https://docs.nvidia.com/cuda/cuda-toolkit-release-notes/index.html

我之前装了半天pytorch,但是一直无法检查到cuda设备就是因为这个原因。

如何查看cuda版本以及驱动版本。

查看CUDA(将路径已经写入环境变量)

nvcc -V

查看显卡驱动版本

dpkg –list | grep nvidia-* 或者 cat /proc/driver/nvidia/version

我所使用的服务器cuda 版本是9.1, 显卡驱动版本时390,作为一个非管理员用户勉勉强强可以再自动的用户目录下成功装上支持GPU加速有的pytorch版本(0.4.1)。但是pytorch版本1.3都已经出来了,就想着可不可以再自己的用户目录下装一个高版本的CUDA ,然后用新版本的pytorch,那岂不是爽歪歪?

以下为尝试过程,但是失败了

原因是服务器的显卡驱动版本过低(390),与CUDA10.1版本不匹配,因此即使成功装上了pytorch 1.3,也检测不到cuda设备。

失败过程如下,如果你所使用的服务器显卡驱动版本较高,而你又是非管理员用户,又想用新版本pytorch的可以尝试一下。

https://developer.nvidia.com/cuda-downloads?target_os=Linux&target_arch=x86_64&target_distro=Ubuntu&target_version=1604&target_type=runfilelocal

下载CUDA Toolkit ,并安装,注意不要安装驱动的选项,因为你没有劝降,并且将其他安装路径都设置再用户目录以及子目录。

再自己目录下安装好CUDA10.1之后,要将CUDA相关的一些环境变量写入,以方便后续conda安装pytorch。可以参考这篇博客

接着利用conda创建虚拟环境进行pytorch安装,详见我的另一篇博客

https://pytorch.org/get-started/locally/

安装之后就是失败啦,torch.cuda.is_avialible() 返回的结果时False。

原因时服务器显卡驱动版本为390,而CUDA Toolkit 10.1要求显卡驱动版本>=418,只能让管理员去升级显卡版本啦。

Ubuntu 16.04 Cuda 9.1 安装支持gpu加速的pytorch

环境:Ubuntu 16.04 ,cuda 9.1,并且预装好了对应的Cudnn,如果服务器是多用户使用,这些是管理员完成的操作。

对于非root非管理员的用户,首先在自己的根目录下安装好Anaconda 3,网上有很多教程,安装anaconda3 也比较简单,不展开说了。

将系统根cuda的路径,配置到用户的环境变量中

然后用 source ~/.bashrc 来使用配置好的环境变量

接着使用conda包管理工具来安装gpu版本的pytorch

在之前将conda源改为国内的清华镜像源,这样下载过程中比较快。

conda config –add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/

conda config –add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main/

conda config –set show_channel_urls yes

利用conda包管理工具,创建一个名称为pytorch-gpu的虚拟环境,虚拟环境的python版本设置为3.6.

conda create -n pytorch-gpu python=3.6

进入虚拟环境中

source activate  

切换虚拟环境

conda activate pytorch-gpu

安装pytorch,这里安装版本匹配需要和pytorch匹配,因为cuda9.1不支持新版本的pytroch,安装版本不匹配则无法用cuda成功加速。

pip install torch==0.4.1

pip install torchvision==0.2.2

安装完成后则可以验证一下是否可用。

参考资料:

代码整洁之道(Clean Code)阅读笔记

本文介绍的内容来自于书籍,《Clean Code》Robert C. Martin 著 韩磊 译(中文名《代码整洁之道》),个人总结出一些比较重要的内容。

第一章

读写代码所花费时间的比例超过10:1。也就是说在写代码时,我们一直在读旧代码。既然比例如此之高,想让读变得轻松,编写代码就变得更难。不可能光写不读,易读即易写。

第二章

如果名称需要注释来补充,那就不算是名副其实。

魔术数最好不要出现,一些常量最好定义一些好的名称

名称满足非误导性(O和0,l和1等)、作有意义的区别(NameString和Name没有区别)、可读性(尽量用可读的单词)、可搜索性(提高查找效率)等

类名不应该为动词,方法名通常为动词或者动宾结构短语,命名也别弄一些语言梗。命名风格最好一以贯之。

取好名字最难的地方在于需要良好的描述技巧和共有文化背景。

第三章

函数最重要的就是要保持短小,避免嵌套层数过多,代码冗长,逻辑混乱

一个函数应该只做一件事,功能单一。

函数名称要具有描述性,参数尽量少,标识参数尽量不要有(分成两个函数),参数过多的换,是不是考虑封装成一个对象传入。

函数内部尽量避免时序耦合。

分隔指令与询问,防止代码语义的混淆,例子如下

if (set("username", "Amy"))....

if (attributeExists("username") {
setAttribute("username", "Amy")...

使用异常替代返回错误码,返回错误码会导致更深层次的嵌套结构,使用异常则能够将错误处理代码从主路径代码中分离出来。

同时通常错误码时一个枚举类型的数据,几乎所有文件都会引用它,如果使用java语言,当错误枚举类修改的时候,所有的类都需要重新的编译和部署。

使用异常替代错误码,新的异常可以从异常类派生出来,不需要重新编译或者部署。

Edsger Dijkstra 的结构化编程规则:每个代码只有一个入口一个出口,只有一个return,最好不要有break continue goto之类的语言,上述规则一般长、功能复杂函数中作用体现比较明显,原来函数就比较精简则帮助不大。

类中的函数位置应该根据调用关系,最好被调用函数直接放在调用函数的下方,这样可以提高阅读性,但不绝对。

怎么做:一开始的函数一般都冗长而复杂,逐步重构代码,分解函数,修改名称,消除重复。不要求一开始就按照各种条条框框的规则写函数,因为没有人会这么做吧。

第四章

别给糟糕的代码加注释——重新写吧

每次写注释,你都该对自己做个鬼脸,感受自己再表达能力上的失败。

用代码来阐述你的故事:

//Check to see if the employee is eligible for full benefits
if ((employee.flags & HOUURLY_FLAG) && (employee.age > 65)) ....

if (employee.isEligibleForFullBenefits()) ...

当然有些注释是必须的,也是有利的,唯一真正好的注释是你想办法不去写的注释。

一些很长的函数往往会有很多注释,然而这又回到了写一个好的函数的问题,把函数写短就可以避免无用的注释。短的函数根本不需要注释,一个好的函数名比注释好一万倍。

注释代码可以再短时间测试的时候使用,但是需要及时清理,否则久了,这些代码会腐烂。

第五章

代码格式中,再导包的声明,每个函数之间都应该有空行分隔开

你是否曾经再某个类中摸索过,从一个函数跳到另一个函数,上下求索,想要弄清楚这些函数的操作,如何互相相关,最后却被搞糊涂了。

关系密切的概念应该相互靠近。

相关函数。若某个函数调用了另一个,就应该把他们放到一起,而且调用者应该尽可能放在被调用者的上面。

编码格式中的风格。下面的代码时本人编码格式的一些样式:

public class Student {
public String name;
void setName(Strint name) {
int sum = 0;
for (int i = 0; i < 10; i++)
sum += -i * 5;
this.name = name;
}

通常再非末尾的符号之后会有一个空格,这也是英文文本的基本格式要求(不排除一些特殊情况,如”(“后面一般不加空格)。二元操作符,前后都加空格。一元操作符,通常不加空格;if、while、for 之类的关键词后面也加空格,函数名称与”(“之间不加空格。

团队工作,统一风格,个人服从于集体。

第六章

暴露给用户的通常时比较抽象的功能就可以,而不需要将底层的逻辑暴露,用户也不会去关心的。

如果用户关心当前汽车还剩多少油,直接返回当前剩余油量的百分比就可以,可不需要将获取汽车油量上限,获取汽车当前油的余量,两个接口不需要暴露出来。

我们不愿意暴露数据细节,更愿意以抽象形态表述数据。

面向对象和面向过程:面向过程便于在不改动既有数据结构的前提 下添加新函数,面向对象便于在不改动既有函数的前提下添加新类(多态)。

第七章

尽量使用异常机制,不要使用错误标识码。虽然异常机制可能比较丑。异常抛出尽量要将信息一并传递出去。别传递null值,这样就不用花费精气去检查null值了。

第十章

保持类的内聚性,将较大的函数切割为小函数会导致更多的类出现。在拆分函数时,需要将变量提升为类的实体变量,这样就不需要写函数之间的参数传递了。

第十一章

一开始就做对系统纯属神话,我们应该只去实现今天的用户故事,然后重构,明天再拓展系统,实现新的用户故事,这是迭代和增量敏捷的精髓所在。

第十二章

简单设计规则:运行所有测试,全面测试并持续通过所有测试的系统,就是可测试的系统。不可测试的系统同样不可验证,不可验证的系统就不应该部署。

简单设计规则:重构。测试消除了对清理代码就会破坏代码的恐惧。重构过程中应该提升内聚降低耦合,消除重复,保证表达力,尽可能减少类和方法的数量。

做到有表达力重要方式就是尝试,因为下一位读代码的人最有可能就是你自己。所以,要多尊重自己的手艺,花一点点时间再每个函数和类上。选用较好的名称,将大函数切分成小函数,时不时看看自己所创造的东西。用心是最珍贵的资源。

第十三章

不要将系统错误归咎于偶发事件,系统(编译里)出错的概率远比你自身编程出现缺陷的概率低。并发代码难写,加入多线程和共享数据后,简单的代码也会变成噩梦。要编写并发代码,就得严格的编写整洁的代码,否则将面临细微和不频繁发生的失败。因为偶发事件往往是再高负载下出现的。

第十四章

保持代码持续整洁和简单,永不让腐坏有机会开始。

第十五章

重构常常会导致另一次推翻此次重构的重构。重构是一种不停试错的迭代过程。

Ubuntu18.02下Docker+WordPross+MySQL 环境搭建

本人近来在阿里云上搞了一台云主机,然后想用来搭建个人博客,用于记录所学所想。

下面简单介绍一下搭建的过程。

建议环境搭建过程使用root账号或者管理员账号。

首先是利用阿里云的源安装docker-ce

apt update # apt full-upgrade -y

# apt install apt-transport-https ca-certificates curl software-properties-common -y

# curl -fsSL http://mirrors.cloud.aliyuncs.com/docker-ce/linux/ubuntu/gpg | apt-key add –

# add-apt-repository \ “deb [arch=amd64] http://mirrors.cloud.aliyuncs.com/docker-ce/linux/ubuntu \ $(lsb_release -cs) \ stable”

# apt update

# apt install docker-ce -y

运行命令docker -v

查看docker的版本号,显示出了版本号说明安装成功。

然后从docker库,下载wordpress和mysql的镜像

docker pull wordpress:latest

docker pull mysql:5.6

这里选取了5.6版本的mysql,本人尝试过安装最新8.1版本的mysql,但是后续建站会报错,因此选择了一个比较稳定的版本。

接下来在docker启动容器

docker run -d –name wp_mysql -v /root/mysql-data:/var/lib/mysql -e MYSQL_ROOT_PASSWORD=你的密码 mysql:5.6

参数解释, docker run 表示运行容器;末尾的mysql:5.6表示将之前下载好的镜像在该容器中运行,并且将这个容器命名为wp_myusql; -d表示后台运行,而不是交互式运行的状态。 -e MYSQL_ROOT_PASSWORD=你的密码:指定容器的环境参数,此处初始化mysql的root密码; -v /root/mysql-data:/var/lib/mysql 表示将宿主机的目录 /root/mysql-data 挂载到容器中的 /var/lib/mysql 目录下。

docker run –name wp_wordpress -d -p 80:80 –link wp_mysql:mysql -v /root/wordpress-html:/var/www/html wordpress

大功告成

一些其他命令

docker ps -l

docker stop

docker rm

参考文献

https://my.oschina.net/taadis/blog/1569239

极大似然估计与极大后验估计

极大似然估计(MLE,Max Likelihood Estimation)

极大后验估计(MAP, Maximum A Posteriori probability estimation)

似然函数与概率函数的区别 \(p(x|\theta)\)

频率学派和贝叶斯学派

先验与后验

贝叶斯估计

先验与后验共轭是贝叶斯估计问题可以进行简化

贝叶斯预测中的解构\(P(\hat{x}|X)\)

贝叶斯估计与贝叶斯预测

先占个坑,详细的内容后续有时间再填完