500 OOPS: cannot change directory错误

Posted by & filed under Excellence Article.

其实这个错误都遇到过好几次了，就是因为默认centos selinux限制了,不过今天居然一时没想起来

现在再做个记录吧:

他的系统是CentOS，是RH派系的。我把vsftpd安装配置好了，以为大功告成，但客户端访问提示如下错误：
500 OOPS: cannot change directory:/home/ftp
原因是他的CentOS系统安装了SELinux，因为默认下是没有开启FTP的支持，所以访问时都被阻止了。
//查看SELinux设置
# getsebool -a|grep ftp
ftpd_disable_trans –> off
或者
ftp_home_dir–>off
//使用setsebool命令开启
# setsebool ftpd_disable_trans 1
或者
# setsebool ftp_home_dir 1
//查看当前状态是否是on的状态
# getsebool -a|grep ftp
ftpd_disable_trans –> on
或者
ftp_home_dir–>on
//setsebool使用-P参数，无需每次开机都输入这个命令
# setsebool -P ftpd_disable_trans 1
或者
# setsebool -P ftp_home_dir 1
# service vsftpd restart

有关selinux的配置

如关闭，仅仅警告，强制等等 需要编辑/etc/sysconfig/selinux 默认是强制

或者直接SELINUX=disabled 禁止掉

不过要服务器重启才生效

MySQL 先排序再分组的问题

Posted by & filed under Excellence Article.

group是分组,想先排序如何办?

建一个表试试

–
– 表的结构 `test`
–

CREATE TABLE IF NOT EXISTS `test` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(16) NOT NULL,
`phone` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

–
– 导出表中的数据 `test`
–

INSERT INTO `test` (`id`, `name`, `phone`) VALUES
(1, ‘a’, 1234),
(2, ‘a’, 3333),
(3, ‘b’, 555),
(4, ‘b’, 6773),
(5, ‘a’, 743),
(6, ‘c’, 95434);

查询一下,
SELECT * FROM `test` group by name
得到
id name phone
1 a 1234
3 b 555
6 c 95434

但我们想得到id最大的name怎么办?
SELECT max(id),id,name,phone FROM test group by name
得到
max(id) id name phone
5 1 a 1234
4 3 b 555
6 6 c 95434
可以看到,虽然每个name的最大id得到了,但是,其他数据依然是每个name的第一行
用子查询
select * from (select * from test order by id desc) t group by name
得到
id name phone
5 a 743
4 b 6773
6 c 95434
这就是我们想要的结果了,但是,这种作法在行数非常多的情况下,相当于把整个表复制了一次,估计效率低.
那用这种子查询
select * from test t where id in (select max(id) from test group by name)
得到
id name phone
4 b 6773
5 a 743
6 c 95434
然而,这种子查询因为用了in,在数量多的情况下,也许还更慢些?不确定,没时间测试
另外,还有一种方法,不过原理我也有些糊涂了,只是看网上有人这样作,
select * from test t inner join (select * from test order by id desc) t2 on t.id=t2.id group by t.name
得到
id name phone id name phone
5 a 743 5 a 743
4 b 6773 4 b 6773
6 c 95434 6 c 95434
为了想提高效率,想到了视图,先按id desc排个视图,再group by name,岂不是相当于子查询?
CREATE VIEW `testv` AS select `test`.`id` AS `id`,`test`.`name` AS `name`,`test`.`phone` AS `phone` from `test` order by `test`.`id` desc;
视图建立了,再查询
SELECT * FROM `testv` group by name
结果竟然是
id name phone
1 a 1234
3 b 555
6 c 95434
和在原表用
SELECT * FROM `test` group by name
的结果一样.看来视图和真正的表毕竟是有区别的

补充:
上网再看了一下,原来第二种子查询方法网上不是那样的,尽管我那样写在这个例子上也成功了,但是,说不定其他表会错?没时间测试.网上的方法是
select * from test t inner join (select max(id) as id,name from test group by name) t2 on t.id=t2.id and t.name=t2.name
得到
id name phone id name
5 a 743 5 a
4 b 6773 4 b
6 c 95434 6 c
另外,把上面这些查询方法中的test表换成testv,都可以得到正确的结果,尽管order by有点不同.
上面的排序都只针对一个字段,两个及以上字段也可以采用类似于
select * from (select * from test order by id desc) t group by name
这样的方法,在子查询中可以多个字段来order by
下面删除原来的test,重建一下
–
– 表的结构 `test`
–

CREATE TABLE IF NOT EXISTS `test` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(16) NOT NULL,
`month` int(11) NOT NULL,
`serial` int(11) NOT NULL,
`other` varchar(20) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

–
– 导出表中的数据 `test`
–

INSERT INTO `test` (`id`, `name`, `month`, `serial`, `other`) VALUES
(1, ‘a’, 200807, 2, ‘aaa1′),
(2, ‘a’, 200805, 2, ‘aaa2′),
(3, ‘b’, 200805, 3, ‘bbb3′),
(4, ‘b’, 200805, 4, ‘bbb4′),
(5, ‘a’, 200805, 1, ‘aaa5′),
(6, ‘c’, 200807, 5, ‘ccc6′),
(7, ‘b’, 200807, 8, ‘bbb7′),
(8, ‘c’, 200807, 3, ‘ccc8′),
(9, ‘a’, 200805, 6, ‘aaa9′);

查询
select * from (select * from test order by month desc,serial desc) t group by name
得到
id name month serial other
1 a 200807 2 aaa1
7 b 200807 8 bbb7
6 c 200807 5 ccc6
换一下排序方式
select * from (select * from test order by month asc,serial desc) t group by name
得到
id name month serial other
9 a 200805 6 aaa9
4 b 200805 4 bbb4
6 c 200807 5 ccc6
都按我们的要求显示了结果

杂记

Posted by & filed under Life Diary, Programming.

本来要学老王，取名叫乱炖，老王一直执着的用这个词，那我就换一个吧。一个多月没写博客了，前面一段时间是因为实在太忙，后面是懒，疯狂加班之后回家就什么都不想动，过了经过差不多一个多星期的正常人生活，现在终于缓过神来了。这个项目差不多是我加入以来我做过的最大的项目，很累，也很疯狂，项目还在继续，迭代一轮一轮的进行中。留下点笔记，记个印象。
1、项目开始的时候往往思想很宽泛，这个想要，那个想要，每一个功能都是无敌的，每一个功能都是必须的。我一直不赞同一开始就把产品设计的看上去很大很全，主要基于两个理由：
第一，产品一开始设计得大而全，会导致开发周期被拉长，在没有经过市场检验或者最终用户使用的时候，过长的周期会导致开发人员效率降低，没有人愿意做一个看不到前景的产品，没有来自最前线新的需求刺激，没人知道这个东西是不是靠谱的，很长的开发周期还会导致开发人员的疲惫，当然这个可能有些公司不一样，如果人手充足，这个情况或许不那么明显，但据我所知，所有的公司都是缺人的，特别是IT公司，为项目加班是常事，如果这个项目周期再长一点的话，估计就崩溃了。
第二,产品一开始就设计得大而全会导致设计出很多无用的功能，每个人都知道一个产品存在的意义在于其20%的功能，或许有人要反驳，我不预先搞多一点功能，我怎么知道那20%的功能是什么。这个疑问是有道理的，问题就在于，如果我们不能找出最精华的20%功能是什么，那么我们或许可以把圈子放大到30%，40%，甚至更大一点的范围，我们的工期也会缩短很多，避免做无谓的工作。
2、关于开发周期，我觉得最好不要超过一个自然月，一个月20个工作日，除掉UI和页面部分设计，再除去测试和修Bug时间，留给研发的时间大约40%~60%，也就是8~12个工作日，如果只需少量页面方面工作，留个研发的时间会多3~5个工作日。研发工作大约两个星期的，大部分正常上班时间是完不成工作的，不可控的因素有很多，所以这个阶段，可能会加班加点，稍微放松的时刻留在bug修复阶段和后续迭代的UI及页面设计阶段，这个阶段如果稍作控制，可以避免研发人员加班，有至少一个星期的时间让心情得到释放。
3、以上两点基本上接近了敏捷开发的管理流程，敏捷开发在最大限度的保证质量和兼顾项目人员之间的平衡，套用一句话，如果实施了敏捷开发，员工没有离职，那一定是加工资了，如果没有加薪，那一定会离职。需求的不断刺激和短周期的迭代，会导致项目人员情绪的紧张和工作的高压。
4、关于Zend DB，这个玩意的可移植性确实不错，稍作整合，就能嵌入其他框架，但是这玩意最好还是别用在复杂的项目中，而且由于Zend DB本身的设计问题，很多东西你不得不去搞个很变态的方式去解决，比如计算符合条件记录总数。可能由于出于降低耦合度的目的，Zend DB 本身不自动设置缓存，每次需要在action，在新建的每个Model中都要去写和缓存相关的代码，当然解决办法也是有的，就是自己在为Zend DB增加一个组件，将接口和数据库操作给整合进去，然后新建的Model不再继承原先的Zend_Db_Abstract，而是继承你增加的那个组件，从而做到相对优雅的使用缓存。不过我还是推崇，直接写SQL，虽然看起来不那么优雅，但是更容易掌控，对项目日后的调优，非常有益，在复杂逻辑的时候表现优越，如果只是单表操作，ORM依然是不错的选择。至于怎么选择，取决于你的需求，和你项目组人员的整体水平。
5、关于Zend Cache，这个玩意是个好东西，让我们在本地写程序的时候可以方便的使用文件缓存，到服务器上也很方便的改成memcache缓存，少排了好多二氧化碳，Zend组件最优越的地方就是可以轻松的整合，偷懒少写了好多代码，唯一用的不爽的地方是Zend Cache的Tag功能，这个功能本来是个很cool，很有用的功能，但是因为大部分key-value缓存不支持这个玩意，这个东西变成了只有文件缓存时可用，但是在每次save一个缓存的时候，如果需要给这个缓存加个过期时间的话，就得这样写:$cache->save($data, $cache_key, $tag, $expire)，因为memcache不支持这个玩意，这时候每次传入的tag就是一个空的数组，我就一直不明白为啥$tag不放到最后一个参数，毕竟所以的缓存类型都支持过期时间，而只有文件缓存才支持Tag
6、关于Tornado（被墙了）,我不知道国内用的人多不多，源代码hosting在github上，从邮件列表来看，似乎国内用的人不多，在华莽用户组这样的Python社区里面都几乎没有人提及，这个玩意非阻塞性的Web Server，集成了Web Framework 和 Web Server，我有幸能在我的试验性项目中使用这个东西，提供一组数据，没啥用处，供需要的人参考，单个进程大约能支持1.2K左右的活动链接，当然，要在Linux服务器上，并且支持epoll，多进程可以到2K，占用内存在100M以内，服务器没有任何异常，有进一步挖掘的潜力，我估计能超过3K，当然不建议你这么做，因为Server的后端可能处理不过来了，如果你想动手实现一个Web IM 之类的应用，Tornado是最佳选择之一，另外，如果用来做Web游戏的Server，也是非常合适的，Tornado的Web Framework这一块还很简陋，非高级人员+非Geek人员，不建议用来做产品开发
7、如果你还在寻找一个项目管理工具，我建议你使用Redmine，这玩意能够显著帮助你的团队减少抱怨，减少无效沟通，能够让上下游的同事更自如的安排计划，当然，这一切还需要你做一个布置，平台是死的，需要大家往里面填充属于自己的东西

代码调优法则–编程珠玑笔记

Posted by & filed under Study & Reading.

1、空间换时间法则

这个东西，稍微有点程序经验的人应该都接触过，比如在设计数据时候冗余了部分数据，避免关联表查询，减少开销，实际上也减少了查询时间，所谓空间换时间。还比如，我们将一个有点开销的计算结果存储起来，避免下次再次运算，减少时间消耗，再如，CPU的设计，设置了高速缓存，一级缓存，二级缓存，主存（通常所说的内存），其实一个硬盘和一个CPU也可以干活，只是干得不怎么样，因为硬盘和CPU之间速度实在是差别太大了，如是就有人想把可能要用到的数据预先加载到高速缓存或者主存中，慢慢形成了今天的个人计算机架构。

2、以时间换空间法则

这个其实也是天天在用的一个法则，只是一般技术人员看到“压缩”二字的时候，没联想到那么多，压缩就是最典型的拿时间换空间的例子，就是不断的重复前面已经存储过的存储地址，用来避免存取真实的数据。

3、循环法则

大部分稍微有点经验的人不会在同一个函数中循环两次同样的变量，但是仅限于同一个函数，假如在一个函数里调用了另外一个函数，那么就不一定了，很多人为了看似解耦的一个操作，在两个函数对同一个变量做了多次的循环。循环法则有几个比较经典细则：
第一、将代码移除循环，这是最容易想到的，当然，可以移除的条件是，每次循环都执行同样的某次操作。
第二、合并测试条件，高效的内循环应该包含尽量少的测试条件，最好只有一个，因此，程序员尽量用一些退出条件来模拟循环的其他退出条件。
第三、哨兵法则，在数据结构边界上放一个哨兵以减少测试是否已经搜索结束的开销。
第四、展开循环，展开循环可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也有很大帮助。
第五、删除赋值，赋值的开销实际上在整个程序的执行过程中占的开销可以忽略不计，但假如你要在一个循环十万次的循环中赋值，那么开销就不能不计了，尽可能的在循环中减少赋值吧。
第六，消除无条件分支，快速的循环中不应该包含无条件分支，通过旋转循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。
第七、循环合并，如果你不小心做了傻事，那么合并两个对同一个变量循环操作吧

4、逻辑法则
利用等价的代数表达式。如果逻辑表达式的求值开销太大就将其替换为开销较小的等价代数表达式。
短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到这个阈值就不在需要计算任何变量了。
对测试机条件重新排序。在组织逻辑测试的时候，应该是降低开销的，经常成功的测试放在高开销的，很少成功的测试前面。

5、过程法则
打破函数层次。对于（非递归地）调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。
并行性。在底层硬件条件下，我们构建的程序应该尽可能多的挖掘并行性。

6、表达式法则
编译时初始化。在程序执行前，应该尽可能多的变量初始化。
利用等价的代数表达式。如果表达式的求值开销过大，就将其替换为开销更小的等价的代数表达式，比如换一种算法
消除公共子表达式。如果两次对同一个表达式求值，其所有变量都没有任何改动，那么我们可以用下面方法避免二次求值：存储第一次的计算结果并用其取代第二次求值。

UDP hole punching 翻译

Posted by & filed under Study & Reading.

3.3. UDP hole punching  UDP打洞技术
The third technique, and the one of primary interest in this document, is widely known as “UDP Hole Punching.” UDP hole punching relies on the properties of common firewalls and cone NATs to allow appropriately designed peer-to-peer applications to “punch holes” through the middlebox and establish direct connectivity with each other, even when both communicating hosts may lie behind middleboxes. This technique was mentioned briefly in section 5.1 of RFC 3027 [NAT-PROT], and has been informally described elsewhere on the Internet [KEGEL] and used in some recent protocols [TEREDO, ICE]. As the name implies, unfortunately, this technique works reliably only with UDP.

第三种技术，也是这篇文章主要要研究的，就是非常有名的“UDP打洞技术”，UDP打洞技术依赖于由公共防火墙和cone NAT，允许适当的有计划的端对端应用程序通过NAT“打洞”，即使当双方的主机都处于NAT之后。这种技术在 RFC3027的5.1节[NAT PROT] 中进行了重点介绍，并且在Internet[KEGEL]中进行了非正式的描叙，还应用到了最新的一些协议，例如[TEREDO,ICE]协议中。不过，我们要注意的是，“术”如其名，UDP打洞技术的可靠性全都要依赖于UDP。

We will consider two specific scenarios, and how applications can be designed to handle both of them gracefully. In the first situation, representing the common case, two clients desiring direct peer-to- peer communication reside behind two different NATs. In the second, the two clients actually reside behind the same NAT, but do not necessarily know that they do.

这里将考虑两种典型场景，来介绍连接的双方应用程序如何按照计划的进行通信的，第一种场景，我们假设两个客户端都处于不同的NAT之后；第二种场景，我们假设两个客户端都处于同一个NAT之后，但是它们彼此都不知道(他们在同一个NAT中)。

3.3.1. Peers behind different NATs 处于不同NAT之后的客户端通信

Suppose clients A and B both have private IP addresses and lie behind different network address translators. The peer-to-peer application running on clients A and B and on server S each use UDP port 1234.? A and B have each initiated UDP communication sessions with server S, causing NAT A to assign its own public UDP port 62000 for A’s session with S, and causing NAT B to assign its port 31000 to B’s session with S, respectively.

我们假设 Client A 和 Client B 都拥有自己的私有IP地址，并且都处在不同的NAT之后，端对端的程序运行于 CLIENT A,CLIENT B,S之间，并且它们都开放了UDP端口1234。 CLIENT A和CLIENT B首先分别与S建立通信会话，这时NAT A把它自己的UDP端口62000分配给CLIENT A与S的会话，NAT B也把自己的UDP端口31000分配给CLIENT B与S的会话。如下图所示：

Now suppose that client A wants to establish a UDP communication session directly with client B.? If A simply starts sending UDP messages to B’s public address, 138.76.29.7:31000, then NAT B will typically discard these incoming messages (unless it is a full cone NAT), because the source address and port number does not match those of S, with which the original outgoing session was established. Similarly, if B simply starts sending UDP messages to A’s public address, then NAT A will typically discard these messages.

假如这个时候 CLIENT A 想与 CLIENT B建立一条UDP通信直连，如果 CLIENT A只是简单的发送一个UDP信息到CLIENT B的公网地址138.76.29.7:31000的话，NAT B会不加考虑的将这个信息丢弃（除非NAT B是一个 full cone NAT），因为 这个UDP信息中所包含的地址信息，与CLIENT B和服务器S建立连接时存储在NAT B中的服务器S的地址信息不符。同样的，CLIENT B如果做同样的事情，发送的UDP信息也会被 NAT A 丢弃。

Suppose A starts sending UDP messages to B’s public address, however, and simultaneously relays a request through server S to B, asking B to start sending UDP messages to A’s public address.? A’s outgoing messages directed to B’s public address (138.76.29.7:31000) cause NAT A to open up a new communication session between A’s private address and B’s public address. At the same time, B’s messages to A’s public address (155.99.25.11:62000) cause NAT B to open up a new communication session between B’s private address and A’s public address. Once the new UDP sessions have been opened up in each direction, client A and B can communicate with each other directly without further burden on the “introduction” server S.

假如 CLIENT A 开始发送一个 UDP 信息到 CLIENT B 的公网地址上，与此同时，他又通过S中转发送了一个邀请信息给CLIENT B，请求CLIENT B也给CLIENT A发送一个UDP信息到 CLIENT A的公网地址上。这时CLIENT A向CLIENT B的公网IP(138.76.29.7:31000)发送的信息导致 NAT A 打开一个处于 CLIENT A的私有地址和CLIENT B的公网地址之间的新的通信会话，与此同时，NAT B 也打开了一个处于CLIENT B的私有地址和CLIENT A的公网地址(155.99.25.11:62000)之间的新的通信会话。一旦这个新的UDP会话各自向对方打开了，CLIENT A和CLIENT B之间就可以直接通信，而无需S来牵线搭桥了。(这就是所谓的打洞技术)！

The UDP hole punching technique has several useful properties. Once a direct peer-to-peer UDP connection has been established between two clients behind middleboxes, either party on that connection can in turn take over the role of “introducer” and help the other party establish peer-to-peer connections with additional peers, minimizing the load on the initial introduction server S. The application does not need to attempt to detect explicitly what kind of middlebox it is behind, if any [STUN], since the procedure above will establish peer- to-peer communication channels equally well if either or both clients do not happen to be behind a middlebox.? The hole punching technique even works automatically with multiple NATs, where one or both clients are removed from the public Internet via two or more levels of address translation.

UDP打洞技术有很多实用的地方：第一，一旦这种处于NAT之后的端对端的直连建立之后，连接的双方可以轮流担任 对方的“媒人”，把对方介绍给其他的客户端，这样就极大的降低了服务器S的工作量；第二，应用程序不用关心这个NAT是属于cone还是symmetric，即便要，如果连接的双方有一方或者双方都恰好不处于NAT之后，基于上叙的步骤，他们之间还是可以建立很好的通信通道；第三，打洞技术能够自动运作在多重NAT之后，不论连接的双方经过多少层NAT才到达Internet，都可以进行通信。

超级简单Python Socket Server一例

Posted by & filed under Programming.

中午，公司太吵，闲着无聊，用python自己跟自己说话，算是YY吧，hoho

server端代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# -*- coding: utf-8 -*-
from socket import *
import sys, time, encodings
 
if __name__ == '__main__':
	if len(sys.argv) < 2:
		print u'请输入端口号'
	else:
		sockobj = socket(AF_INET, SOCK_STREAM)
		sockobj.bind( ('', int(sys.argv[1])) )
		sockobj.listen(2)
		while True:
			connection,address = sockobj.accept()
			rcvd = connection.recv(1024)
			if not rcvd :
				pass
			else:
				print u'收到:', rcvd.decode('utf-8').encode('gb2312')
				print u'发送：能'
				connection.send("能")
				break
			connection.close()

Client端代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#coding: utf-8
from socket import *
import time
 
if __name__ == '__main__':
	sockobj = socket(AF_INET, SOCK_STREAM)
	sockobj.connect(('localhost', 2828) )
	send_info = "能收到信息吗？"
	time.sleep(1)
	print u"发送:", send_info.decode("utf-8").encode("gbk")
	sockobj.send(send_info)
	rcvd = sockobj.recv(1024)
	print u"收到：", rcvd.decode('utf-8').encode('gb2312')
	sockobj.close()
	print u"完成"

特别说明一下，我是在Windows下面搞的，CMD默认只能显示GBK编码，所以在print的时候转来转去，如果在Linux终端，直接显示就行了

N-Gram学习笔记

Posted by & filed under Study & Reading.

统计语言模型

假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)：

这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定：

N-Gram模型

当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。
N-Gram模型被称为一阶马尔科夫链。 N的值不能太大，否则计算仍然太大。
根据最大似然估计，语言模型的参数：

其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数

平滑技术的引入

传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求：

N>>K

其中K为随机变量能够取到的值的个数。

实际语言模型中往往无法满足这个要求。
例如：词性标注问题，共有140个可能的标记，考虑当前词前后两个词的影响的三阶模型。

K=140*140*140=2,744,000

给定一个10万词左右的人工标注训练集，即

N=100,00，可见训练数据显得非常不足。

假设k泛指某一事件，N(k)表示事件k观察到的频数，极大似然法使用相对频数作为对事件k的概率估计：

p(k)=N(k)/N

在语言模型中，训练语料中大量的事件N(k)=0，这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。
这种零值的概率估计会导致语言模型算法的失败，例如：概率值作为乘数会使结果为0，而且不能做log运算。
计数等价类

根据对称性原理，事件除了出现次数之外不应具有细节特征，即所有具有相同计数r=N(k)的事件k（事件出现的次数称为事件的计数）应当具有相同的概率估计值，这些计数相同的事件称为计数等价，将它们组成的一个等价类记为计数等价类Gr。
对于计数为r的计数等价类，定义nr为等价类中成员的个数，pr为等价类中事件的概率，R是最大可能出现的计数次数，则
交叉检验

交叉检验就是把训练样本分为m份，其中一份作为保留部分，其余m-1份作为训练部分。训练部分作为训练集估计概率pr，保留部分作为测试集进行测试。
我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计，即使对数似然函数最大化：
使用拉格朗日乘子解决约束条件下的最大值问题，即：
对pr求偏导，得到交叉检验估计：
如果测试部分也作为保留部分的话，就是典型的极大似然估计：
留一估计

留一方法是交叉检验方法的扩展，基本思想是将给定N个样本分为N-1个样本作为训练部分，另外一个样本作为保留部分。这个过程持续N次，使每个样本都被用作过保留样本。
优点：充分利用了给定样本，对于N中的每个观察，留一法都模拟了一遍没有被观察到的情形。
对于留一方法，pr的极大似然估计为：
Turing-Good公式

因为nRpR与1相比一般可以忽略，留一估计公式可以近似为：
留一估计可以利用计数r=1的事件来模拟未现事件，对于未现事件有如下估计：

这个公式就是著名的Turing-Good公式。

空等价类

留一估计中要求么个nr均不为0，在实际问题中当r=5时，这个要求通常都不能满足，即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序：
对应的出现r(l)次的事件的个数记为nr(l)，在进行留一估计时，使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1，留一估计公式变为：

式中对空的等价类没有估计概率，因为空等价类并没有对应任何有效事件。
Turing-Good估计的优缺点和适用范围
缺点：( 1 )无法保证概率估计的“有序性”，即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似，好的估计应当保证pr<=r/N。
优点：其它平滑技术的基础。
适用范围：对0<r<6的小计数事件进行估计。
约束留一估计
单调性约束：pr-1<=pr；折扣约束：p<=r/N。
约束留一估计：让计数估计r*=pr•N处于距其最近的绝对频数之间：

在这个约束下，单调性约束自然满足。
计算方法：计算m时检查每个pr是否满足约束，不然就用约束的上下界进行裁剪，然后重新计算m，一直迭代下去直到所有pr满足约束。
折扣模型
Katz指出Turing-Good公式实质是对模型中观察到的事件进行折扣，将折扣得来的概率摊到所n0个未现事件中。在这个思想的指导下，估计公式可以下成如下形式：
其中，dr是对计数为r的事件的计数的一个折扣函数。
绝对折扣模型
若折扣函数定义为：dr=b，其中b为一个大于0的常数。那么未现事件的总概率为：
对应绝对折扣模型的估计公式为：
线性折扣模型
若折扣函数定义为：dr=a·r，其中a为一个大于0的常数。那么未现事件的总概率为：
对应线性折扣模型的估计公式为：
若a=n1/N，则n0p0=n1/N，与Turing-Good估计相同。

删除插值法（Deleted Interpolation）
其基本思想是，由于N-Gram比N+1-Gram出现的可能性大的多，所以使用N-Gram估计N+1-Gram的概率，例如trigram的计算公式如下：

其中，

参数l的确定：将训练数据分为两部分，一部分用于估计f(wi| w1w2…wi-1)，一部分用于计算参数l，求使语言模型的困惑度最小的l。

Django 1.2.1 CSRF verification failed. Request aborted.

Posted by & filed under Excellence Article, Programming.

I was getting this 403 error today while attempting to make a POST request to a view:
403 Forbidden

CSRF verification failed. Request aborted.
Help

Reason given for failure:

CSRF cookie not set.

Hopefully this saves you some time because I sure wasted a lot of mine solving it.  I ended up having to add ‘django.middleware.csrf.CsrfViewMiddleware’, and  ‘django.middleware.csrf.CsrfResponseMiddleware’ to my MIDDLEWARE_CLASSES in settings.py and my problems were solved.  All I had to say was mutha eff.  Django also was no help with their debug.  My MIDDLEWARE_CLASSES now looks like:

MIDDLEWARE_CLASSES = (
'django.middleware.common.CommonMiddleware',
'django.contrib.sessions.middleware.SessionMiddleware',
'django.middleware.csrf.CsrfViewMiddleware',
'django.middleware.csrf.CsrfResponseMiddleware',
'django.contrib.auth.middleware.AuthenticationMiddleware',
'django.contrib.messages.middleware.MessageMiddleware',
)

Hope this helps.

Windows平台安装Python2.6 和 MySQL-Python

Posted by & filed under Excellence Article, Programming.

Python 版本：2.6
下载地址：http://www.python.org/download/releases/2.6.1/
下载msi文件并安装

MySQLdb版本： MySQL-python-1.2.2.win32-py2.6.exe
下载地址：http://home.netimperia.com/files/misc/MySQL-python-1.2.2.win32-py2.6.exe
参见：http://sourceforge.net/forum/forum.php?thread_id=2316047&forum_id=70460

常见问题：
1.ImportError: DLL load failed: 找不到指定的模块。
—————————————————————————————————-
D:\Program Files\Python2.6>python
Python 2.6.1 (r261:67517, Dec  4 2008, 16:51:00) [MSC v.1500 32 bit (Intel)] on win32
Type “help”, “copyright”, “credits” or “license” for more information.
>>> import MySQLdb
Traceback (most recent call last):
File “<stdin>”, line 1, in <module>
File “D:\Program Files\Python2.6\Lib\site-packages\MySQLdb\__init__.py”, line 19, in <module>

import _mysql
ImportError: DLL load failed: 找不到指定的模块。
—————————————————————————————————-
解决方法：下载libmmd.dll(附件)和libguide40.dll(附件)两个dll文件并复制到python安装目录的Lib\site-packages下。
参见：http://sourceforge.net/forum/message.php?msg_id=5613887

2.ImportError: DLL load failed: 找不到指定的模块。
—————————————————————————————————-
D:\Program Files\Python2.6>python
Python 2.6 (r26:66721, Oct  2 2008, 11:35:03) [MSC v.1500 32 bit (Intel)] on win32
Type “help”, “copyright”, “credits” or “license” for more information.
>>> import MySQLdb
D:\Program Files\Python2.6\lib\site-packages\MySQLdb\__init__.py:34: DeprecationWarning: the sets module is deprecated
from sets import ImmutableSet
—————————————————————————————————-
解决方法：
1) file “__init__”, replace:

from sets import ImmutableSet
class DBAPISet(ImmutableSet):

with

class DBAPISet(frozenset)

2) file “converters.py”, remove:

from sets import BaseSet, Set

3) file “converters.py”, change “Set” by “set” (IMPORTANT: only two places):

line 45: return set([ i for i in s.split(',') if i ])
line 128: set: Set2Str,
参见：http://sourceforge.net/forum/message.php?msg_id=5808948

附件:
libguide40.dll.zip(77.3 KB)
libmmd.dll.zip(169 KB)
libmySQL.dll.zip(861 KB)
原文: http://www.3gmatrix.cn/4/viewspace-16757.html

无题

Posted by & filed under Life Diary.

最近项目一直压得喘不过气来，博客荒废了很久了，不过还好养成了在睡觉前将当天google reader中新的文章全部看完，PHP领域缺乏新意，每每有几篇文章出来也是跟我这样的庸俗后生一样泛泛而谈，大多已经了解，没有激起半点欲望。倒是蔡学镛老师的最近几篇文章激起我更多的感慨和思考，蔡以技术而成名，而最近几篇文章却一直避而不谈技术，这是技术者的反思，顺着他的思路，我也来感慨一下。
1、谈敬业
蔡学镛说：即使是面对自己不喜欢、违反自己的意愿与志趣（但不违反法律）的工作，依然努力去完成，这就是敬业。我赞成这个定义，按照这个标准，我进入阿里集团的头几个月是不敬业的，因为我迷失的，发现根本跟当初想象的是两回事。现在我觉得我是敬业的，因为我已经忘记了工作时的兴趣，也就是把工作和兴趣完全分开了，兴趣回家搞，工作公司搞，努力把一天的Todo List完成，回家捣鼓自己的玩意，越早越好，这就是我现在的状态，因此我开始避免和逃避加班，因为那妨碍我搞兴趣。我会有点抵触的情绪。因为既然工作不能足够的吸引我，那么我只好在9小时以外的时间来处理了，这一点上我觉得阿里云这样的纯技术公司，至少目前是纯技术公司应该向google学习，每天赶进度不是一个公司的长久，神天天或者非常之经常加班也会烦的。
2、主管应该写周报给下属
我觉得蔡在写下这个题目时一定有很多疑惑，遭受过很多碰壁，经历过很多疑惑，我估计每个做下属都这样，我不知道我的头在干嘛，我不知道做的事情我的头知道多少，我今天只干了一点点东西，我日报或者周报上写了一堆东西，我的头知道么？为什么我找头商量某个实现或者某个方案的时候，他总是不在？他是怎么干活的？我要怎么样才能晋升到他那个位置？他为什么有开不完的会？他为我做了什么？他为公司做了什么？他凭什么他处于现在的位置？
3、KPI心理学
蔡说对KPI的重视程度分为四个阶段，70% -> 30% -> 100% -> 0%，我身边有大把的人对KPI重视程度出于第三个阶段，每天KPI不离口，一提到工作就是KPI，会议上一讨论任务或者接下来的工作的时候就是KPI，我仔细想想，我也许出于第二个阶段，也许处于第四个阶段，或许未来我也会走到100% KPI导向，为了年终奖，为了晋升，也许我觉得这个不是我该做的，那么我会选择离开。KPI这个东西，我觉得有点像中国的考试制度，明知道有弊端，还是无可争议的引入，KPI驱动会让战略任务得以完成，也会失去很多东西，销售因为KPI可能会不停的骚扰客户，这已经不是什么个案了，技术会因为KPI而码一些纯粹为了需求的不够健壮的代码，运营会因为KPI而弄虚作假，如此等等……
4、程序员的激情之道

曾经有人质疑我为何老是要在项目中采用新技术，是不是为了显示自己很不一样，很厉害？其实这根本就误解我了。我只是通过新技术保持我的激情，新技术就是我的毒品呀！

让一个技术人员保持一种激情我觉得很简单，技术，学习就足够了，阿里内部有很多很多形形色色的分享，每次分享邮件从outlook中弹出来的时候，我都点了Accept，事实上，我只去过一次，关于淘宝搜索广告的分享，分享完毕了之后，我觉得那天是我进入阿里以后收获最多的一天，心情最好的一天，其他的时间分享我也很想去，可是我没有时间，如果我去了，我的项目就无法完成。一个个活生生的例子是一个同事因为对淘宝的数据库架构太感兴趣了，跑过去听了，回来就给他的领导给批评了，好吧，我也想去听，只是我更知道揣测圣意。每个员工都很忙，分享的同学或许是出于自己的兴趣或者分享精神，或许是主管的要求，或许是KPI驱动（分享对KPI评审有加分），这都没有关系，问题是去听的人每次都那么少，我听的那次虽然是京杭同步的视频会议分享，到场者寥寥
5、你被截肢了吗？

在大公司中，员工只需要单一方面的工作表现到极致，就可以为公司做出贡献。但是，如果员工有两方面的能力，甚至三方面、四方面的能力都很突出，这些多出来的能力就无法得到发挥，会受到压抑，导致萎缩。

这是一个悲剧，但这个悲剧在大公司都会出现，我觉得每个优秀的技术性公司向伟大的公司转变的时候都应该学习google，让20%的时间释放多面手员工的技术和创意，未必影响公司的运转和产出，说不定能增加员工对公司的忠诚度和依赖度。