2008年10月7日星期二

Microsoft Interview question

有7克、2克砝码各一个,天平一只,如何只用这些物品三次将140克的盐分成50、90克各一份?
Answer
a. 140 = 69+71 (2g on the 69 side)
b. 71 = 31 + 40 (2g and 7g on the 31 side), 40+69 = 109
c. 109 = 50+59 (2g and 7g on the 50 side), 59+31 = 90
如果你有无穷多的水,一个3公升的提捅,一个5公升的提捅,两只提捅形状上下都不均匀,问你如何才能准确称出4公升的水?
3先装满,倒在5里,再把3装满,倒进5里。把5里的水倒掉,把3里剩下的水倒进5里,再把3装满,倒进5里,ok!

2008年10月6日星期一

C#设计模式(7)-Singleton Pattern

一、 单例(Singleton)模式

单例模式的特点:

  • 单例类只能有一个实例。
  • 单例类必须自己创建自己的唯一实例。
  • 单例类必须给所有其它对象提供这一实例。

单例模式应用:

  • 每台计算机可以有若干个打印机,但只能有一个Printer Spooler,避免两个打印作业同时输出到打印机。
  • 一个具有自动编号主键的表可以有多个用户同时使用,但数据库中只能有一个地方分配下一个主键编号。否则会出现主键重复。


二、 Singleton模式的结构:

Singleton模式包含的角色只有一个,就是Singleton。Singleton拥有一个私有构造函数,确保用户无法通过new直接实例 它。除此之外,该模式中包含一个静态私有成员变量instance与静态公有方法Instance()。Instance方法负责检验并实例化自己,然后 存储在静态成员变量中,以确保只有一个实例被创建。(关于线程问题以及C#所特有的Singleton将在后面详细论述)。


三、 程序举例:

该程序演示了Singleton的结构,本身不具有任何实际价值。

// Singleton pattern -- Structural example
using System;

// "Singleton"
class Singleton
{
// Fields
private static Singleton instance;

// Constructor
protected Singleton() {}

// Methods
public static Singleton Instance()
{
// Uses "Lazy initialization"
if( instance == null )
instance
= new Singleton();

return instance;
}

}


///
/// Client test
///

public class Client
{
public static void Main()
{
// Constructor is protected -- cannot use new
Singleton s1 = Singleton.Instance();
Singleton s2
= Singleton.Instance();

if( s1 == s2 )
Console.WriteLine(
"The same instance" );
}

}



四、 在什么情形下使用单例模式:

使用Singleton模式有一个必要条件:在一个系统要求一个类只有一个实例时才应当使用单例模式。反过来,如果一个类可以有几个实例共存,就不要使用单例模式。

注意:

不要使用单例模式存取全局变量。这违背了单例模式的用意,最好放到对应类的静态成员中。

不要将数据库连接做成单例,因为一个系统可能会与数据库有多个连接,并且在有连接池的情况下,应当尽可能及时释放连接。Singleton模式由于使用静态成员存储类实例,所以可能会造成资源无法及时释放,带来问题。


五、 Singleton模式在实际系统中的实现

下面这段Singleton代码演示了负载均衡对象。在负载均衡模型中,有多台服务器可提供服务,任务分配器随机挑选一台服务器提供服务,以确保任务均衡(实际情况比这个复杂的多)。这里,任务分配实例只能有一个,负责挑选服务器并分配任务。

// Singleton pattern -- Real World example

using System;
using System.Collections;
using System.Threading;

// "Singleton"
class LoadBalancer
{
// Fields
private static LoadBalancer balancer;
private ArrayList servers = new ArrayList();
private Random random = new Random();

// Constructors (protected)
protected LoadBalancer()
{
// List of available servers
servers.Add( "ServerI" );
servers.Add(
"ServerII" );
servers.Add(
"ServerIII" );
servers.Add(
"ServerIV" );
servers.Add(
"ServerV" );
}


// Methods
public static LoadBalancer GetLoadBalancer()
{
// Support multithreaded applications through
// "Double checked locking" pattern which avoids
// locking every time the method is invoked
if( balancer == null )
{
// Only one thread can obtain a mutex
Mutex mutex = new Mutex();
mutex.WaitOne();

if( balancer == null )
balancer
= new LoadBalancer();

mutex.Close();
}

return balancer;
}


// Properties
public string Server
{
get
{
// Simple, but effective random load balancer
int r = random.Next( servers.Count );
return servers[ r ].ToString();
}

}

}


///
/// SingletonApp test
///

///

public class SingletonApp
{
public static void Main( string[] args )
{
LoadBalancer b1
= LoadBalancer.GetLoadBalancer();
LoadBalancer b2
= LoadBalancer.GetLoadBalancer();
LoadBalancer b3
= LoadBalancer.GetLoadBalancer();
LoadBalancer b4
= LoadBalancer.GetLoadBalancer();

// Same instance?
if( (b1 == b2) && (b2 == b3) && (b3 == b4) )
Console.WriteLine(
"Same instance" );

// Do the load balancing
Console.WriteLine( b1.Server );
Console.WriteLine( b2.Server );
Console.WriteLine( b3.Server );
Console.WriteLine( b4.Server );
}

}



六、 C#中的Singleton模式

C#的独特语言特性决定了C#拥有实现Singleton模式的独特方法。这里不再赘述原因,给出几个结果:

方法一:

下面是利用.NET Framework平台优势实现Singleton模式的代码:

sealed class Singleton
{
private Singleton();
public static readonly Singleton Instance=new Singleton();
}

这使得代码减少了许多,同时也解决了线程问题带来的性能上损失。那么它又是怎样工作的呢?

注意到,Singleton类被声明为sealed,以此保证它自己不会被继承,其次没有了Instance的方法,将原来_instance成员 变量变成public readonly,并在声明时被初始化。通过这些改变,我们确实得到了Singleton的模式,原因是在JIT的处理过程中,如果类中的static属 性被任何方法使用时,.NET Framework将对这个属性进行初始化,于是在初始化Instance属性的同时Singleton类实例得以创建和装载。而私有的构造函数和 readonly(只读)保证了Singleton不会被再次实例化,这正是Singleton设计模式的意图。
(摘自:http://www.cnblogs.com/huqingyu/archive/2004/07/09/22721.aspx

不过这也带来了一些问题,比如无法继承,实例在程序一运行就被初始化,无法实现延迟初始化等。

详细情况可以参考微软MSDN文章:《Exploring the Singleton Design Pattern》

方法二:

既然方法一存在问题,我们还有其它办法。

public sealed class Singleton
{
Singleton()
{
}


public static Singleton GetInstance()
{
return Nested.instance;
}


class Nested
{
// Explicit static constructor to tell C# compiler
// not to mark type as beforefieldinit
static Nested()
{
}


internal static readonly Singleton instance = new Singleton();
}

}

这实现了延迟初始化,并具有很多优势,当然也存在一些缺点。详细内容请访问:《Implementing the Singleton Pattern in C#》。文章包含五种Singleton实现,就模式、线程、效率、延迟初始化等很多方面进行了详细论述。


参考文献:
阎宏,《Java与模式》,电子工业出版社
[美]James W. Cooper,《C#设计模式》,电子工业出版社
[美]Alan Shalloway James R. Trott,《Design Patterns Explained》,中国电力出版社
[美]Robert C. Martin,《敏捷软件开发-原则、模式与实践》,清华大学出版社
[美]Don Box, Chris Sells,《.NET本质论 第1卷:公共语言运行库》,中国电力出版社