分类 技术 下的文章

算法导论-动态规划-笔记

动态规划:找其中一个最优解
4个步骤来设计
1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值,通常是自底向上的方法
4.构造解

适合用动态规划求解的最优化问题,应具备两个要素:
最优子结构、子问题重叠

对于不同问题领域,最优子结构的不同 体现在两个方面:

  1. 原问题的最优解中涉及多少个子问题
  2. 在确定最优解使用哪些子问题时,我们需要考察多少种选择

动态规划 vs 贪心算法
能够应用贪心算法的问题也必须具有最优子结构性质。两者不同之处是:
动态规划,首先寻找子问题的最优解,然后在其中选择
贪心算法,首先做一次“贪心”选择————在当时(局部)看来最优的选择————然后求解选出的子问题,从而不必求解所有可能相关的子问题

贪心算法两个关键要素:
贪心选择性质
最优子结构

proftpd配置备忘

proftpd看似很简单、很强的ftp服务器,但是想快速配置、运行起来,却不太直观。

我的两个使用场景:
1.Mac开发 FTP代码同步到Linux开发机,在服务器中运行程序
2.给其他人共享一些文件

./configure
make
make install
三步骤完成后,怎么配置,才能正常跑起来?
这里分享一个同事写的shell脚本,命名为init.sh

#!/bin/sh

CURPATH=`cd $(dirname $0);pwd`

authmsg=$(id)

#uid=506(quanjing)
suid=$(echo $authmsg|awk -F' ' '{print $1}')
#gid=505(map)
sgid=$(echo $authmsg|awk -F' ' '{print $2}')

uid=$(echo $suid | awk -F'=' '{print $2}' | awk -F'(' '{print $1}')
gid=$(echo $sgid | awk -F'=' '{print $2}' | awk -F'(' '{print $1}')

uname=$(echo $suid | awk -F'(' '{print $2}' | awk -F')' '{print $1}')
gname=$(echo $sgid | awk -F'(' '{print $2}' | awk -F')' '{print $1}')


echo "uid $uid uname $uname gid $gid gname $gname";

proconf="$CURPATH/etc/proftpd.conf"

## 替换配置文件
function editconf()
{
opt="$1"
#sed -i "s/^.$opt[[:space:]]*.*/$opt     $2/" $proconf
sed -i "s#^\s*[#]*\s*$opt\s.*#$opt      $2#" $proconf
#echo "sed -i \"s/^\s*[#]*\s*$opt\s*.*/$opt $2/\" $proconf"
}

editconf "User"   "$uname"
editconf "Group"  "$gname"

editconf "DefaultRoot"  "$HOME"

editconf "AuthUserFile"        "$CURPATH/var/ftpd.passwd"
editconf "AuthGroupFile"       "$CURPATH/var/ftpd.group"
editconf "UserAlias"           "anonymous ftp $uname"

# 处理UID
bin/ftpasswd --home $HOME --name $uname --group $gname --shell /bin/bash --file $CURPATH/var/ftpd.group --uid $uid --gid $gid
bin/ftpasswd --home $HOME --name $uname --passwd $uname --shell /bin/bash --file $CURPATH/var/ftpd.passwd --uid $uid --gid $gid

我们执行 sh init.sh 它做的事儿是:
通过调用ftpasswd命令、替换默认配置文件,以当前用户作为ftp的用户

最后 sh start.sh启动服务

#!/bin/sh
CURDIR=`cd $(dirname $0);pwd`
export LD_LIBRARY_PATH=$CURDIR/lib:$LD_LIBRARY_PATH
nohup sbin/proftpd -c $CURDIR/etc/proftpd.conf -n &

附件 proftpd.tar.gz.zip 是已编译好的proftpd,先后执行init.sh start.sh 可快速运行起来。

参考 http://ftp.proftpd.org/docs/

写作&输出计划

我大学本科读的是管理科学与工程,包含经济管理、计算机相关课程。
大学时,我没有好好学习专业课程,只是学会了些编程技术,做了程序员。

现在想想,其实是自己的焦虑和懒惰、缺乏好奇心,措施很多认真学习的机会。没办法,现在我很想捡回来,很想成为一个真正的思考者、实践者,能够不断提高自己的认知、见识体验更多事物、同时带来一定的财富,理想地过这一生。

接下来,我的计划是

  1. 深入研究计算机科学,产出系列教程,包括算法详解、GOLANG语言基础、WEB项目实战
  2. 深入学习金融证券,产出学习总结系列文章

本周起,每周一篇文章

本地开发测试、服务器运行的一个方案

本文目的是分享一个开发便捷、运行简便、工作优雅的开发方案。
本文适用于使用IDE写代码、看代码的RD及QA。对于热衷Vim等编辑器的同学,可能不适用。
本地指个人笔记本,服务器指的是开发运行的机器。

本地开发服务器运行.png

1.开发便捷:利用IDE的强大功能就好

2.运行简便:服务器(开发机)上的环境是直接可用的,所以将本地代码快捷地同步到服务器上运行,本地开发并提交版本控制。
什么方式?SFTP/FTP/SMB等都可以,服务器上只要运行相关服务器,本地配置认证、目录映射,本地代码变动,手动或自动地将代码上传。如何在Webstorm/Phpstorm中设置连接FTP

3.工作优雅:举例说,本地开发分支A,服务器运行调试,开发完成(提交代码)或开发至一半(git stash暂存工作进度),本地切换分支B,开发下一个功能... 此刻服务器上代码的版本控制,就是不干净的,所以在本地切分支A->B时,同时处理好服务器的代码,清理不干净的代码、同样切换A->B,以git为例

git clean -df
git reset --hard
git pull
git checkout --track origin/B

remote_addr及X-Forwarded-For及用户真实IP及内网安全

先缕一下背景,计算机网络,连在网络中的机器都有一个(或多个)IP地址,提供Web服务的机器,常有一个便于人们记忆的域名,通过DNS解析到一个(或多个)IP地址。有的网站流量大,需要不止一台机器提供服务,但域名只有一个,只能指向一台机器,怎么办呢?

代理服务器负载均衡(简称LB),提升静态网页的访问速度,增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性

互联网产品做大了,再做它个开放平台,搞完用户,搞合作伙伴。对外提供内网服务,开放平台服务器(简称OP)实现认证,代理调用内网服务。
以下,OP、LB、Server均为Nginx

remote_addr_proxy.png

Web服务器,一些场景,根据来源IP地址,决定服务与否。若是内网接口,只服务内网机器,拒绝服务来自外网的请求。
遇到的问题是,当client c通过OP请求内网接口时,Server解析客户端IP为client c的IP,其为外网IP 遂拒绝了服务。此时,我们希望Server拿到的客户端IP为OP的内网IP,这样就能正常为OP代理的客户服务了。怎么做呢?

HTTP协议虽然定义了Client-Ip请求头,但不是安全的,服务器的做法是取TCP连接的对端IP作为client ip,在Nginx中,解析为变量$remote_addr,不架设代理、负载均衡时,直接拿来用即可。但当在Server前代理时,应利用Nginx的ngx_http_realip_module中的real_ip_header指令,指定用哪个请求header的值来替换默认的$remote_addr。

假设
client a IP:12.34.56.78
OP IP: 34.56.78.90 及内网IP 10.22.33.44
LB IP: 10.23.34.45
这时,我们考察 X-Forwarded-For 的定义及格式,对于上图Server接收来自client c的请求时,X-Forwarded-For首先由OP设置为client c的IP,即

proxy_set_header X-Forwarded-For $remote_addr;

LB接收此header时,应再次设置

proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;

此时,到达Server的信息应该是:
$remote_addr: 10.23.34.45
X-Forwarded-For: 12.34.56.78,10.22.33.44

注意,Server知道Load Balance的存在,所以不关心$remote_addr的默认值,关心的是真正的请求IP,此时可设置
real_ip_header

set_real_ip_from  10.0.0.0/8;
real_ip_header    X-Forwarded-For;
real_ip_recursive off;

关于real_ip_recursive指令,官方文档:

If recursive search is disabled, the original client address that
matches one of the trusted addresses is replaced by the last address
sent in the request header field defined by the real_ip_header
directive. If recursive search is enabled, the original client address
that matches one of the trusted addresses is replaced by the last
non-trusted address sent in the request header field.

设置off时,Server得到的$remote_addr为10.22.33.44 即开放平台的IP,正常服务!

注:RFC 7239 定义了一个新的 Forwarded header,更完备地组织这些信息。