99久久免费国产精品特黄,色88久久久久高潮综合影院,久久亚洲欧美日本精品

設計模式之strategy

一、概述
Strategy（策略）模式又稱Policy模式，用于定義一系列的算法，把它們一個個封裝起來，并且使它們可相互替換。這里的算法并非狹義的數據結構或算法理論中所討論的KMP、shell sort等算法，而是指應用程序設計中不同的處理邏輯，前面所說的狹義的算法只是其中的一部分。Strategy模式使得算法與算法的使用者相分離，減少了二者間的耦合度，使得算法可獨立于使用它的客戶而變化；同時，由于設計粒度的減小，程序的復用性也得到了進一步提高，分離出來的算法可以更好地適應復用的需要。

二、結構
Strategy模式的結構如下圖所示：

從結構上看，Strategy模式與State模式有幾分相似，但二者所討論的Context（情景）具有顯著的差異：
State模式在于將其狀態信息分離出來保存到一個獨立的對象中，以便狀態信息的獲取或狀態的轉換；Strategy模式在于將可能的算法分離出來，根據需要進行適當的選擇。此外，二者的區別還在于，Strategy模式中各個Strategy（算法、策略）往往用于解決相同的問題，即只是解決同一問題的不同“策略”、“途徑”，而且，一次只能有一個Strategy為上次應用提供服務；而State模式中的各個State本身往往具有一定的差異，但他們之間存在明顯的相互轉換的關系，而且這種轉換往往會在程序運行過程中經常性地發生，同時存在一個以上State也是可能的。

區別參考：二者的應用場合不同。狀態模式用于處理對象有不同狀態（狀態機）的場合，策略模式用于隨不同外部環境采取不同行為的場合。在狀態模式中，狀態的變遷是由對象的內部條件決定，外界只需關心其接口，不必關心其狀態對象的創建和轉化；而策略模式里，采取何種策略由外部條件決定。所以，有人說“狀態模式是完全封裝且自修改的策略模式”。至于Bridge，在結構上與前兩者都不一樣了。要說相似之處，就是三者都有具有對外接口統一的類，展現出多態性而已。

三、應用
當存在以下情況時可考慮使用Strategy模式：
1.許多相關的類僅僅是行為有異。“策略”提供了一種用多個行為中的一個行為來配置一個類的方法。
2.需要使用一個算法的不同變體。例如，你可能會定義一些反映不同的空間/時間權衡的算法，當這些變體實現為一個算法的類層次時，可以使用策略模式。
3.算法使用客戶不應該知道的數據?？墒褂貌呗阅Ｊ揭员苊獗┞稄碗s的、與算法相關的數據結構。
4.一個類定義了多種行為，并且這些行為在這個類的操作中以多個條件語句的形式出現。將相關的條件分支移入它們各自的Strategy類中以代替這些條件語句。
更具體的應用實例包括：
1.以不同的格式保存文件；
2.以不同的方式對文件進行壓縮或其他處理；
3.以不同的方式繪制/處理相同的圖形數據；
等等。

四、舉例
下面是一個應用Strategy模式對vector進行排序的例子，為了簡化問題，其中的排序Strategy實際上調用的是STL的排序算法：sort和stable_sort。

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <time.h>
  5 using namespace std;
  6
  7 template <typename T>
  8 class SortStrategy    // Strategy
  9 {
10 public:
11     virtual void Sort( vector<T>& v_t ) = 0;
12 };
13
14 template <typename T>
15 class SortQuick : public SortStrategy<T>    // ConcreateStrategy1
16 {
17 public:
18     void Sort( vector<T>& v_t ) { std::sort( v_t.begin(), v_t.end() ); }
19 };
20
21 template <typename T>
22 class SortStable : public SortStrategy<T>    // ConcreateStrategy1
23 {
24 public:
25     void Sort( vector<T>& v_t ) { std::stable_sort(v_t.begin(), v_t.end()); }
26 };
27
28 template <typename T>
29 class Context {        // Context, who or whose client takes charge of which strategy will be selected
30 public:
31     Context() { m_pStrategy = NULL; }
32     virtual ~Context() { if (m_pStrategy != NULL) delete m_pStrategy; }
33
34     void SetStrategy(SortStrategy<T>* pStrategy);    // select a strategy
35
36     void ReadVector( vector<T>& v_t);
37     bool SortVector();
38     void OutputVector();
39 private:
40     vector<T> m_vt;
41     SortStrategy<T>*  m_pStrategy;    // a pointer to current strategy
42 };
43
44 template <typename T>
45 void Context<T>::SetStrategy( SortStrategy<T>* pStrategy )
46 {
47     if ( NULL != m_pStrategy )
48         delete m_pStrategy;
49
50     m_pStrategy = pStrategy;
51 }
52
53 template <typename T>
54 void Context<T>::ReadVector( vector<T>& v_t)
55 {
56     m_vt.clear();
57     copy( v_t.begin(), v_t.end(), back_inserter( m_vt ) );
58 }
59
60 template <typename T>
61 bool Context<T>::SortVector()
62 {
63     if ( NULL == m_pStrategy )
64         return false;
65
66     m_pStrategy->Sort( m_vt );
67
68     return true;
69 }
70
71 template <typename T>
72 void Context<T>::OutputVector()
73 {
74     copy( m_vt.begin(), m_vt.end(), ostream_iterator<T>( cout, " " ) );
75 }
76
77 // a functor to generate random int
78 struct RandGen
79 {
80     RandGen(int ratio) { m_ratio = ratio; }
81     int operator() () { return rand() % m_ratio + 1; }
82 private:
83     int m_ratio;
84 };
85
86 int main()
87 {
88     const int NUM = 9;
89     vector< int > vi;
90     time_t t;
91     srand( (unsigned) time(&t) );
92
93     // create a vector with random information
94     vi.reserve(NUM + 1);
95     generate_n(back_inserter(vi), NUM, RandGen(NUM));
96
97     Context< int >  con;
98     con.SetStrategy( new SortQuick<int>() );
99     con.ReadVector( vi );
100     con.OutputVector();
101
102     cout << endl;
103
104     con.SortVector();
105     con.OutputVector();
106
107     return 0;
108 }

本文轉自：http://blog.csdn.net/haiyan0106/article/details/1651797

posted @ 2012-07-17 08:11 王海光閱讀(576) | 評論 (0) | 編輯收藏

C++設計模式-Iterator

一、概述
Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內部表示?；蛘哌@樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。
由于Iterator模式的以上特性：與聚合對象耦合，在一定程度上限制了它的廣泛運用，一般僅用于底層聚合支持類，如STL的list、vector、stack等容器類及ostream_iterator等擴展iterator。
根據STL中的分類，iterator包括：
Input Iterator：只能單步向前迭代元素，不允許修改由該類迭代器引用的元素。
Output Iterator：該類迭代器和Input Iterator極其相似，也只能單步向前迭代元素，不同的是該類迭代器對元素只有寫的權力。
Forward Iterator：該類迭代器可以在一個正確的區間中進行讀寫操作，它擁有Input Iterator的所有特性，和Output Iterator的部分特性，以及單步向前迭代元素的能力。
Bidirectional Iterator：該類迭代器是在Forward Iterator的基礎上提供了單步向后迭代元素的能力。
Random Access Iterator：該類迭代器能完成上面所有迭代器的工作，它自己獨有的特性就是可以像指針那樣進行算術計算，而不是僅僅只有單步向前或向后迭代。
這五類迭代器的從屬關系，如下圖所示，其中箭頭A→B表示，A是B的強化類型，這也說明了如果一個算法要求B，那么A也可以應用于其中。

圖1、五種迭代器之間的關系
vector 和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的 iterators是 ForwardIterator，關于STL中iterator的更多信息。
二、結構
Iterator模式的UML結構如下圖所示：

三、應用
Iterator模式有三個重要的作用：
1）它支持以不同的方式遍歷一個聚合復雜的聚合可用多種方式進行遍歷，如二叉樹的遍歷，可以采用前序、中序或后序遍歷。迭代器模式使得改變遍歷算法變得很容易: 僅需用一個不同的迭代器的實例代替原先的實例即可，你也可以自己定義迭代器的子類以支持新的遍歷，或者可以在遍歷中增加一些邏輯，如有條件的遍歷等。
2）迭代器簡化了聚合的接口有了迭代器的遍歷接口，聚合本身就不再需要類似的遍歷接口了，這樣就簡化了聚合的接口。
3）在同一個聚合上可以有多個遍歷每個迭代器保持它自己的遍歷狀態，因此你可以同時進行多個遍歷。
4）此外，Iterator模式可以為遍歷不同的聚合結構（需擁有相同的基類）提供一個統一的接口，即支持多態迭代。
簡單說來，迭代器模式也是Delegate原則的一個應用，它將對集合進行遍歷的功能封裝成獨立的Iterator，不但簡化了集合的接口，也使得修改、增加遍歷方式變得簡單。從這一點講，該模式與Bridge模式、Strategy模式有一定的相似性，但Iterator模式所討論的問題與集合密切相關，造成在Iterator在實現上具有一定的特殊性，具體將在示例部分進行討論。

四、優缺點
正如前面所說，與集合密切相關，限制了 Iterator模式的廣泛使用，就個人而言，我不大認同將Iterator作為模式提出的觀點，但它又確實符合模式“經常出現的特定問題的解決方案”的特質，以至于我又不得不承認它是個模式。在一般的底層集合支持類中，我們往往不愿“避輕就重”將集合設計成集合 + Iterator 的形式，而是將遍歷的功能直接交由集合完成，以免犯了“過度設計”的詬病，但是，如果我們的集合類確實需要支持多種遍歷方式（僅此一點仍不一定需要考慮 Iterator模式，直接交由集合完成往往更方便），或者，為了與系統提供或使用的其它機制，如STL算法，保持一致時，Iterator模式才值得考慮。

五、舉例
可以考慮使用兩種方式來實現Iterator模式：內嵌類或者友元類。通常迭代類需訪問集合類中的內部數據結構，為此，可在集合類中設置迭代類為friend class，但這不利于添加新的迭代類，因為需要修改集合類，添加friend class語句。也可以在抽象迭代類中定義protected型的存取集合類內部數據的函數，這樣迭代子類就可以訪問集合類數據了，這種方式比較容易添加新的迭代方式，但這種方式也存在明顯的缺點：這些函數只能用于特定聚合類，并且，不可避免造成代碼更加復雜。

STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator類的形式，雖然STL的集合類的iterator分散在各個集合類中，但由于各Iterator類具有相同的基類，保持了相同的對外的接口（包括一些traits及tags等，感興趣者請認真閱讀參考1、2），從而使得它們看起來仍然像一個整體，同時也使得應用algorithm成為可能。我們如果要擴展STL的iterator，也需要注意這一點，否則，我們擴展的iterator將可能無法應用于各algorithm。

以下是一個遍歷二叉樹的Iterator的例子，為了方便支持多種遍歷方式，并便于遍歷方式的擴展，其中還使用了Strategy模式（見筆記21）：
（注：1、雖然下面這個示例是本系列所有示例中花費我時間最多的一個，但我不得不承認，它非常不完善，感興趣的朋友，可以考慮參考下面的參考材料將其補充完善，或提出寶貴改進意見。2、我本想考慮將其封裝成與STL風格一致的形式，使得我們遍歷二叉樹必須通過Iterator來進行，但由于二叉樹在結構上較線性存儲結構復雜，使訪問必須通過Iterator來進行，但這不可避免使得BinaryTree的訪問變得異常麻煩，在具體應用中還需要認真考慮。3、以下只提供了Inorder<中序>遍歷iterator的實現。）

1 #include <assert.h>
2
3 #include <iostream>
4 #include <xutility>
5 #include <iterator>
6 #include <algorithm>
7 using namespace std;
8
9 template <typename T>
10 class BinaryTree;
11 template <typename T>
12 class Iterator;
13
14 template <typename T>
15 class BinaryTreeNode
16 {
17 public:
18      typedef BinaryTreeNode<T> NODE;
19      typedef BinaryTreeNode<T>* NODE_PTR;
20
21      BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }
22      BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)
23          :data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)
24      {
25          if (leftChild)
26              leftChild->setParent(this);
27          if (rightChild)
28              rightChild->setParent(this);
29      }
30
31      T getData(void) const { return data; }
32      NODE_PTR getLeft(void) const { return leftChild; }
33      NODE_PTR getRight(void) const { return rightChild; }
34      NODE_PTR getParent(void) const { return parent; }
35      void SetData(const T& data) { this->data = item; }
36      void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); }
37      void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); }
38      void setParent(NODE_PTR ptr) { parent = ptr; }
39 private:
40      T data;
41      NODE_PTR leftChild;
42      NODE_PTR rightChild;
43      NODE_PTR parent;   // pointer to parent node, needed by iterator
44
45      friend class BinaryTree<T>;
46 };

本文轉自：http://www.cnblogs.com/berry/archive/2009/10/12/1581554.html

posted @ 2012-07-16 08:11 王海光閱讀(758) | 評論 (0) | 編輯收藏

singleton模式

singleton模式是Gof提出的23中模式之一，也稱為單例模式，那么簡單說一下，什么叫單例模式呢？
通常我們創建類的對象是使用new Object()，然后就調用該對象里面的方法，那么當我們多次使用new Object()的話，會對系統資源造成一種浪費，當然.net內部已經有垃圾回收機制可以處理這種浪費。當然我們并不會再程序里面多次使用new Object()，但是，作為一個類的設計者，我們需要負什么責任，除了讓別的模塊可以調用使用之外，我們的設計還需要一種規范，這也是OO里面的規范，singleton模式在這里派上了用場。

      singleton模式的意圖：確保一個類只能擁有一個實例，并保證邏輯的正確性以及良好的效率，并提供一個該實例的全局訪問點。
      singleton模式類型：單線程singleton，多線程singleton
      singleton思路：要讓使用者只能使用一個實例的話，那么必須繞過常規的公有缺省構造器

singleton代碼：

1 public class singleton
2 {
3     private static singleton instance;
4     private singleton() { }
5     public static singleton Instance
6     {
7         get
8         {
9             if (instance == null)
10             {
11                 instance = new singleton();
12             }
13             return instance;
14         }
15     }
16 }
17

      第4行：利用私有構造函數繞開系統自帶的缺省公有構造函數，這樣就使類的外部不可以直接使用new實例化對象
      第5行：提供一個靜態的公有屬性，供類外部調用
      第9行：在這里可能存在BUG，當有兩個線程同時操作公有屬性時，常規的話應該返回兩個一樣的實例，但是假如當第一個實例還未來得及創建時，第二個線程又訪問了它，顯然也會執行　　　　          new singleton（）這個語句，那么這兩個對象的引用就不一樣了，可以使用object.ReferenceEquals測試一下對象的引用是否一樣。因此，給大家提供多線程方案，請看下面代碼

1 public class singletons
2 {
3     private static volatile singletons instances = null;
4     private static object lockHelper = new object();
5     private singletons() { }
6     public static singletons Instance
7     {
8         get
9         {
10             if(instances==null)
11             {
12                 lock (lockHelper)
13                 {
14                     if(instances==null )
15                     {
16                         instances = new singletons();
17                     }
18                 }
19             }
20             return instances;
21         }
22     }
23 }

      顯然看起來與單線程singleton差不多，多了volatile 修飾符，還有一個Object對象，接下來跟大家解釋使用這些其中的緣由
      volatile 修飾符
      假如我定義兩個變量和兩個屬性

1  int a;
2  volatile int b;
3  public int GetFirst
4  {
5      get { return a; }
6  }
7  public int GetSecond
8  {
9      get { return b; }
10  }

GetFirst會得到當前線程中a的值，而多個線程就會有多個a的變量拷貝，而且這些拷貝之間可以互不相同，換句話說，另一個線程可能改變了它線程內的a值，而這個值和當前線程中的a值不相同，那么就造成線程沖突了。
那么再來看看b，因為volatile 修飾的變量不允許有不同于“主”內存區域的變量拷貝，換句話說，一個變量經volatile 修飾后在所有線程中都是同步的；任何線程改變了它的值，所以其他線程立即獲取到了相同的值，當然加了volatile 修飾的變量存儲時會比一般變量消耗的資源要多一點。

Object對象鎖
對象鎖可以保證Lock里面的代碼只能同時讓一個線程執行，所以確保了一個對象只存在一個實例。

同樣的需求可以有不同的方法實現，以下是另外一種實現singleton模式的代碼，代碼更簡單，不夠有缺陷，請看

1 public class singletonss
2  {
3      public static readonly singletonss Instance = new singletonss();
4      private singletonss() { }
5  }

首先定義一個靜態的只讀實例，當然也需要私有構造器繞過缺省構造器，這樣子也可以保證多線程里也只誕生一個對象實例，因為.Net類型初始化機制保證只有一個線程執行了靜態構造器。當然這么少的代碼也可以實現singleton，但是靜態構造器不支持參數，也不能重構，因為在.Net機制里面只允許一個類擁有一個靜態構造器而且是私有的，外部不能調用只能供系統調用，所以我們不能使用參數。

本文轉自：http://www.cnblogs.com/magicchaiy/archive/2010/12/02/1894826.html
其他鏈接：http://www.shnenglu.com/dyj057/archive/2005/09/20/346.html

posted @ 2012-07-13 08:14 王海光閱讀(454) | 評論 (0) | 編輯收藏

C++設計模式之一工廠模式（簡單工廠、工廠和抽象工廠）

摘要: 今天開始這個系列之前，心里有些恐慌，畢竟園子里的高手關于設計模式的經典文章很多很多，特別是大俠李會軍、呂震宇老師的文章更是堪稱經典。他們的文筆如行云流水，例子活潑生動，講解深入淺出。好在他們都是用C#描述，也沒有提供必要的源碼下載，所以我這里用C++實現。首先我想聲明的是我的文筆絕對不如他們的好，例子也沒有他們的形象，不過我打算把C+... 閱讀全文

posted @ 2012-07-12 08:44 王海光閱讀(575) | 評論 (0) | 編輯收藏

Active Object 模式

Active Object 模式是Command模式的一種，是實現多線程控制的一項古老技術 .

在《敏捷軟件開發》這本書中描述的算法如下：
1、構造一個命令。（實現Command模式的一個命令）
2、將該命令放入Active Object Engine（也就是放入一個隊列，LinkedList）
3、從該Engine取出一個命令，執行，若該命令沒有執行過，設為執行過，然后將自己加入隊列尾部，若執行過，判斷該命令執行需要的事件發生沒有，未發生，再將自己加入隊列尾部。事件發生了，將需要執行的命令加入隊列尾部。

Active Object模式不屬于《Design Pattern》23模式。實際上，她是一種特殊的Command Queue。其特殊之處在于：

1. 隊列的擁有者會順序地執行隊列中所有Command對象的Execute方法。（這個其實不算特殊）

2.Command對象在自己的Execute方法結束前，可以把一個新的command對象（實際上常常是這個command對象自己）再加到隊列的尾部。

看出來了嗎，這個隊列有可能不會終止的，他可以一直執行下去。這個可以作為一個應用或者服務的主模塊了，想像一下她可以作多少事情吧。

《ASP》指出這個模式可以用來在一個線程中處理多任務的問題?。。?^_^ 太cool了。

如何處理呢？你可以把每個command對象看作是一個任務。他在Execute函數中，處理自己的任務，在任務告一段落時，記錄自己的狀態，然后把自己插入到隊列的尾部，結束Execute方法。當隊列輪完一周后，又會再次執行這個command對象的Execute方法。 ^_^ 很cool吧。

那么這種方法和多線程的方法相比有什么有缺點呢？

最大的優點是，所有的command都在同一個線程中，因此切換時，不需要進入內核模式！！超高效?。?！而且，可以有很多很多的command，數量上遠遠超過多線程的數量。

缺點嘛，是這種方法需要用戶自己來實現調度，另外這其實是一種非剝奪模式的多任務，如果command處理不好，就會連累其它所有的command，因此實際上比多線程要更復雜。（嘿嘿，程序員能夠怕麻煩嗎？）

還有一點，Active Object運行于單線程，也就是說，她不能享受多處理器或多處理器核心帶來的性能上的改善。

其實，這最后一點是非常致命的一點。也就是說，在當前intel的超線程CPU機器上，如果系統的負擔并不重的時候。Active Object的效率有可能比多線程更低。

Anyway，這是一個非常有趣的模式。只是一般的程序員可能沒有機會用到。

本文轉自：http://www.shnenglu.com/tx7do/archive/2010/02/28/108617.aspx

posted @ 2012-07-11 08:14 王海光閱讀(817) | 評論 (0) | 編輯收藏

Command 模式

摘要: 引言提起Command模式，我想沒有什么比遙控器的例子更能說明問題了，本文將通過它來一步步實現GOF的Command模式。我們先看下這個遙控器程序的需求：假如我們需要為家里的電器設計一個遠程遙控器，通過這個控制器，我們可以控制電器(諸如燈、風扇、空調等)的開關。我們的控制器上有一系列的按鈕，分別對應家中的某個電器，當我們在遙控器上按下“On”時，電器打開；當我們按下... 閱讀全文

posted @ 2012-07-10 13:40 王海光閱讀(524) | 評論 (0) | 編輯收藏

VC中怎么執行一個應用程序，并取得應用程序的返回值

假設需要執行的程序如下：

int main(int argc, char* argv[])
{
return argc;
}

執行它，并取得其返回值，我寫了一個函數如下：

DWORD         WinExecAndWait32(    LPCTSTR lpszAppPath,   // 執行程序的路徑
                                LPCTSTR lpParameters,  // 參數
                                LPCTSTR lpszDirectory, // 執行環境目錄
                                DWORD dwMilliseconds)  // 最大等待時間, 超過這個時間強行終止
{
    SHELLEXECUTEINFO ShExecInfo = {0};
    ShExecInfo.cbSize    = sizeof(SHELLEXECUTEINFO);
    ShExecInfo.fMask    = SEE_MASK_NOCLOSEPROCESS;
    ShExecInfo.hwnd        = NULL;
    ShExecInfo.lpVerb    = NULL;
    ShExecInfo.lpFile    = lpszAppPath;
    ShExecInfo.lpParameters = lpParameters;
    ShExecInfo.lpDirectory    = lpszDirectory;
    ShExecInfo.nShow    = SW_HIDE;
    ShExecInfo.hInstApp = NULL;
    ShellExecuteEx(&ShExecInfo);

    // 指定時間沒結束
    if (WaitForSingleObject(ShExecInfo.hProcess, dwMilliseconds) == WAIT_TIMEOUT)
    {    // 強行殺死進程
        TerminateProcess(ShExecInfo.hProcess, 0);
        return 0;    //強行終止
    }

    DWORD dwExitCode;
    BOOL bOK = GetExitCodeProcess(ShExecInfo.hProcess, &dwExitCode);
    ASSERT(bOK);

    return dwExitCode;
}

我上傳了兩個工程，希望對大家有所幫助！

下載

本文轉自：http://www.shnenglu.com/humanchao/archive/2007/12/28/39815.html

posted @ 2012-07-10 08:28 王海光閱讀(775) | 評論 (0) | 編輯收藏

完成端口

完成端口聽起來好像很神秘和復雜，其實并沒有想象的那么難。這方面的文章在論壇上能找到的我差不多都看過，寫得好點的就是CSDN.NET上看到的一組系列文章，不過我認為它只是簡單的翻譯了一下Network Programming for Microsoft Windows 2nd 中的相關內容，附上的代碼好像不是原書中的，可能是另一本外文書里的。我看了以后，覺得還不如看原版的更容易理解。所以在我的開始部分，我主要帶領初學者理解一下完成端口的有關內容，是我開發的經驗，其他的請參考原書的相關內容。
采用完成端口的好處是，操作系統的內部重疊機制可以保證大量的網絡請求都被服務器處理，而不是像WSAAsyncSelect 和WSAEventSelect的那樣對并發的網絡請求有限制，這一點從上一章的測試表格中可以清楚的看出。
完成端口就像一種消息通知的機制，我們創建一個線程來不斷讀取完成端口狀態，接收到相應的完成通知后，就進行相應的處理。其實感覺就像 WSAAsyncSelect一樣，不過還是有一些的不同。比如我們想接收消息，WSAAsyncSelect會在消息到來的時候直接通知Windows 消息循環，然后就可以調用WSARecv來接收消息了；而完成端口則首先調用一個WSARecv表示程序需要接收消息（這時可能還沒有任何消息到來），但是只有當消息來的時候WSARecv才算完成，用戶就可以處理消息了，然后再調用一個WSARecv表示等待下一個消息，如此不停循環，我想這就是完成端口的最大特點吧。
Per-handle Data 和 Per-I/O Operation Data 是兩個比較重要的概念，Per-handle Data用來把客戶端數據和對應的完成通知關聯起來，這樣每次我們處理完成通知的時候，就能知道它是哪個客戶端的消息，并且可以根據客戶端的信息作出相應的反應，我想也可以理解為Per-Client handle Data吧。Per-I/O Operation Data則不同，它記錄了每次I/O通知的信息，比如接收消息時我們就可以從中讀出消息的內容，也就是和I/O操作有關的信息都記錄在里面了。當你親手實現完成端口的時候就可以理解他們的不同和用途了。
CreateIoCompletionPort函數中有個參數NumberOfConcurrentThreads，完成端口編程里有個概念Worker Threads。這里比較容易引起混亂，NumberOfConcurrentThreads需要設置多少，又需要創建多少個Worker Threads才算合適？NumberOfConcurrentThreads的數目和CPU數量一樣最好，因為少了就沒法利用多CPU的優勢，而多了則會因為線程切換造成性能下降。Worker Threads的數量是不是也要一樣多呢，當然不是，它的數量取決于應用程序的需要。舉例來說，我們在Worker Threads里進行消息處理，如果這個過程中有可能會造成線程阻塞，那如果我們只有一個Worker Thread，我們就不能很快響應其他客戶端的請求了，而只有當這個阻塞操作完成了后才能繼續處理下一個完成消息。但是如果我們還有其他的Worker Thread，我們就能繼續處理其他客戶端的請求，所以到底需要多少的Worker Thread，需要根據應用程序來定，而不是可以事先估算出來的。如果工作者線程里沒有阻塞操作，對于某些情況來說，一個工作者線程就可以滿足需要了。

===========================================================

“完成端口”模型是迄今為止最為復雜的—種I/O模型。然而。假若—個應用程序同時需要管理為數眾多的套接字，那么采用這種模型。往往可以達到最佳的系統性能,然而不幸的是,該模型只適用于以下操作系統(微軟的)：Windows NT和Windows 2000操作系統。因其設計的復雜性，只有在你的應用程序需要同時管理數百乃至上千個套接字的時候、而且希望隨著系統內安裝的CPU數量的增多、應用程序的性能也可以線性提升，才應考慮采用“完成端口”模型。要記住的一個基本準則是，假如要為Windows NT或windows 2000開發高性能的服務器應用,同時希望為大量套接字I/O請求提供服務(Web服務器便是這方面的典型例子)，那么I/O完成端口模型便是最佳選擇.

從本質上說,完成端口模型要求我們創建一個Win32完成端口對象,通過指定數量的線程對重疊I/O請求進行管理。以便為已經完成的重疊I/O請求提供服務。要注意的是。所謂“完成端口”,實際是Win32、Windows NT以及windows 2000采用的一種I/O構造機制,除套接字句柄之外,實際上還可接受其他東西。然而，本節只打算講述如何使用套接字句柄，來發揮完成端口模型的巨大威力。使用這種模型之前，首先要創建一個I/O完成端口對象,用它面向任意數量的套接字句柄。管理多個I/O請求。要做到這—點,需要調用CreateIoCompletionPort函數。該函數定義如下：

HANDLE CreateIoCompletionPort(

HANDLE FileHandle,

HANDLE ExistingCompletionPort,

DWORD CompletionKey,

DWORD NumberOfConcurrentThreads

);

在我們深入探討其中的各個參數之前,首先要注意意該函數實際用于兩個明顯有別的目的：

■用于創建—個完成端口對象。

■將一個句柄同完成端口關聯到一起。

最開始創建—個完成端口的時候，唯一感興趣的參數便是NumberOfConcurrentThreads 并發線程的數量)；前面三個參數都會被忽略。NumberOfConcurrentThreads 參數的特殊之處在于．它定義了在一個完成端口上，同時允許執行的線程數量。理想情況下我們希望每個處理器各自負責—個線程的運行，為完成端口提供服務,避免過于頻繁的線程“場景”切換。若將該參數設為0,說明系統內安裝了多少個處理器,便允許同時運行多少個線程！可用下述代碼創建一個I/O完成端口：

CompetionPort=CreateIoCompletionPort(INVALID_HANDLE_VALUE,NULL,0,0)

該語加的作用是返問一個句柄．在為完成端口分配了—個套接字句柄后，用來對那個端

口進行標定(引用)。

1．工作者線程與完成端口

成功創建一個完成端口后，便可開始將套接字句柄與對象關聯到一起。但在關聯套接字之前、首先必須創建—個或多個“工作者線程”，以便在I/O請求投遞給完成端口對象后。為完成端口提供服務。在這個時候，大家或許會覺得奇怪、到底應創建多少個線程。以便為完成端口提供服務呢?這實際正是完成端口模型顯得頗為“復雜”的—個方面, 因為服務I/O請求所需的數量取決于應用程序的總體設計情況。在此要記住的—個重點在于，在我們調用CreateIoComletionPort時指定的并發線程數量,與打算創建的工作者線程數量相比,它們代表的并非同—件事情。早些時候,我們曾建議大家用CreateIoCompletionPort函數為每個處理器都指定一個線程(處理器的數量有多少,便指定多少線程)以避免由于頻繁的線程“場景”交換活動，從而影響系統的整體性能。CreateIoCompletionPort函數的NumberofConcurrentThreads參數明確指示系統：在一個完成端口上，一次只允許n個工作者線程運行。假如在完成端門上創建的工作者線程數量超出n個．那么在同一時刻，最多只允許n個線程運行。但實際上，在—段較短的時間內,系統有可能超過這個值。但很快便會把它減少至事先在CreateIoCompletionPort函數中設定的值。那么,為何實際創建的工作者線程數最有時要比CreateIoCompletionPort函數設定的多—些呢?這樣做有必要嗎?如先前所述。這主要取決于應用程序的總體設計情況，假設我們的工作者線程調用了一個函數，比如Sleep()或者WaitForSingleobject()，但卻進入了暫停(鎖定或掛起)狀態、那么允許另—個線程代替它的位置。換行之，我們希望隨時都能執行盡可能多的線程；當然，最大的線程數量是事先在CreateIoCompletonPort調用里設定好的。這樣—來。假如事先預料到自己的線程有可能暫時處于停頓狀態,那么最好能夠創建比CreateIoCompletionPort的NumberofConcurrentThreads參數的值多的線程．以便到時候充分發揮系統的潛力。—旦在完成端口上擁有足夠多的工作者線程來為I/O請求提供服務,便可著手將套接字句柄同完成端口關聯到一起。這要求我們在—個現有的完成端口上調用CreateIoCompletionPort函數，同時為前三個參數: FileHandle,ExistingCompletionPort和CompletionKey——提供套接字的信息。其中,FileHandle參數指定—個要同完成端口關聯在—一起的套接字句柄。

ExistingCompletionPort參數指定的是一個現有的完成端口。CompletionKey(完成鍵)參數則指定要與某個特定套接字句柄關聯在—起的“單句柄數據”,在這個參數中，應用程序可保存與—個套接字對應的任意類型的信息。之所以把它叫作“單句柄數據”,是由于它只對應著與那個套接字句柄關聯在—起的數據?？蓪⑵渥鳛橹赶蛞粋€數據結構的指針、來保存套接字句柄；在那個結構中，同時包含了套接字的句柄,以及與那個套接字有關的其他信息。就象本章稍后還會講述的那樣,為完成端口提供服務的線程例程可通過這個參數。取得與其套字句柄有關的信息。

根據我們到目前為止學到的東西。首先來構建—個基本的應用程序框架。

程序清單8—9向人家闡述了如何使用完成端口模型。來開發—個回應(或“反射’)服務器應用。

在這個程序中。我們基本上按下述步驟行事：

1) 創建一個完成端口。第四個參數保持為0，指定在完成端口上，每個處理器一次只允許執行一個工作者線程。

2) 判斷系統內到底安裝了多少個處理器。

3) 創建工作者線程,根據步驟2)得到的處理器信息，在完成端口上，為已完成的I/O請求提供服務。在這個簡單的例子中,我們為每個處理器都只創建—個工作者線程。這是出于事先已經預計到,到時候不會有任何線程進入“掛起”狀態,造成由于線程數量的不足，而使處理器空閑的局面(沒有足夠的線程可供執行)。調用CreateThread函數時,必須同時提供—個工作者線程，由線程在創建好執行。本節稍后還會詳細討論線程的職責。

4) 準備好—個監聽套接字。在端口5150上監聽進入的連接請求。

5) 使用accept函數,接受進入的連接請求。

6) 創建—個數據結構，用于容納“單句柄數據”。同時在結構中存入接受的套接字句柄。

7) 調用CreateIoCompletionPort將自accept返回的新套接字句柄向完成端口關聯到一起,通過完成鍵(CompletionKey)參數，將但句柄數據結構傳遞給CreateIoCompletionPort。

8) 開始在已接受的連接上進行I/O操作。在此，我們希望通過重疊I/O機制,在新建的套接字上投遞一個或多個異步WSARecv或WSASend請求。這些I/O請求完成后,一個工作者線程會為I/O請求提供服務,同時繼續處理未來的I/O請求,稍后便會在步驟3)指定的工作者例程中。體驗到這一點。

9) 重復步驟5)—8)。直到服務器終止。

程序清單8。9 完成端口的建立

StartWinsock()

//步驟一,創建一個完成端口

CompletionPort=CreateIoCompletionPort(INVALI_HANDLE_VALUE,NULL,0,0);

//步驟二判斷有多少個處理器

GetSystemInfo(&SystemInfo);

//步驟三：根據處理器的數量創建工作線程,本例當中，工作線程的數目和處理器數目是相同的

for(i = 0; i < SystemInfo.dwNumberOfProcessers,i++){

HANDLE ThreadHandle;

//創建工作者線程，并把完成端口作為參數傳給線程

ThreadHandle=CreateThread(NULL,0，

ServerWorkerThread，CompletionPort,

0， &ThreadID);

//關閉線程句柄(僅僅關閉句柄，并非關閉線程本身)

CloseHandle(ThreadHandle);

}

//步驟四:創建監聽套接字

Listen=WSASocket(AF_INET,S0CK_STREAM,0,NULL,

WSA_FLAG_OVERLAPPED);

InternetAddr.sin_famlly=AF_INET;

InternetAddr.sin_addr.s_addr = htonl(INADDR_ANY);

InternetAddr.sln_port = htons(5150);

bind(Listen,(PSOCKADDR)&InternetAddr，sizeof(InternetAddr));

//準備監聽套接字

listen(Listen，5);

while(TRUE){

//步驟五，接入Socket,并和完成端口關聯

Accept = WSAAccept(Listen,NULL,NULL,NULL,0);

//步驟六創建一個perhandle結構，并和端口關聯

PerHandleData=(LPPER_HANDLE_DATA)GlobalAlloc(GPTR，sizeof(PER_HANDLE_DATA));

printf("Socket number %d connected\n",Accept);

PerHandleData->Socket=Accept;

//步驟七,接入套接字和完成端口關聯

CreateIoCompletionPort((HANDLE)Accept,

CompletionPort,(DWORD)PerHandleData,0);

//步驟八

//開始進行I/O操作，用重疊I/O發送一些WSASend()和WSARecv()

WSARecv(．．．)

本文轉自：http://blog.sina.com.cn/s/blog_458f4a2c0100nq44.html

posted @ 2012-07-04 17:02 王海光閱讀(528) | 評論 (0) | 編輯收藏

（轉）優秀博客推薦：各種數據結構與算法知識入門經典（不斷更新)

基本算法
貪心算法：貪心算法作者：獨酌逸醉
貪心算法精講作者：3522021224
遞歸和分治：遞歸與分治策略作者：zhoudaxia

圖論
圖的遍歷（DFS和BFS）：圖的遍歷作者：jefferent
最小生成樹（Prim算法和Kruskal算法）：貪心算法--最小生成樹作者：獨酌逸醉
Dijkstra算法：最短路徑之Dijkstra算法詳細講解作者：綠巖
最短路徑算法—Dijkstra(迪杰斯特拉)算法分析與實現(C/C++) 作者：tankywoo
Bellman-Ford算法：最短路徑算法—Bellman-Ford(貝爾曼-福特)算法分析與實現(C/C++) 作者：tankywoo
Floyd-Warshall算法：最短路徑算法—Floyd(弗洛伊德)算法分析與實現(C/C++) 作者：tankywoo
Johnson算法：Johnson 算法作者：huliang82
A*算法：A*算法詳解作者：愚人有節
拓撲排序：拓撲排序作者：

midgard

如何去理解拓撲排序算法作者：張善友
關鍵路徑：關鍵路徑作者：navorse
歐拉路：歐拉路問題作者：MaiK
差分約束：差分約束系統作者：fuliang
二分圖最大匹配：二分圖匹配總結作者：北極天南星
二分圖匹配算法總結作者：z7m8v6
網絡流：網絡流基礎作者：chhaj523

數據結構
并查集：并查集--學習詳解作者：yx_th000
哈希表：哈希表作者：獵人杰
二分查找：查找（二）：二分查找作者：xiaosuo
哈夫曼樹：哈夫曼樹作者：angle平衡二叉樹：平衡二叉樹（解惑）作者：Never
樹狀數組：樹狀數組總結作者：熊貓yingcai
線段樹：線段樹總結作者：星星
歸并排序求逆序數：利用歸并排序求逆序數作者：kahn
動態規劃（DP）
簡單動態規劃：動態規劃作者：brokencode
背包問題：《背包九講》

數學
遺傳算法：遺傳算法入門作者：heaad
容斥原理：容斥原理（翻譯）作者：vici
母函數：母函數入門小結作者：zhangxiang0125
秦九韶算法：秦九韶算法作者：simonezhlx
高斯消元法：
歐幾里得定理（GCD）：
擴展歐幾里得定理：
中國剩余定理：
概率問題：

計算幾何
幾何公式：
離散化：什么是離散化？作者：matrix67
掃描線算法：
叉積和點積：
凸包：

本文轉自：http://www.shnenglu.com/cxiaojia/archive/2011/11/16/rumen.html

posted @ 2012-06-30 16:21 王海光閱讀(478) | 評論 (0) | 編輯收藏

最短路徑算法—Floyd(弗洛伊德)算法分析與實現(C/C++)

Floyd-Warshall算法，簡稱Floyd算法，用于求解任意兩點間的最短距離，時間復雜度為O(n^3)。

使用條件&范圍
通?？梢栽谌魏螆D中使用，包括有向圖、帶負權邊的圖。

Floyd-Warshall 算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。

1.注意單獨一條邊的路徑也不一定是最佳路徑。
2.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。
對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
3.不可思議的是，只要按排適當，就能得到結果。
偽代碼:

1 // dist(i,j) 為從節點i到節點j的最短距離
2 For i←1 to n do
3    For j←1 to n do
4       dist(i,j) = weight(i,j)
5
6 For k←1 to n do // k為“媒介節點”
7    For i←1 to n do
8       For j←1 to n do
9          if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路徑？
10             dist(i,j) = dist(i,k) + dist(k,j)

我們平時所見的Floyd算法的一般形式如下：

1 void Floyd(){
2      int i,j,k;
3      for(k=1;k<=n;k++)
4          for(i=1;i<=n;i++)
5              for(j=1;j<=n;j++)
6                  if(dist[i][k]+dist[k][j]<dist[i][j])
7                      dist[i][j]=dist[i][k]+dist[k][j];
8 }

注意下第6行這個地方，如果dist[i][k]或者dist[k][j]不存在，程序中用一個很大的數代替。最好寫成if(dist[i] [k]!=INF && dist[k][j]!=INF && dist[i][k]+dist[k][j]

Floyd算法的實現以及輸出最短路徑和最短路徑長度，具體過程請看【動畫演示Floyd算法】。

代碼說明幾點：

1、A[][]數組初始化為各頂點間的原本距離，最后存儲各頂點間的最短距離。

2、path[][]數組保存最短路徑，與當前迭代的次數有關。初始化都為-1，表示沒有中間頂點。在求A[i][j]過程中，path[i][j]存放從頂點vi到頂點vj的中間頂點編號不大于k的最短路徑上前一個結點的編號。在算法結束時，由二維數組path的值回溯，可以得到從頂點vi到頂點vj的最短路徑。

初始化A[][]數組為如下，即有向圖的鄰接矩陣。

完整的實現代碼如下：

  1 #include <iostream>
  2 #include <string>
  3 #include <stdio.h>
  4 using namespace std;
  5 #define MaxVertexNum 100
  6 #define INF 32767
  7 typedef struct
  8 {
  9     char vertex[MaxVertexNum];
10     int edges[MaxVertexNum][MaxVertexNum];
11     int n,e;
12 }MGraph;
13
14 void CreateMGraph(MGraph &G)
15 {
16     int i,j,k,p;
17     cout<<"請輸入頂點數和邊數:";
18     cin>>G.n>>G.e;
19     cout<<"請輸入頂點元素:";
20     for (i=0;i<G.n;i++)
21     {
22         cin>>G.vertex[i];
23     }
24     for (i=0;i<G.n;i++)
25     {
26         for (j=0;j<G.n;j++)
27         {
28             G.edges[i][j]=INF;
29             if (i==j)
30             {
31                 G.edges[i][j]=0;
32             }
33         }
34     }
35     for (k=0;k<G.e;k++)
36     {
37         cout<<"請輸入第"<<k+1<<"條弧頭弧尾序號和相應的權值:";
38         cin>>i>>j>>p;
39         G.edges[i][j]=p;
40     }
41 }
42 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n);
43
44 void Floyd(MGraph G)
45 {
46     int A[MaxVertexNum][MaxVertexNum],path[MaxVertexNum][MaxVertexNum];
47     int i,j,k;
48     for (i=0;i<G.n;i++)
49     {
50         for (j=0;j<G.n;j++)
51         {
52             A[i][j]=G.edges[i][j];
53             path[i][j]=-1;
54         }
55     }
56     for (k=0;k<G.n;k++)
57     {
58         for (i=0;i<G.n;i++)
59         {
60             for (j=0;j<G.n;j++)
61             {
62                 if (A[i][j]>A[i][k]+A[k][j])
63                 {
64                     A[i][j]=A[i][k]+A[k][j];
65                     path[i][j]=k;
66                 }
67             }
68         }
69     }
70     Dispath(A,path,G.n);
71 }
72
73 void Ppath(int path[][MaxVertexNum],int i,int j)
74 {
75     int k;
76     k=path[i][j];
77     if (k==-1)
78     {
79         return;
80     }
81     Ppath(path,i,k);
82     printf("%d,",k);
83     Ppath(path,k,j);
84 }
85
86 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n)
87 {
88     int i,j;
89     for (i=0;i<n;i++)
90     {
91         for (j=0;j<n;j++)
92         {
93             if (A[i][j]==INF)
94             {
95                 if (i!=j)
96                 {
97                     printf("從%d到%d沒有路徑\n",i,j);
98                 }
99             }
100             else
101             {
102                 printf("  從%d到%d=>路徑長度:%d路徑:",i,j,A[i][j]);
103                 printf("%d,",i);
104                 Ppath(path,i,j);
105                 printf("%d\n",j);
106             }
107         }
108     }
109 }
110
111 int main()
112 {
113     freopen("input2.txt", "r", stdin);
114     MGraph G;
115     CreateMGraph(G);
116     Floyd(G);
117     return 0;
118 }

測試結果如下：

本文轉自：http://www.wutianqi.com/?p=1903