红黑树

红黑树是一种很常用的自平衡二叉树。之前写过二叉搜索树,我们知道二叉搜索树查找速度是由树的高度决定的,但是因为二叉搜索树对树的平衡没什么限制,如果所有节点都在一个叉上,就变成了链表了。红黑树作为二叉搜索树的同时,用以下五个性质保证了树的平衡:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

因为这些性质,一棵红黑树尽量保持每个路径上节点数差距不大,从来保证了树的查找速度。

红黑树

红黑树是一颗二叉搜索树,其查找方法自然也就是二叉搜索树的查找方法。因为给二叉搜索树节点涂了颜色,树上面的修改操作(如插入、删除)会影响红黑树的某些性质,恢复其性质需要需要O(log n) 次操作。

继续阅读

二叉查找树

二叉查找树英语Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合multiset关联数组等。

二叉查找树是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的节点(英语:no duplicate nodes)。

注:维基百科和百度百科上性质【1】和【2】不同,描述中的一个性质会存在键值相等的情况,考虑到性质【4】,是不应该存在这个相等情况的。

注:以上定义摘自维基百科(微幅修改)。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,等于树高,期望为O(log n),最坏为O(n)。

二叉查找树

两个高度相同的二叉查找树

上面的两个二叉查找树树高是一样的,但是查找是速度是相同的。

下面介绍二叉查找树的一些操作:

继续阅读

PHP访问类私有元素

从PHP5开始,我们通过反射类来访问私有方法:

继续阅读

linux内核同步方法-原子操作

转自:edsionte's TechBlog

原子操作

原子操作用于执行轻量级、仅执行一次的操作,比如修改计数器,某些条件下的增加值或设置位等。原子操作指的是指令以原子的方式执行。之所以用原子来修饰这种操作方式是因为它们均不可再分。也就是说,原子操作要么一次性执行完毕,要么就不执行,这些操作的执行过程是不可被打断的。原子操作的具体实现取决于体系架构,以下代码如无特别声明,均来自linux/arch/x86/include/asm/atomic.h中

内核中提供了两组原子操作的接口:原子整形操作和原子位操作。前者是一组对整形数据的操作,后者则是针对单独的位操作。通过上面的叙述我们可以知道,这写操作接口完成的动作都是原子的。

继续阅读

python生成时间分割的日志

日常写应用写日志是再常见不过的事情,用python的时候发现python自带一个日志模块还挺好用的,不仅支持常见的日志分隔方案,还支持输出到各种位置(比如文件、SMTP、内存)。

网上有大量的logging模块使用教程(可以见后面的参考),这里仅说说按照时间分割的方案。

logging模块按照时间分隔可以使用TimedRotatingFileHandler,logging模块提供三个基本的handler:StreamHandlerFileHandlerNullHandler,其他的handler放在logging.handlers里面,所以需要使用TimedRotatingFileHandler则需要import logging.handlers

logging分割日志用先往默认的文件(test.log)里打,等到分割条件的时候,把之前打的那部分日志转移到对应的分割文件里(上例中就是test.log.20141016.18),这样的好处就是每次最新的都在test.log中,不过你想统一后缀(比如test.2014101618.log)似乎有点困难了,而且应该会有额外的开销。

这里仅仅是简单解释了一下logging的时间分割文件方法,不是一个十分基础和详细的文章,如果您需要更详细的内容还请看下面的参考文章。

参考:

python logging使用方法(官方)
python logging模块文档(官方文档)
python logging TimedRotatingFileHandler(官方文档)
使用python的logging模块
python标准日志模块logging及日志系统设计
python logging现学现用 – TimedRotatingFileHandler使用方法

python-snappy编译安装遇到的问题

最近使用snappy压缩数据,编译python-snappy的时候,因为没有root权限,只好自己来指定链接的地址。

build的时候发现没有可以指定的选项,只好通过指定CPLUS_INCLUDE_PATH到snappy库的include目录,指定LIBRARY_PATH到snappy的lib目录。

成功安装snappy。

之后引入snappy模块的时候,发现没有安装ffi库,真是杯具呀。编译libffi到指定目录,启动python发现python找不到这个库。

python不是查找LIBRARY_PATH和CPLUS_INCLUDE_PATH的,是通过查找C_INCLUDE_PATH和LD_LIBRARY_PATH来找到对应的头文件和库文件的。

所以我们需要把libffi和snappy的路径指定上:

snappy终于可以用啦。

如果需要每次都生效就把export语句放到.bashrc中就可以了。

php使用反射访问私有元素

php的反射机制可以让使用者获取到一些元素的运行信息、状态等,我们可以通过ReflectionClass导出类、访问其元素、获取类定义信息等,可以通过ReflectionFunctionReflectionMethodReflectionProperty等类访问函数、方法、属性之类元素的信息。

下面是一个可以访问私有元素的类,通过ReflectionMethodReflectionClass实现:

反射类比较强大,用类的方法实现也更加直观。为我们进行一些简单测试或者工具制作上提供了不小的便利。

pymongo保存snappy压缩数据

在使用python snappy压缩以后的数据,保存到mongo时报字符串编码错误,错误内容和下面的差不多:

bson.errors.InvalidStringData
strings in documents must be valid UTF-8

这时候可以使用bson binary格式来保存这类数据:

以上,希望能对你起到帮助。