堆排序

上次写了个快排的文章,果不其然被大家鄙视了。大概平时是一个写脚本的,这东西也不会了,大学时代还能帮别人替考c语言,现在连c都不会了。

回归正题,这里使用二叉堆,二叉堆是一个近似的完全二叉树,在很多地方都会用到这个结构。

通常使用数组来表示一个堆:假设数组第一个元素为根节点,那么它的左孩子节点就是第二个元素,右孩子节点为第三个元素。以此类推,假设一个节点是数组的第n个元素,它的左孩子节点就是第2n个元素,右孩子节点就是2n+1,可以使用floor(n/2)来获取其父节点。

二叉堆分为最大堆(MAX-HEAP,大顶堆)和最小堆(MIN-HEAP,小顶堆),最大堆就是父节点的值大于或等于子节点值的堆,所以根节点应该是最大的节点,最小堆反之。这里使用了最大堆。

继续阅读

php的traits和单例

最近和同事聊天时发现很多同事并不了解php的一些特性。有时他们会说python的某些特性非常有趣,确实,但我提到php中也存在一些类似特性的时候,他们表示并不了解,于是考虑写几篇关于php特性的文章。如果其他语言有这类特性,我会尝试着对比来讲解。

phper们应该都知道在5.4以后增加了一个新特性叫做traits,其文档如下:

http://php.net/manual/zh/language.oop5.traits.php

traits感觉像是让你更方便的复制粘贴代码,这些代码统一的管理着。你可以使用trait_exists方法来检查traits是否存在,使用class_uses列出所有使用traits的方法。

网上有些文章吐槽traits这个特性破坏了封装或是如何,我的层次不高,只能默默表示有时候用这东西还是比较舒服的。

比如我们写单例方法,这东西我们的项目中经常性的用到:

为了不让别人初始化,我们需要控制构造函数好克隆方法的权限,然后让类自己检查和初始化自己。

继续阅读

scp被.bashrc中的echo打断问题

很多人喜欢在.bashrc中输出一些东西,比如一些字符画。但是,如果我们往这台机器scp东西的时候,会发现输出了短短一行数据就结束了。

这是因为echo中断了scp,scp会使用标准输入输出来传递自己的协议数据。可以通过如下方式避免这类情况:

  • 通过检查inertactive选项,可以通过这样一个判断来检查:
  • 使用tty来检查,比如:
  • 检查$SSH_TTY的值。

如此就可以区分登录的shell类型,避开对scp的影响了。

参考:SCP doesn't work when echo in .bashrc?

说说python的__del__方法

python中提供一个__del__方法,这个方法在实例释放的时候被调用,被称为析构器。

但最近使用中发现这个析构器和其他语言的析构方法不太一样,存在着一些不确定性。

比如我们在php中可以这样销毁一个对象:

此时php的析构方法__destruct()被调用。

python中我们经常会这样做

标量的销毁是没有任何问题的,但是对于对象来说,因为存在着比较复杂的引用关系,del只是把对象的引用计数减一,而不是直接调用__del__方法,这导致del方法没有达到预期内的效果。

而且,在对象的引用计数为0的时候,垃圾回收也不一定会回收此对象,而__del__方法在垃圾回收的时候才被调用。

同时,使用了__del__以后,python似乎不再追踪和释放循环引用(这点还没有经过确认)。

更多关于__del__的问题可以参考这个stack overflow question : how to call the __del__ method ? 

所以,当我们想像某些其他语言一样在调用完以后执行一些小动作的时候,比如关闭文件句柄、写点小日志之类。可以考虑使用python提供的with方案。下面是一个with的调用方法:

这个demo比较简单,python的open也支持with,但这个重复造的不完整轮子也比较容易解释with结构。这段代码在with语句结束的时候会调用__exit__方法。__enter__方法的返回值会返回给as作为f的值。

当然,__del__早晚会被调用的,如果你不着急而且控制得当,应该是没有任何问题的。

快速排序(ruby版)

前几天有人问起快排,我心想这不难呀,把原理讲完了以后发现自己写不出来……回去默默看着导论用ruby写了一个……

快排使用分治思想。最重要的是分区:取一个基准值,比基准值小的放到数组左边,比基准值大的放到数组右边,基准值自己放到中间。然后对左边和右边的数进行再分区,如此递归直到全部排列好。

基准值是从数组中获取到的,你可以自己选择,或者随机选择一个。如果是随机取基准值的快排,因为无法确定命中最好情况还是最坏情况,所以大量的排序情况下会趋近于期望值。

快排基本上保持着两个变量或者指针,一个是当前迭代到的key,一个是当前需要交换的key。如果达到交换条件(比如迭代到的key对应的值相对比对值小)就和需要交换的key进行交换。这两个变量或者指针可以按照自己的意愿进行调整,不管是从左到右,从右到左,还是分别从两头都行。

本来还想用各种语言都写一遍给大家参考,后来想想我好像有点太无聊了……就先算了吧……

关于redis的传输协议

很久之前就想写这篇,但是因为时间问题一直也没有弄,先粗糙整理一篇。

redis的传输协议(RESP)

redis的协议总体算比较简单,第一个符号表示回复的类型:

"+" 表示是一个简单字符串,一般都是状态消息,比如输入PING命令
"-" 错误返回使用减号,比如输入一条错误命令
":" 返回数字,比如使用INC命令
"$" 表示返回一条字符串安全的字符串,最长512M,比如使用GET命令
"*" 返回的是一组数据,比如使用SMEMBERS命令

如果是"+"、"-"或者":"后面紧跟着消息体,然后跟一个CRLF,CRLF其实就是"\r\n",消息结束。

[+-:]<msg>CRLF

比如:

  •  +PONG\r\n
  • -unknow command 'foobar'\r\n
  • :10\r\n

剩下的两个个形式在第一个符号后面跟着对应的长度表示,然后是CRLF,接着是消息体表示,最后CRLF结尾:

[$*]<LEN>CRLF<BODY>CRLF

这里的<LEN>如果是结果是字符串则表示字符串长度,如果是一组数据则表示元素个数。<BODY>是消息体,如果是字符串则表示字符串长度,如果是一组数据则使用对应的单条数据的表示形式填充(:|$等数据)。如果长度是-1则表示没有这条数据。比如:

  • $6\r\nfoobar\r\n
  • $-1\r\n
  • *0\r\n
  • *2\r\n$3\r\nfoor$3\r\nbar\r\n
  • *5\r\n:10\r\n$-1\r\n$3foor\r\n

redis协议可以参考这篇文档:redis protocol

这里还有篇中文的:通信协议

继续阅读

php 异步执行脚本

最近有个地方需要拉起一个脚本处理任务,起了进程交给init进程发现还是会阻塞,后来找到这篇文章,发现原来自己想的太复杂。

这里说的异步执行是让php脚本在后台挂起一个执行具体操作的脚本,主脚本退出后,挂起的脚本还能继续执行。比如执行某些耗时操作或可以并行执行的操作,可以采用php异步执行的方式。主脚本和子脚本的通讯可以采用外部文件或memcached的方式。原理就是通过exec或system来执行一个外部命令。注意:本文所述的是针对Linux环境。

在Linux下要让一个脚本挂在后台执行可以在命令的结尾加上一个 “&” 符号,有时候这还不够,需要借助nohup命令才能是忽略挂起信号。

继续阅读

mysq使用like查找有反斜杠的数据

不知道什么时候记录的这条了,一直也没发布。

这里的重点是使用like binary,而且使用了四个反斜线。

具体可以参考下面的地址:

http://stackoverflow.com/questions/8583144/mysql-like-operator-with-wildcard-and-backslash

wordpress禁用Google Open Sans字体

这两天打开博客发现十分慢,看了一下网络请求,发现多了一个google样式

搜了一下发现wordpress3.8开始就使用这个google开放字体了,由于google的网络因为一些原因访问异常,所以我们只能想办法禁用掉了。

可以使用【Disable Google Fonts】这个插件禁用这个样式。

PHP autoload和spl_autoload自动加载机制详解 [转]

PHP autoload机制详解

(1) autoload机制概述

在使用PHP的OO模式开发系统时,通常大家习惯上将每个类的实现都存放在一个单独的文件里,这样会很容易实现对类进行复用,同时将来维护时也很便利。这 也是OO设计的基本思想之一。在PHP5之前,如果需要使用一个类,只需要直接使用include/require将其包含进来即可。下面是一个实际的例 子:

在这个例子中,no-autoload.php文件需要使用Person类,它使用了require_once将其包含,然后就可以直接使用Person类来实例化一个对象。

但 随着项目规模的不断扩大,使用这种方式会带来一些隐含的问题:如果一个PHP文件需要使用很多其它类,那么就需要很多的require/include语 句,这样有可能会造成遗漏或者包含进不必要的类文件。如果大量的文件都需要使用其它的类,那么要保证每个文件都包含正确的类文件肯定是一个噩梦。

PHP5为这个问题提供了一个解决方案,这就是类的自动装载(autoload)机制。autoload机制可以使得PHP程序有可能在使用类时才自动包含类文件,而不是一开始就将所有的类文件include进来,这种机制也称为lazyloading。 下面是使用autoload机制加载Person类的例子:

通常PHP5在使用一个类时,如果发现这个类没有加载,就会自动运行__autoload()函数,在这个函数中我们可以加载需要使用的类。在我们这个简 单的例子中,我们直接将类名加上扩展名" title="扩展名">扩展名”.class.php”构成了类文件名,然后使用require_once将其加载。

从这个例子中,我们可以看出 autoload至少要做三件事情,第一件事是根据类名确定类文件名,第二件事是确定类文件所在的磁盘路径(在我们的例子是最简单的情况,类与调用它们的 PHP程序文件在同一个文件夹下),第三件事是将类从磁盘文件中加载到系统中。第三步最简单,只需要使用include/require即可。要实现第一 步,第二步的功能,必须在开发时约定类名与磁盘文件的映射方法,只有这样我们才能根据类名找到它对应的磁盘文件。 继续阅读