快速排序

示例数组:3 1 4 5 9 2 6 8 7   


标识为红色的为需要交换的元素

标识为蓝色的为比较的元素

定义:较小元素是小于或等于枢纽(pivot)的元素,较大元素为大于枢纽的元素(pivot)。

一开始,整个数组将看作为一个较大的分区(partition)。这时,两个坐标同时初始化,一个是由左向右搜索的坐标(我们假设为i),一个是由右向左搜索的坐标(我们假设为k)。

i的坐标是分区的第一个元素,现在为0,这时,k的值是8,分区的最后一个元素。

3 1 4 5 9 2 6 8 7

分区的第一个元素是3,选作枢纽(pivot),然后以这个枢纽为准,分成两个子分区。目标是让前面的分区元素都小于枢纽,但子分区没有特定的排序。

第一个元素3作为pivot元素,目标是前面的元素都比pivot元素要小。

这时,会先向右扫描,找出第一个比3大的元素。一旦找到了,它会从右边开始扫描出第一个比3小的元素。找到的这两个元素会相互交换。

因为现在i设为0,所以枢纽在寻找比它大的元素时会先和自己比较。

3 1 4 5 9 2 6 8 7

查找第一个比枢纽大的元素继续向右,i值随着向右继续增加。

3 1 4 5 9 2 6 8 7

因为4比枢纽3大,这时候向右搜索停止,这样,i的坐标为2。

3 1 4 5 9 2 6 8 7

现在,从数组的最后一个元素开始,查找第一个比枢纽小的元素。随着向左移动,k值不断减小。

3 1 4 5 9 2 6 8 7

3 1 4 5 9 2 6 8 7

3 1 4 5 9 2 6 8 7

因为2比枢纽3小,这时候向左的查找停止。k的坐标为5.

3 1 2 5 9 4 6 8 7

这时,元素2和4交换位置。(分别是位置i=2,k=5)

3 1 2 5 9 4 6 8 7

接着,查找从向右查找的坐标停止的位置继续向右。(i=2的位置)

3 1 2 5 9 4 6 8 7

马上,就找到了比枢纽(这时还是3)大的元素5(i=3),向右查找停止。

3 1 2 5 9 4 6 8 7

这时,向左的查找从刚才停止的位置继续向左扫描比枢纽3小的元素。

3 1 2 5 9 4 6 8 7

3 1 2 5 9 4 6 8 7

3 1 2 5 9 4 6 8 7

这时候比枢纽3小的元素找到了,但这个时候并不需要交换元素。但i的坐标设成k的。

意味着较小的元素已经在一边,较大的元素已经在另外一边。

2 1 3 5 9 4 6 8 7

剩下一样事情还需要做,就是交换枢纽和当前i指向的元素(i=2,上一步已将i的坐标设成和k的一样)。在这算法中,这种交换是有含义的,因为能保证左边的元素都小于枢纽(当前为3)。但他们各自的顺序暂不重要。现在坐标0到坐标(i-1)形成左分区。(k+1)之后的为右分区,包含全部大于枢纽的元素。

现在先对左分区进行排序(前两个)。

2 1 3 5 9 4 6 8 7

2选为枢纽,搜索时仍然先和自己比较。

2 1 3 5 9 4 6 8 7

然后查找到第二个元素(下标为1)比枢纽小。

因为左分区只有两个元素,向左查找的坐标从第二个元素开始,然后找到1。

1 2 3 5 9 4 6 8 7

这时候,左分区有一个元素(1),右分区没有元素。

然后对左分区进行排序,现在左分区只有一个元素,因此不需任何操作。

接着,对右分区(第3个到第8个元素进行排序)   


1 2 3 5 9 4 6 8 7

选中5作为枢纽。   


1 2 3 5 9 4 6 8 7

向右扫描的坐标马上找到9比5大。   


1 2 3 5 9 4 6 8 7

向左扫描的坐标开始。   


1 2 3 5 9 4 6 8 7

1 2 3 5 9 4 6 8 7

1 2 3 5 9 4 6 8 7

最后,找到元素4比枢纽5小。这时候k=5。   


1 2 3 5 4 9 6 8 7

这样,第一个找到比5大的元素和比5小的元素交换位置。   


1 2 3 5 4 9 6 8 7

向右搜索继续。   


1 2 3 5 4 9 6 8 7

找到了比枢纽5大的元素9,向右搜索停止。   


1 2 3 5 4 9 6 8 7

因为刚才k坐标停留在5的位置上,所以向左搜索从坐标5继续。   


1 2 3 5 4 9 6 8 7

1 2 3 4 5 9 6 8 7

对于该分区,最后一步是将枢纽放到正确的位置。这时,左分区只有坐标为3的元素4,右分区是元素(9687)。   


对左分区进行排序(坐标3到坐标3)   


对右分区进行排序(坐标5到坐标8)   


1 2 3 4 5 9 6 8 7

9选作枢纽。   


1 2 3 4 5 9 6 8 7

向右查找第一个比9大的元素开始。   


1 2 3 4 5 9 6 8 7

1 2 3 4 5 9 6 8 7

找不到比9更大的元素。   


1 2 3 4 5 9 6 8 7

向左查找开始,但是不能继续,因为坐标i和k重合了。   


1 2 3 4 5 7 6 8 9

枢纽9和k指向的元素7交换位置。对于子分区,这一步是最后的一步。   


接着,我们对第5到第7个元素排序。   


1 2 3 4 5 7 6 8 9

7选为枢纽。

1 2 3 4 5 7 6 8 9

向右查找找到8,停止。

1 2 3 4 5 7 6 8 9

向左查找开始。

1 2 3 4 5 7 6 8 9

找到了6,向左搜索停止,搜索坐标重合,不需要任何操作。

1 2 3 4 5 6 7 8 9

现在对左分区进行排序(只有元素6,不作任何操作)。

对右分区进行排序(只有元素8,不作任何操作)。

对元素9至8排序(不作任何操作)

1 2 3 4 5 6 7 8 9

最后,整个数组排序完成。

Posted in Algorithms | Tagged , | Leave a comment

观察者模式

Winform开发中经常会用到观察者模式,主要可以统一通知已向主体注册的观察者。譬如当值的改变时,所有的观察者都可以收到这个信息。

使用接口实现观察者模式:

   1     public interface IObserver

    2     {

    3         void Notify(string msg);

    4     }

    5 

    6     public class ObservableObject

    7     {

    8         private Hashtable _hashTable;

    9         public ObservableObject()

   10         {

   11             _hashTable = new Hashtable();

   12         }

   13 

   14         public void Register(IObserver observer)

   15         {

   16             if (!_hashTable.Contains(observer))

   17                 _hashTable.Add(observer, observer);

   18         }

   19 

   20         public void UnRegister(IObserver observer)

   21         {

   22             if (_hashTable.Contains(observer))

   23                 _hashTable.Remove(observer);

   24         }

   25 

   26         public void NotifyAll(string msg)

   27         {

   28             foreach (IObserver o in _hashTable.Keys)

   29             {

   30                 o.Notify(msg);

   31             }

   32         }

   33     }

   34 

   35     public class TestObj1 : IObserver

   36     {

   37         public void Notify(string msg)

   38         {

   39             Console.WriteLine("Obj1:" + msg);

   40         }

   41     }

   42 

   43     public class TestObj2 : IObserver

   44     {

   45         public void Notify(string msg)

   46         {

   47             Console.WriteLine("Obj2:" + msg);

   48         }

   49     }

   50 

   51     class Program

   52     {

   53         static void Main(string[] args)

   54         {

   55             ObservableObject observerObj = new ObservableObject();

   56             IObserver obj1 = new TestObj1();

   57             IObserver obj2 = new TestObj2();

   58 

   59             observerObj.Register(obj1);

   60             observerObj.Register(obj2);

   61 

   62             observerObj.NotifyAll("abcd");

   63         }

       64     }

 

使用委托和事件实现观察者模式:


    1     public class ObserverEventDemo

    2     {

    3         public delegate void ObserverEventHandler(object sender, EventArgs e);

    4         public event ObserverEventHandler ObserverChanged;

    5 

    6         public void ObserverOnChange(EventArgs e)

    7         {

    8             if (ObserverChanged != null)

    9                 ObserverChanged(this, e);

   10         }

   11     }

   12 

   13 

   14     class Program

   15     {

   16         static void Main(string[] args)

   17         {

   18             ObserverEventDemo demo = new ObserverEventDemo();

   19             demo.ObserverChanged += demo_ObserverChanged;

   20         }

   21 

   22         static void demo_ObserverChanged(object sender, EventArgs e)

   23         {

   24             throw new NotImplementedException();

   25         }

   26     }

Posted in Design Pattern | Tagged | Leave a comment

防止Sharepoint日志文件增长过快

MOSS 2007对于Office Server 2007 或者 WSS 3.0, 产生的日志文件体积都非常惊人,默认情况下,日志文件存在于C:\Program Files\Common Files\Microsoft Shared\web server extensions\12\LOGS,

而且部分日志文件的大小达到G级以上,光选择这些文件进行删除后,很快就会重新产生同样大小的文件出来。其实,大部分的信息我们并不需要,我们可以在SharePoint管理中心设置日志产生的内容,不需要的信息就不用写进日志了(甚至完全禁用日志)。

详细的步骤如下图:

Administrative Tools ->SharePoint 3.0 Central Administration->

Operations->Diagnostic Logging

找到Event Throttling,如果需要禁用,则可以如下图设置。

不过对于生产机,我们还是有必要相关日志的,不过只记录错误的信息即可。

如果觉得日志文件数太多,可以将Number of log files设少一些。同时,我们可以将日志文件的路径设去其他盘,以免C盘空间太少降低服务器速度。

Posted in MOSS/Sharepoint | Tagged , | Leave a comment

在.NET平台上的分布式缓存方案

.NET FrameworkMicrosoft "Velocity"

概述(MSDN):

"Velocity"是可提供构建具有扩展性和高性能的分布式应用缓存平台。程序可以存储任何在CLR里序列化的对象而不必担心对象存储在哪。可扩展性是指可以很简单的增加更多的电脑去满足实际需要。而且它可以允许数据的副本存储在集群里,以保护数据免受失败。而且"Velocity"还包含SESSION Provider,因此在ASP.NET使用SESSION时可以直接存放在缓存而不必写在数据库。

主要特点:

  • 通过简单的API可以对CLR序列化的对象进行缓存和访问。

  • 支持企业规模:数十到数百台电脑。

  • 可以配置成一种服务,在网络上或者在嵌入的程序上进行访问。

  • 支持常用的缓存配置。

  • 可以通过增加新的节点进行动态扩展。

  • 可配置多份拷贝已提高可用性。

  • 自动负载平衡

  • 集成一体化管理和监测工具,例如事件跟踪(ETW), 系统中心等。

  • 可以和ASP.NET紧密集成,缓存SESSION数据而不需将这些数据写入到数据库,进一步提高性能。

  • 延续CTP1时的缓存搁置功能,我们必须显式去指定哪些对象需要移除,这样"Velocity"自动同步时便不会去理这些对象。

  • 支持多种语言(例如PHP,C#,C++

现在的最新版本是CTP(2),CTP(3)将会在20093月的Mix09进行发布。安装时机子上需要预先安装好.NET Framework 3.5 and PowerShell 1.0

相关资源:

1. Microsoft Project Code Named "Velocity" Community Technology Preview 2 (CTP2)

2. MSDN Home

3. Team Blog

4. Samples

5. Forums 

Posted in .NET | Tagged , | Leave a comment

出差在北京

Beijing 2008 Olympic刚决定从Blogbus搬家过来,主要原因有两个,一是yo2基于WordPress,另一个原因是因为这里的主题很吸引,主题包里还看到我朋友iLemoned制作的主题。不过发觉这个网站不是太稳定,响应时间比较长(一般来说点击一个链接等了7秒都还没有反应,有很多人都会关闭该页面)。希望这个能够改善。

下面是我这个月在出差照的,发觉北京的天气比广州好很多,鼻炎也有一段时间没有发作了。

鸟<u style=莫道不消魂巢" width="328" height="240">

Posted in Travel | Tagged , | Leave a comment