四则表达式去重/去冗余(规范化法)的思考

四则表达式是指仅使用以下符号+, -, *, /, (, )及实数数值组成的合法表达式。至于什么是“合法表达式”,好吧,“合法”的定义这里先不展开,首先说说干嘛要做四则表达式的去重/去冗余。比如玩24点游戏,给出4个数构造一个四则表达式,使得结果正好等于24的问题,找出“全部解”。注意到这里所谓的“全部解”的说法是有问题的,比如这四个数是1,2,3,4,那么可以给出一百多种结果为24的不同的表达式,但很多都看起来是“重复”了,通过交换律和结合律可以变换为另一个。经过筛选,本质不同的只有如下三个解:
4*(1+2+3)
(1+3)*(2+4)
1*2*3*4
那些通过交换得到的各种组合我们并不关心,于是就有以上表达式去冗余的问题。

 

但我们平常所使用的表达式,一般均是指中缀表达式,像(1+2)*3-4这样子的,即表达先计算1与2相加,结果再乘以3,得到的结果再减去4。但这种表示法会产生歧义,于是乎有优先级,结合性,加括号等等一堆问题。这里改使用前缀表达式,例如前面这个式子可表达为:
(- (* (+ 1 2) 3) 4)
即(+ 1 2)表示1与2相加,实质上这就是lisp语言。下文的表达式均使用类似的表达形式。简要文法(定义①):
E -> VAL|(E')
E'-> + F|- E E|* F|/ E E
F -> E|E F
VAL -> 数值的词法由程序自己按需定义了

 

注意到,以上这种定义方式中,减法和除法是二元运算,加法和乘法是多元运算,因为加法和乘法具有交换律和结合律的性质,连续的加法运算,可以转化为多元的加法而不会影响结果,故如此定义,以便化简表达式。

 

我们如何判断两个表达式表达的含义相似,从而判断其中一个为冗余的呢?通常的做法是把表达式通过一组规则,转化为另一个“规范表达式”,或简称“范式”,然后判断这两个表达式转化得到的范式是否完全一样即可,就像离散数学里面二元逻辑中的范式。另外,表达式的运算的值是我们需要关心的,通过把以上前缀表达式改造,得到一个适合于做以上工作的表达式(定义②):
E -> (VAL E')T
E'-> NULL|+ F|- E E|* F|/ E E|0- E|1/ E
F -> E|E F
T -> NULL|{T'}
T'-> VAL|VAL T'

 

一眼看去估计不好看懂,用前面的例子,(- (* (+ 1 2) 3) 4)表示为:
(5 – (9 * (3 + (1) (2)) (3)) (4))
也就是说,操作符前面的数值表示这个表达式的最终值,而且可以没有操作符以表示这是叶子结点。而后面的T是干什么的呢?比如表达式(+ (* 1 2 3) 0),可以写为:
(6 * (2) (3)){0 1}
存在不影响表达式值运算的数,则丢到后方大括号,还原表达式的时候,遇到0则+0,遇到1则*1即可(如果需要的话)。
可能有人问为什么要保留这些不影响结果的数,其实这是保证处理后保留参数运算的所有的数值的信息,避免把3*4+0与1*3*4与3*4总是视为相同的情况,毕竟参与运算的数本身都不相同,这样可以由使用者决定要不要比较这些数。
特殊情况例如(1 +),这表示了一个非叶子结点,但是存在有效值,这种特殊结点下文会用到。

 

实质上,此方式定义了一种多叉树数据结构,数据包含运算结果、操作符、子结点列表、不影响结果的结点集合
特殊规定:所有的变形规则不能改变此表达式树的叶子结点个数(含不影响结果的结点集合内的叶子结点)
Read the rest of this entry »

Tags: , , , ,

Linux网站服务器搭建SSL/TLS(https)

首先SSL/TLS是什么鬼?比如你现在正在看的https://misakamm.com/blog,前面是https,表明这个是https协议,https就是http + SSL/TLS,在http外面套一个加密层,让第三方难以得到传输的明文数据。如果用chrome访问这个站,在这个URL旁边会显示一个绿色的锁,表明这个连接是安全的。另外境外的https还有一个附加效果就是抵御关键字的审查,同时Google也更喜欢收录https的站点。

其实以上是在说废话,看这文章的乃萌肯定是知道此为何物才会找到这里来的啦,所以就不废话了,以下是搭建步骤:

1.生成公钥和私钥对
2.公钥提交到CA机构签发一个crt证书(不建议自签发证书)
3.配置证书链
4.在你的apache或nginx里开启SSL支持并配置好你的crt证书和私钥
[5].继续其它配置,如SPDY,HSTS,SSL session resumption,和 Perfect Forward Secrecy (可选)
其中,你如果希望你的站点是全https的话,建议配置HSTS,这样别人使用http访问时会自动转向到https

由于这里主要讲搭建步骤,去CA机构注册什么的就不介绍了,个人小站推荐StartSSL和AlphaSSL,前者可以得到免费证书。

1.生成公钥和私钥对
执行以下命令
$ openssl genrsa –out my-private.key 2048
就会在当前目录下生成一个私钥文件my-private.key,文件名自己随便定义
如果需要对私钥加密,可以执行
$ openssl genrsa -aes256 –out my-private.key 2048
这时需要输入你的自定义密码来保护这个私钥,之后的步骤若用到私钥,则会要求你输入你的自定义密码
然后再执行
$ openssl req –new –key my-private.key –out www.misakamm.com.csr
这时会要求你输入一些信息,具体如下:
Country Name (2 letter code) [AU]:
State or Province Name (full name) [Some-State]:
Locality Name (eg, city) []:
Organization Name (eg, company) [Internet Widgits Pty Ltd]:
Organizational Unit Name (eg, section) []:
Common Name (eg, YOUR name) []:
Email Address []:
A challenge password []:
An optional company name []:

注意从Email Address开始不要填写
Common Name填写你要SSL支持的域名(你的站的域名),如 www.misakamm.com
如果你申请的是泛域名证书,那么这里应该填写类似 *.misakamm.com

填写完毕后就会生成一个www.misakamm.com.csr文件,这样第一步就完成了。

2.公钥提交到CA机构签发一个crt证书
使用任何一个文本编辑器打开刚才生成的csr文件,你将会看到类似如下的内容
-----BEGIN CERTIFICATE REQUEST-----
MIICrjCCAZYCAQAwaTELMAkGA1UEBhMCR0IxDzANBgNVBAgMBkxvbmRvbjEPMA0G
......
-----END CERTIFICATE REQUEST-----

复制里面全部内容,然后在CA机构网站上,在提交csr内容的地方,粘贴。然后签发成功后,你就能下载回来一个.crt文件,可能通过网页上下载,也可能通过邮件方式发送给你。如果是邮件方式的话,要注意最好是使用gmail邮箱。邮件方式的话需要自行复制里面crt文件的部分自行保存为crt文件。crt文件类似以下的格式:
-----BEGIN CERTIFICATE-----
MIIETTCCAzWgAwIBAgILBAAAAAABRE7wNjEwDQYJKoZIhvcNAQELBQAwVzELMAkG
A1UEBhMCQkUxGTAXBgNVBAoTEEdsb2JhbFNpZ24gbnYtc2ExEDAOBgNVBAsTB1Jv
b3QgQ0ExGzAZBgNVBAMTEkdsb2JhbFNpZ24gUm9vdCBDQTAeFw0xNDAyMjAxMDAw
MDBaFw0yNDAyMjAxMDAwMDBaMEwxCzAJBgNVBAYTAkJFMRkwFwYDVQQKExBHbG9i
YWxTaWduIG52LXNhMSIwIAYDVQQDExlBbHBoYVNTTCBDQSAtIFNIQTI1NiAtIEcy
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA2gHs5OxzYPt+j2q3xhfj
kmQy1KwA2aIPue3ua4qGypJn2XTXXUcCPI9A1p5tFM3D2ik5pw8FCmiiZhoexLKL
dljlq10dj0CzOYvvHoN9ItDjqQAu7FPPYhmFRChMwCfLew7sEGQAEKQFzKByvkFs
MVtI5LHsuSPrVU3QfWJKpbSlpFmFxSWRpv6mCZ8GEG2PgQxkQF5zAJrgLmWYVBAA
cJjI4e00X9icxw3A1iNZRfz+VXqG7pRgIvGu0eZVRvaZxRsIdF+ssGSEj4k4HKGn
kCFPAm694GFn1PhChw8K98kEbSqpL+9Cpd/do1PbmB6B+Zpye1reTz5/olig4het
ZwIDAQABo4IBIzCCAR8wDgYDVR0PAQH/BAQDAgEGMBIGA1UdEwEB/wQIMAYBAf8C
AQAwHQYDVR0OBBYEFPXN1TwIUPlqTzq3l9pWg+Zp0mj3MEUGA1UdIAQ+MDwwOgYE
VR0gADAyMDAGCCsGAQUFBwIBFiRodHRwczovL3d3dy5hbHBoYXNzbC5jb20vcmVw
b3NpdG9yeS8wMwYDVR0fBCwwKjAooCagJIYiaHR0cDovL2NybC5nbG9iYWxzaWdu
Lm5ldC9yb290LmNybDA9BggrBgEFBQcBAQQxMC8wLQYIKwYBBQUHMAGGIWh0dHA6
Ly9vY3NwLmdsb2JhbHNpZ24uY29tL3Jvb3RyMTAfBgNVHSMEGDAWgBRge2YaRQ2X
yolQL30EzTSo//z9SzANBgkqhkiG9w0BAQsFAAOCAQEAYEBoFkfnFo3bXKFWKsv0
XJuwHqJL9csCP/gLofKnQtS3TOvjZoDzJUN4LhsXVgdSGMvRqOzm+3M+pGKMgLTS
xRJzo9P6Aji+Yz2EuJnB8br3n8NA0VgYU8Fi3a8YQn80TsVD1XGwMADH45CuP1eG
l87qDBKOInDjZqdUfy4oy9RU0LMeYmcI+Sfhy+NmuCQbiWqJRGXy2UzSWByMTsCV
odTvZy84IOgu/5ZR8LrYPZJwR2UcnnNytGAMXOLRc3bgr07i5TelRS+KIz6HxzDm
MTh89N1SyvNTBCVXVmaU6Avu5gMUTu79bZRknl7OedSyps9AsUSoPocZXun4IRZZ
Uw==
-----END CERTIFICATE-----

(以上其实就是AlphaSSL的crt证书,下文会用到)保存好了后,第二步就完成了。
Read the rest of this entry »

Tags: , , ,

如何让流氓软件难以联网作恶

流氓软件,就是指瓷器国内的公司大多数软件,尤其是安全软件(那你不要安装不就好了噗)。问题是如果某流氓软件你不得不安装,又不想让它直接外连网络(不然等于直接开后门了),又或者你只希望得到你允许的软件才能联网,怎么办呢?

如果局域网内你有两台机子(或者一台机子能轻松带一个虚拟机),那么就比较简单了。先命名一下常用那一台(需要做保护的)为A机器,另一台(真实机器或虚拟机)为B机器,B机器若为虚拟机则联网方式要设置为桥接。首先在B机器上架设一个socks5或http代理服务器,比如在windows下可以使用TightSocks5或CCProxy或Privoxy,linux下可以用Squid或ssh-server等等。

然后在A机器上设置ip地址为手动设置,需要故意把网关地址配置错误。
例如你的路由配置是192.168.0.1,掩码255.255.255.0,B机器的IP为192.168.0.100,A机器的IP为192.168.0.101,把A机器的网关IP从原来的192.168.0.1改为192.168.0.2,这样A机器就会成为只能访问内网的状态。假如B机器配置的是http代理,端口号为8080,那么A机器需要配置好代理地址和端口。具体配置如下:
B:
IP 192.168.0.100
Mask 255.255.255.0
Gateway 192.168.0.1
Http proxy listen: 8080
Socks5 proxy listen: 1080 (以上二选一就行了)

A:
IP 192.168.0.101
Mask 255.255.255.0
Gateway 192.168.0.2
Proxy setting: 192.168.0.100:8080 or 192.168.0.100:1080

如果是firefox,在选项->高级->网络->配置,填写B机器的ip 192.168.0.100,端口号8080,协议为http即可。如果是IE浏览器,因为IE不支持Socks5代理,如果B机器配置的是Socks5代理,那么A机器上需要安装Privoxy把它转换为http代理再使用。如果是linux开的ssh-server,那么在A机器上建立一个ssh-tunnel转为Socks5代理使用即可。

对于支持自定义代理的软件可以使用以上设置,但如果不支持自定义代理的软件呢?比如QQ(别和我说QQ那个配置代理的功能,那个是残废的,QQ一样会走直连,你试试就知道了,群文件群图片都收不到的),比如QQGame(它有非常多依赖IE显示的页面,这些不走代理),又比如网游,怎么办呢?这个时候可以用Proxifer或Proxycap,指定代理规则,强行让某些程序通过你指定的代理。

这种做法会比双虚拟机法更节省资源,不过因为能直接访问同网段的机器,如果中了ARP病毒的话这部分则没有保护(可以考虑用双路由来实现)。以上做法能同时让一部分木马失去作用(除非它注入到你能通过代理连接的进程里,而那个进程又是用Proxifer强行走代理的话),不是万能,安全什么的还是得自己小心再小心。

2015/02/07补充:
最近爆出了WebRTC漏洞,窝经过测试发现这样配置下能屏蔽掉这个漏洞的影响;而使用一般工具控制应用程序的连网的情况下,还是会泄露公网真实IP。另外这个配置还能防止flash方式泄露真实IP

Tags:

传统规则俄罗斯方块AI比赛(Traditional Tetris A.I. Contest)

活动帖子链接:http://tieba.baidu.com/p/3133583238 http://tieba.baidu.com/p/3150868298

 

规则:
包括仅考虑当前块(不考虑下一块)在场地大小为10×20的俄罗斯方块生存比赛
以及考虑当前块和下一块在场地大小为10×10的俄罗斯方块生存比赛
比赛目标:统计平均消行数,平均消行数越高排名越前
使用经过Misakamm调整的ColinFahey平台
接口和接口说明在开发包里:http://pan.baidu.com/s/1hqmnJ16

Rules:
There are two sub-contests; 1 piece (NO preview) in 10×20 matrix, 2 pieces (with ONE preview) in 10×10 matrix,
both with the goal to make as many rows/game as possible.
Platform: Colin Fahey’s Standard Tetris version 2003, modified by Misakamm.
The development pack and documentation is available here: http://pan.baidu.com/s/1hqmnJ16

 

提交办法:
把工程属性改为Release编译出dll,然后使用度受盘共享你的dll(或如果你愿意的话可以连同源代码),然后在活动帖子里发共享链接,或者把dll发送到我的email里,需要注明你的网名或贴吧ID,连同此dll所支持的技术,最好连同QQ或email等联系方式一起发。
mail

How to submit:
Build your project and output the dll file in Release mode, write some instructions about your algorithm, then mail them to misakamm. Share your source code if you are willing to.
Read the rest of this entry »

Tags: , , ,

传统规则俄罗斯方块AI技术介绍

传统俄罗斯方块介绍
  俄罗斯方块,英文Tetris,俄语Тетрис。发明者Alexey Pajitnov (Russian: Алексей Леонидович Пажитнов, regularly Aleksei Leonidovich Pazhitnov, born 1956)于1984年6月6日发布,名字由希腊数字4的前缀tetra-与网球tennis(作者最喜爱的运动)合并而来。
  传统俄罗斯方块,指的是Alexey Pajitnov所发明的版本,游戏场地标准尺寸为10×20,而每个方块由四个小方块拼成,一共有7种不同的形状,相应的象形字母为ITOSZJL。每种形状均可以90度旋转,当一行堆满方块时,此行就会消去,在其上面的方块就会下降一行。在消除的同时,按照一次性所消除的行数,累加不同的积分,看谁能在失败之前得到最多的积分。
e99ec4b23ce5a8d833407c28f47eefbd
FC俄罗斯方块
st_12st_15
Standard Tetris运行Misakamm two-piece AI,已消超过5亿行和10亿行的截图
 
俄罗斯方块AI介绍
  传统的俄罗斯方块,版本有很多种,但是基本上都有一个特点,就是只能看到一个next方块,少数的甚至根本不显示next方块。也就是说,要做AI的话,也只有两个选择:考虑next和不考虑next。而不考虑next的是最多的(由于早期机器性能原因,或由于偷懒),任天堂、世嘉等的各版本俄罗斯方块中所带的AI绝大多数都是不考虑next的。当时,俄罗斯方块的AI研究,主要是围绕如何才能“不败”。在证明俄罗斯方块是NP-complete问题(于2002年11月完成证明并发表论文),以及证明完全随机的方块最终游戏一定会结束(Heidi Burgiel. How to lose at tetris. Mathematical Gazette, 81:491:194–200, July 1997)后,研究者开始围绕one-piece(单块,不考虑下一块的)算法,在只知道当前的方块的情况下,怎么样的AI平均能得到更高的积分或消除更多的行。在这里的研究中,最为出名的算法,是Pierre Dellacherie(France)于2003年1月创作的算法,当时在世界范围内取得了平均最高消行数。此AI最高消行超过200万行,平均65万行(在Colin Fahey的emulator上)。因为它们只为了得分或消行数高,不会主动的垒四行,在人的眼里看来,这些AI有时候相当的笨,除了速度快,没有多少优点。
 
俄罗斯方块AI基础
  传统规则下,如果你也想制作一个one-piece(单块或只看当前块,不考虑下一块)算法,那是相当的简单的,网上也有相当多的人的不同实现。不过,这些AI程序均不考虑架空可以平移插入的情况,并且这些AI的做法也相当的一致,穷举最多10*4种可能性(不考虑下落中途横插去补洞),然后针对每一个可能性进行评分,AI按照得分最高的那个位置进行摆放即可。建议先自行实现一个评估方案后再参考Pierre Dellacherie的评分算法,也可以参阅这个pdf,介绍了现有的不同的评分方式,里面还有介绍Pierre Dellacherie的评分公式和Thiery and Scherrer的评分公式。或者也可以参阅此网友的实现,还有Colin Fahey的实现,里面包含实现源代码,有若干个实现版本。
  要注意的一点是,俄罗斯方块的AI类型与棋类AI很不一样的地方,就是俄罗斯方块不仅仅与局面相关,还与产生这个局面的行动(即最近一块的摆放位置产生的效果)有关,达到同一个局面,是消行产生的还是不通过消行产生的是完全不同的,但棋类根本不必关心产生这个局面的前一个局面是什么样子的(和棋或长将什么的例外),这个根本上的区别导致它与棋类AI会很不一样。不少的单块AI实现使用了最近一块摆放的位置和效果信息,比如高度,消行数等等,单块的AI下使用这些信息并没有什么大问题,实现上相对自由。但若打算做多块AI的话,使用的信息就要非常慎重小心了。
  局面信息的选取,并没有什么规定,纯经验类的东西。不过大部分的AI都会使用到“洞”的个数,即空格子的上方若有实心格子,那么它就定义为洞。但这个信息的选取对AI的影响非常的大,并且有很多坑。后文将对此解释。
  有了基本的理解后,就需要动手搭建一个游戏。编写的时候注意,这里有一个规范性的问题,规范性内容至少包括:
1.新方块出现的位置;
2.那7个形状旋转后的形状及位置,可参阅colin上的图
3.产生碰撞而不能移动或旋转的处理(传统规则下还没有踢墙的概念);
4.玩家的所有可操作集合(有没有重力影响,单向旋转还是双向,单向的话是哪个方向,下落是下落一格还是直接到底还是两者均可等等);
5.AI的可操作集合是否与人类玩家一致(不一致即使用作弊方式,比如直接移动到目的地不管事实上能不能办到);
6.下一块的产生算法(使用什么样的随机函数,是否带有记忆或限制条件,是否与玩家当前场地有关等等);
7.当前操作方块旋转时会不会高于游戏场地,允不允许高于的情况出现。
  规范若有差别,很可能是相同AI下表现却很不一样。根据以上规范性问题,在这里和读者约定一下主要的规范:
1.新方块的4*4矩阵出现在游戏场地内最顶部的中间,若场地宽度为奇数,则出现于偏左边;
2.方块旋转以上文中的图片为准;
3.碰撞时操作取消;
4.玩家可以做的操作有,左移一格,右移一格,逆时针旋转90度,直接下降到底部并固定,无重力;
5.AI只能做人能做的事,不能作弊;
6.使用MT19937算法,以线性均匀分布方式产生方块序列,种子使用当前时间,仅打开程序时初始化种子,重新开始游戏不重新初始化随机数种子;
7.不可能出现高于顶部。
  另外,AI部分规定先旋转再移动,以便移植到colin的平台上有相同的行为,即不支持下图中的行为:
1754324343
  这里有一点需要注意的,就是随机数算法的影响。如果用随机性一般的算法,会对其AI性能有非常大的影响,有的会令其平均行数大幅提升,有的会令其大幅下降,所以建议使用随机性较好的MT19937算法,且必须以线性均匀分布方式产生。
 
one-piece AI排行榜(不完整,仅参考用)
  在这里约定使用Colin Fahey(或类似)的emulator上,场地大小为10×20,one-piece(不带next块)。目前在这平台上,实现了的包括Pierre Dellacherie的算法、Colin实现的Roger LLima/Laurent Bercot/Sebastien Blondeel算法、Colin Fahey自己的、由Misakamm实现的Thiery and Scherrer算法、Misakamm实现的两个版本的算法。之所以直接用这个平台,是因为这个实现在one-piece AI里很有代表性,同时Misakamm也懒得再自己搭建一个了,除了少许地方与前面所说的规范在随机数略有区别外,其它几乎都一样。而且它不会硬生成10*4种摆法,而是会验证在以上规范下能不能移动达到再去计算。

AI名称及年代
A.I. name & year
平均行数
average rows
运行局数
total games
历史最高行数
max rows
Misakamm Ver2.0 (2014)
2,727,734
577
15,219,733
Misakamm Ver1.0 (2014)
1,309,011
1752
11,048,999
Thiery and Scherrer (2009)
867,695
2086
7,256,062
James and Glen one-piece (2004)
592,334
1226
5,180,342
Pierre Dellacherie (2003)
578,921
1959
4,109,278
James and Glen hybird (2004)
568,595
1412
4,330,312
Roger LLima etc. (2005)
42,000
Roger LLima etc. (1996)
19,406
2224
123,020
Kakade (2001)
6,800
Farias and van Roy (2006)
4,700
Bertsekas and Tsitsiklis (1996)
3,200
Lagoudakis et al. (2002)
2,000
Colin Fahey (2003)
644
464
4,905
Ramon and Driessens (2004)
50
Updated on: 12 April, 2014

Read the rest of this entry »

Tags: , , , ,

TOJ规则俄罗斯方块人机对战视频

视频链接:http://static.video.qq.com/TPout.swf?vid=h011622rvar&auto=0
b站高清版本链接 http://www.bilibili.tv/video/av678799/
youtube原版链接 http://www.youtube.com/watch?v=3BiXG8mMPvs

由玩家Jonathan Boccardi(左)对战V1.3P4版本level7 AI(右)。
Player “Jonathan Boccardi”(left) VS “V1.3p4 level7 AI”(right)

其它规则细节:玩家开启了180旋转,回合制对战模式(人放多少方块AI就放多少方块)
other rule detail: enable 180 spin, turn-based mode

一共对战100局(前两局没录到,第三局开始),视频时长119分钟
total 100 games(begin from the 3th game), 119 minutes stream

 

非常感谢视频录制的玩家Jonathan Boccardi,他录制的这段视频让我发现AI中存在的问题,这些改进在新版本中得到了体现。现把这段录像与大家分享,如果你在录像中发现AI中更多的不足,请与我联系

玩家原话(引用自u2b):
This bot is so much fun to play. It is far better than I am, but the games were worth the fights. There were plenty of matches where I could have done better, such as slowing down and eliminating unnecessary misdrops, but anyone can go on about what could be better. I played 100 games with the bot and won 7.

Big thanks to Misaka for the hard work she put into this and for sharing it with the Tetris community! I’m looking forward to the upcoming releases for this client. :D

Music (In order):
Lost Cause – TeeBee & Noisia
Choke – Mayhem & Noisia feat. MC Verse
One Last Chance – Aeph
Capsize – Memtrix
800 Pound Gorilla – Neonlight & Receptor
Back To Reality – Infuze
Malfunction – Apex
Head Case – Apex
Computer Music – Neonlight
Sprech Funk – Neonlight
Cosmic Cowboy – Neonlight
True Legend – Neonlight
Altered Dimensions (Monkey Freakz Remix) – Fonik **(I skipped this one. I was really in the mood for Drum & Bass. :P )
Surge (16Bit Remix) – Amon Tobin
retrocausality – Urbandawn
redeemer (feat. lucy) – Loki, Lucy
switchblade – BLOKHE4D, Prolix
the shakes – Prolix
space truckers – Aeph, Neonlight
parallel universe – Telekinesis
reminiscence – Neonlight, sH1, Wintermute
savage jackson – Aeph
warning (feat. massi) – Fistognosticated, Massl
bass dust – BLOKHE4D, Receptor

YES I LOVE DRUM & BASS SHUT UP
Read the rest of this entry »

Tags: , , , ,

Ubuntu下配置php5+apache2+mysql

说明:也可以看成是安装WordPress或phpbb等php程序的服务器配置文档
以下指令全部使用root执行,或者sudo之,至于文件的修改,你可以vim/vi/emacs/nano

apt-get install apache2
安装后,打开127.0.0.1(如果是本机上的话,否则填写对应的ip地址或域名),如果显示It Works!则安装成功

apt-get install php5 php5-mysql libapache2-mod-php5 php5-cli
apt-get install mysql-server
安装mysql时会让你设置root密码,最好设置一下,不要为空

配置apache2:
修改/etc/apache2/httpd.conf
添加一行
ServerName 127.0.0.1:80

ServerName localhost:80
用于配置默认的ServerName,此步可做可不做,不做的话,在启动apache2时会有一个警告(或者把下文中的VirtualHost中每一个都写上ServerName就没有这个警告)

启用url rewrite:
执行a2enmod rewrite开启rewrite模块(非常重要)
修改/etc/apache2/sites-enabled/000-default文件中的
AllowOverride None 改为 AllowOverride All
同时,这个文件也管理www根目录的位置,以及虚拟目录的设置,默认为/var/www,你可以修改它
如果你需要设置虚拟目录,那么可以在最前面加上类似以下的内容:

1
2
3
4
5
6
7
8
9
10
11
<VirtualHost *:80>
        ServerAdmin misakamm@localhost
        ServerName ege.misakamm.com
        DocumentRoot /home/misaka/www/ege
        <Directory /home/misaka/www/ege>
                Options FollowSymLinks
                AllowOverride All
                Order allow,deny
                allow from all
        </Directory>
</VirtualHost>

VirtualHost 的参数指定监听ip和端口,ServerName 限定访问域名,DocumentRoot 设置www根目录,Directory设置对应目录的配置。最后重启apache
/etc/init.d/apache2 restart

然后你可以编写一个内容为的test.php文件放在根目录访问,看能不能出现php信息,如果之前你以其它方式安装的php,或者移动了www目录,则有可能出现不显示phpinfo的情况,这时候你查找/etc/php5/apache2/php.ini里面的open_basedir的值,有没有包含www根目录,如果没有则需要加上。但如果显示403错误,有可能是没有文件访问权限,用root登陆后,chmod 666 xxx.php,如果要设置整个目录就chmod -R 666 xxx

注意看一下phpinfo里,有没有mod_rewrite模块。

然后复制文件到/var/www(或者你设置的路径),比如安装一个phpmyadmin用于可视化管理数据库,要用到数据库root密码
如果用phpmyadmin访问时,出现mysqli相关的错误,执行以下命令:
apt-get install php5-mysql
/etc/init.d/mysql restart

之后便可以安装wordpress或其它php程序了。注意的是,如果需要wordpress的在线自动更新功能,那么需要对wordpress安装目录下的文件设置为apache的owner,具体使用的user可以用命令ps -aux查看当前进程的属性,不过我们只关心与apache有关的,所以我们可以用ps -aux|grep apache2,我们发现

www-data 12829  0.0  6.1  55752 31088 ?        S    20:48   0:02 /usr/sbin/apache2 -k start

于是转到安装目录下使用
chown -R www-data .
就解决了,否则在使用在线自动更新功能的时候,wordpress会向你请求ftp帐号

如果需要php支持上传更大的文件,或者更长的执行时间等权限,请参阅php的配置文档。

若需要支持邮件发送通知功能,那么需要安装sendmail
apt-get install sendmail

Tags: , , ,

算法分析之随机选取无重复元素集合(Select a single, random combination of values)

这是一个经典且不衰的问题,具体问题是:
给定一个n(n>0)元素集合,在当中随机选取m(0<=m<=n)个元素(假设随机函数能均匀分布且随机性足够好),满足两个条件:
1. 元素不能重复
2. 能证明各元素是被等概率选取到

其中第2个条件至关重要,算法必须能证明能等概率抽取,否则算法无效
为了让问题简化并在程序中实现,我们规定这个n元素集合,就是[0, n)中所有的整数

算法一:
最简单能证明是等概率的,并且很容易实现的算法是这样子的(python代码,注意randint(a, b)是等概率产生范围[a,b]之间的整数):

def gen(n, m):
    res = set()
    i = 0
    while i < m:
        r = random.randint(0, n-1)
        if r not in res:
            res.add(r)
            i += 1
    return res

思想很简单,就是抽签法,我们先证明一下抽签是等概率的,被抽中的概率于先后无关,此证明在中学的数学课本也有
抽签法就是在n个元素中,依次抽取m个,假设任意某签是A,那A第一个被抽中的概率是1/n,第二个被抽中的概率是第一次没抽中的概率 1-1/n 乘以第二次被抽中的概率1/(n-1),即(1-1/n) * 1/(n-1) = 1/n,第三个的概率是(1-1/n) * (1-1/(n-1)) * 1/(n-2) = 1/n,如此类推,得到A在每一次被抽中的概率都是1/n,即任意签在第任意次都是以1/n的概率被抽到。所以任意签在抽取m次后,被抽取到的概率都是m/n。
如此以来,可推论抽取第i个的时候是等概率从n-i+1个里选一个的话,就是抽签法,此法可保证每个元素是等概率的选取,之后的证明会到这个推论来简化证明。 Read the rest of this entry »

Tags: , , , , , ,