月度归档:2012年01月

有限自动机的字符串匹配

自动机虽然是通过很多数学知识来论证其正确性,但是其原理确很简单。这里通过加回忆之前的学习,简单介绍下自动机的字符串匹配原理。自动机的字符在完成前期的工作后,其字符串的匹配时间复杂度为O(n),其中n为目标串的字符数,即自动机的匹配搜索不需要回溯,其如何完成避免回溯工作的呢? 继续阅读

监控项目分析报告-系统架构

通过上面的需求分析可以清晰地看到整个监控系统外部的数据流:

  1. 接收数据流很大,送出数据流很小;
  2. 接收数据流为内容数据,送出数据流为控制数据;
  3. 内容数据在系统两端进行处理,前端机器处理为硬实时(秒级),后端人工处理为软实时(时级);
  4. 控制数据在系统两端都有送出,送出时间与其对应的内容数据处理的时间点一致,处理完内容数据即送出。控制数据内容为对应各个产品对其产品内容数据的控制动作。 继续阅读

python源码分析:dict对象的实现-2

你是否对上面那个lookdict提出过疑问?

对啦,没有退出语句,它不会成为死循环吧,不会!下面马上提晓答案。

看下面这段代码,位于PyDict_SetItem中:

if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
return 0;
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

即dict在插入数据时,都会检查hash空间使用情况,一旦新添加一条且(dummy+used)的数量小于空间总大小的2/3,就会执行dictresize,就会来扩展原有的hash空间,从而始终保证空间中有空闲位置,这样上面那个’死循环‘的疑问就解决了

2/3:还有一个原因,就是根据统计结果,发现装载率超过2/3后冲突率就会急剧升高。 继续阅读

MySQLdb sql转义与编码处理

进行转义操作时,MySQLdb.escape_string(sql) 中sql的编码是utf8(前提相关表的connection-charset为utf8,即与数据库的connection-charset保持一致)。

由于不管connection的charset是什么,cursor.execute只需要unicode的字符串,在执行上面的转义sql时,需要解码:execute(MySQLdb.escape_string(sql).decode('utf8'))。