一、红黑树的好处及用途
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以O(lgn)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构,能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性，典型的用途是实现关联数组。
二、AVL树
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查 找、插入和删除在平均和最坏情况下都是O(lg n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于 它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度。 Continue reading »
五 092012
五 052012
许多Web应用都将数据保存到RDBMS中，应用服务器从中读取数据并在浏览器中显示。但随着数据量的增大、访问的集中，就会出现RDBMS的负担加重、数据库响应恶化、网站显示延迟等重大影响。这时就该memcached大显身手了。memcached是高性能的分布式内存缓存服务器。一般的使用目的是，通过缓存数据库查询结果，减少数据库访问次数，以提高动态Web应用的速度、提高可扩展性。关于memcached的详情及原理请参考《Memcached深度剖析(转)》，下面就Linux下对memcached的安装与使用进行简单介绍。
安装环境：Ubuntu11.04 + libevent-2.0.18 + memcached-1.4.13 + libmemcached-1.0.4
一、安装libevent
由于memcached用到了libevent这个库中关于Socket的处理，所以安装memcached之前需安装libevent，目前（2012.5.2）最近版本是libevent-2.0.18-stable.tar.gz，安装方法如下：
#tar zxvf libevent-2.0.18-stable.tar.gz
#cd libevent-2.0.18-stable
#./configure –prefix=/usr/local/libevent
#make
#make intsall
二、安装memcached服务器
安装memcached时需要指定libevent的安装路径，目前（2012.5.2）最新版本是memcached-1.4.13.tar.gz，安装方法如下：
#tar zxvf memcached-1.4.13.tar.gz Continue reading »
五 022012
对于普通的C++对象内存布局，比较简单，就不做总结了。这里只总结涉及到虚拟继承的情况。
因为不同编译器对虚拟继承的实现采用不同的方式，所以要完整的分析是不可能的。这里只考虑VS2005/2008，还有简单涉及GCC编译器。
1、单个虚拟继承
只是为了分析而已，实际中并没有太大的作用。跟虚拟继承相关的派生类对象的内存布局跟具体的编译器相关。
（1）VS编译器：无论有无虚函数，必然含有虚基类表指针。虚基类表中的内容为本类实例的偏移和基类实例的相对偏移值。如果有虚函数，那么基类的虚函数表跟派生类的虚函数表是分开的。
在内存布局上，地址从低到高，顺序如下：派生类的虚函数表指针+虚基类表指针+派生类的成员变量+“间隔”（4个字节）+基类的虚函数表指针+基类的成员变量。派生类跟基类实例的位置关系跟普通继承正好相反。
说明：“间隔”产生的原因是派生类重写了基类的虚函数。如果没重写，则这一项没有。”本类地址”指的是包含有虚基类的对象（或部分对象），也就是继承链上的直接子类对象的地址，本例比较简单，就是派生类对象地址。“本类地址跟虚基类表指针地址只差”，这个值经常是-4、0，-4表明“本类”还有一个虚函数表指针；0则表明“本类”的第一个4字节保存的就是虚基类表指针，没有虚函数表指针。 Continue reading »
四 082012
首先分清楚Stack，Heap的中文翻译：Stack——栈，Heap——堆。
在中文里，Stack可以翻译为“堆栈”，所以查找了计算机术语里面堆和栈开头的词语：
堆存储: heapstorage； 堆存储分配: heapstorage allocation； 堆存储管理: heap storage management；
栈编址: stack addressing； 栈变换: stack transformation； 栈存储器: stack memory； 栈单元: stack cell.
接着，总结在Java里面Stack和Heap分别存储数据的不同。
关于Stack和Heap更多具体的存储原理及区别，参考《栈(Stack)和堆(Heap)的区别》
1. 保存对象实例，实际上是保存对象实例的属性值，属性的类型和对象本身的类型标记等，并不保存对象的方法（方法是指令，保存在stack中），对象实例在heap中分配好以后，需要在stack中保存一个4字节的heap内存地址，用来定位该对象实例在heap中的位置，便于找到该对象实例；
2. 基本数据类型包括byte、int、char、long、float、double、boolean和short，函数方法属于指令。 Continue reading »
四 052012
一、关于栈(Stack)和堆(Heap)的问题:
栈(Stack）：由操作系统分配和回收，函数调用的参数及其内部局部变量就是从这分配。其特点是：分配容量有限且连续比较固定，但不容易引起内存泄露。
堆(Heap）：易称动态分配，是由程序员自己分配和回收的，如程序员用new, malloc分配内存，用delete, free来释放内存。若在程序结束时，未回收则由操作系统来完成回收工作。其特点是：分配容量较大且比较灵活，且内存不要求连续，但容易造成内存泄露；
注：它们都不同于数据结构中的堆栈结构，需要区分理解。补充解释：
操作系统里的堆和栈是指对内存进行操作和管理的一些方式. 数据结构里面的堆实际上指的就是（满足堆性质的）优先Queue的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构. 堆栈的说法是连起来叫,但是他们还是有很大不同的,连着叫只是由于历史的原因。
简单地讲“堆栈”（栈）就是一个序列,这个序列按照后进先出(POP/PUSH)的规则组织。
“栈”就是整齐的货物一个挨一个地码在一起.整齐的货物就是同样的数据类型.最后码上去的肯定在最上边,最上边的也肯定是最先搬下来. “堆”应该是”堆栈”的一种推广.按照某种优先原则组织的一组数据. “堆”就是一些货物看似杂乱无章地堆在一起,但是可以按某种原则每次取一个出来.”二叉堆”像不像一个堆成金字塔的货堆?
“堆栈”（栈）是”堆”的优先原则的一种特例。
Continue reading »
三 242012
本文的目的是用简明扼要的语言向你解释这三个时下最流行的IT术语（云计算、社交网络和移动互联网）的实质，分析它们的问题，并预测未来趋势。
什么是云计算
首先是云计算。时至今日，我的身边还常有朋友问起，这个喊得震天响的云计算，到底是什么东西？开始时我也会解释一大堆话，后来发现，简单记得住最管用。于是概括为一句：云计算就是互联网，互联网就是云计算。而云计算的用处，或者说目的，是要将个人电脑（台式机也好笔记本也好）放到互联网中。
什么叫个人电脑放到互联网中？举例来说，你能直接在网络上看电视剧，并且可以在任何能上网的地方接着看同一部电视剧。而在几年前，你可能得先把电视剧一集集下载到你的个人电脑里，还得先安装好暴风影音这样的播放软件。换句话说，原本属于个人电脑的功能，现在被互联网替代了。
云计算的最终目的，就是要取代个人电脑的全部功能，这就叫把个人电脑放到网络里。云计算将最终让你能够在任何时间任何地点做任何与电脑相关的事，还不用随身带着笔记本或者U盘，因为你需要的所有数据、软件都在云中，在你的网络账户里。 Continue reading »
可能不少人会问，Linux下什么类型的可用软件最多？答案是文本处理程序。除了常见的Grep、more、less、cat、awk等文本显示和处理程序外，更多的，就是文本编辑器了。在新立得下试着搜索一下，能够找到的文本编辑器简直可以按“堆”来计算。这里，简单介绍一下Linux下常用的gedit文本编辑器配置方法，以方便初学者能够较快地适应Linux的使用环境。其实对于Linux下将文本编辑器配置成IED还有其他文本编辑器，比如Emacs、Editra，Geany，有些其功能远比gedit文本编辑器强大。由于个人精力和知识有限，难免有些介绍会有遗漏，如哪位朋友发现相关错误，请在评论中告知。 ^ ^
gedit是Gnome默认的文本编辑器，不少人把它当作Windows下记事本的替代品。但事实上它也十分强大，大量插件的支持，让用户可以实现大部分他们想要的功能。同样支持语法高亮。经过配置后，可以把它当作一款“准IDE”使用。下面就针对一些简单方法将Linux下的默认文本编辑器进行配置进行介绍。 Continue reading »
十二 182011
一、Java内存管理机制
在C++语言中，如果需要动态分配一块内存，程序员需要负责这块内存的整个生命周期。从申请分配、到使用、再到最后的释放。这样的过程非常灵活，但是却十分繁琐，程序员很容易由于疏忽而忘记释放内存，从而导致内存的泄露。Java语言对内存管理做了自己的优化，这就是垃圾回收机制。Java的几乎所有内存对象都是在堆内存上分配（基本数据类型除外），然后由GC（garbage collection）负责自动回收不再使用的内存。
上面是Java内存管理机制的基本情况。但是如果仅仅理解到这里，我们在实际的项目开发中仍然会遇到内存泄漏的问题。也许有人表示怀疑，既然Java的垃圾回收机制能够自动的回收内存，怎么还会出现内存泄漏的情况呢？这个问题，我们需要知道GC在什么时候回收内存对象，什么样的内存对象会被GC认为是“不再使用”的。
Java中对内存对象的访问，使用的是引用的方式。在Java代码中我们维护一个内存对象的引用变量，通过这个引用变量的值，我们可以访问到对应的内存地址中的内存对象空间。在Java程序中，这个引用变量本身既可以存放堆内存中，又可以放在代码栈的内存中（与基本数据类型相同）。GC线程会从代码栈中的引用变量开始跟踪，从而判定哪些内存是正在使用的。如果GC线程通过这种方式，无法跟踪到某一块堆内存，那么GC就认为这块内存将不再使用了（因为代码中已经无法访问这块内存了）。
通过这种有向图的内存管理方式，当一个内存对象失去了所有的引用之后，GC就可以将其回收。反过来说，如果这个对象还存在引用，那么它将不会被GC回收，哪怕是Java虚拟机抛出OutOfMemoryError。 Continue reading »
近期评论