Monday, February 28, 2011

Recursive Search With Yield in C#

 

 

Requirement :

Have the following Table

 

partno    designnumber    code1    code2    code3    module
11111    x    x    x    x    NM63-1
(NU12)050201    NULL    NULL    NULL    NULL    NM63-1
22222    NU12    05    02    01    NULL
(NK12)060302    NU12    05    02    01    NULL
33333    NK12    06    03    02    NULL
4444    NK12    06    03    02    NULL
(MJ12)070403    NK12    06    03    02    NULL
5555    MJ12    07    04    03    NULL

 

(NU12)050201 is referred partno which need to find

22222    NU12    05    02    01    NULL

 

(NK12)060302    NU12    05    02    01    NULL
->

33333    NK12    06    03    02    NULL
4444    NK12    06    03    02    NULL
(MJ12)070403    NK12    06    03    02    NULL

->

5555    MJ12    07    04    03    NULL

 

Final Result:

11111    x    x    x    x    NM63-1
22222    NU12    05    02    01    NULL
33333    NK12    06    03    02    NULL
4444    NK12    06    03    02    NULL
5555    MJ12    07    04    03    NULL

 

Solution 1  : not using Yield

……………..

//define a global variable

public List<DataRow> final = new List<DataRow>();

……………..

public void GetRecursivePartListNotUsingYield(DataRow dr)
   {
       string partnonew = dr["partno"].ToString();
           if (partnonew.Length == 12) // validation function , will use different
           {               DataTable dt2 = DatabaseFactory.CreateDatabase("ETAConnectionString").ExecuteDataSet(CommandType.Text, "select * from [0228test] where designnumber like '" + partnonew.Substring(1, 4) + "' and code1='" + partnonew.Substring(6, 2) + "' and code2='" + partnonew.Substring(8, 2) + "' and code3='" + partnonew.Substring(10, 2) + "'").Tables[0];


               foreach (DataRow dr2 in dt2.Rows)
               {
                   GetRecursivePartListNotUsingYield(dr2);
               }

           }
           else
           {

               final.Add(dr);
           }

   }

 

………………………….

 

test :

 

DataTable dt = DatabaseFactory.CreateDatabase("ETAConnectionString").ExecuteDataSet(CommandType.Text, "select * from [0228test] where module='NM63-1'").Tables[0];

      foreach (DataRow dr in dt.rows

      {
          GetRecursivePartListNotUsingYield(dr);

      }

// Check final list

foreach(DataRow dr in final)

{

 

 

}

 

Solution 2:

 

public IEnumerable<DataRow> GetRecursivePartListUsingYield(DataTable dt)
  {
      foreach (DataRow dr in dt.Rows)
      {

          string partnonew = dr["partno"].ToString();
          if (partnonew.Length != 12)
          {
              yield return dr;
          }
          else
          {
              DataTable dt2 = DatabaseFactory.CreateDatabase("ETAConnectionString").ExecuteDataSet(CommandType.Text, "select * from [0228test] where designnumber like '" + partnonew.Substring(1, 4) + "' and code1='" + partnonew.Substring(6, 2) + "' and code2='" + partnonew.Substring(8, 2) + "' and code3='" + partnonew.Substring(10, 2) + "'").Tables[0];
              if (dt2.Rows.Count > 0)
              {
                  foreach (DataRow dr2 in GetRecursivePartListUsingYield(dt2))
                  {
                      yield return dr2;

                  }

              }

          }
      }

  }

Test:

 

DataTable dt = DatabaseFactory.CreateDatabase("ETAConnectionString").ExecuteDataSet(CommandType.Text, "select * from [0228test] where module='NM63-1'").Tables[0];

         foreach (DataRow dr in GetRecursivePartListUsingYield(dt))
         {
             Debug.WriteLine(dr["partno"].ToString());
         }

Tuesday, February 22, 2011

Scalable Web Application

.NET下实现 web负载均衡 + 数据库主从 + 缓存 + 分布式存储 + 队列
具体的实现方案或Demo下载 介绍下具体学习的内容。

Wednesday, February 16, 2011

SP 2010 Tip

(1)

Get Error when trying to create /manager web application in Central Administration

 

Error

Object reference not set to an instance of an object.

 

 

Workout:

 

Central Admin -> Security -> Configure managed accounts

Register new managed account with current user.(win-fss5d5nj561/administrator)

 

select “win-fss5d5nj561/administrator” for  “Farm Account”

Tuesday, February 15, 2011

SharePoint Structure Overview

image

 

image

Friday, February 11, 2011

Deploy IIS Hosted WCF Service To Server

--publish to local folder
-- add four files

System.Data.Entity.dll
System.Data.Entity.Design.dll

Thursday, February 10, 2011

WCF Performance Tuning(ZT)

 

From http://www.aspnet101.com/2010/08/wcf-performance-best-practices/

 

WCF was introduced to overcome the constraints of previous distributed technologies like ASP.NET Web Services, WSE, .NET Enterprise Services and .NET Remoting and to provide a performance boost in addition. For an introduction to WCF please read my first WCF article - WCF Tutorial .

Performance is a central goal for web or app site, expecially since Google now includes site responsiveness a factor in their ranking algorithm.  For ASP.NET optimization tips, please see  my article titled 50 Tips to Boost ASP.NET Performance.  In this article I will  discuss   WCF performance tuning techniques.

Use DataContractSerializer:

Serialization  is the process of converting an object instance into a portable and transferable format.   Xml Serialization  is popular for its interoperability and binary Serialization  is more useful for transferring objects between two .NET  applications.

System.Runtime.Serialization.DataContractSerializer is   designed for WCF but can also be used for general serialization. The DataContractSerializer has some benefits over XmlSerializer:

  1. XmlSerializer can serialize only properties but DataContractSerializer can serialize fields in addition to  properties.
  2. XmlSerializer can serialize only public members but DataContractSerializer can serialize not only public members but also private and protected members.
  3. In performance terms,  DataContractSerializer is approximately 10% faster than XmlSerializer.

Select proper WCF binding:

System-provided WCF bindings are used to specify the transport protocols, encoding, and security details required for clients and services to communicate with each other. The below are the available  system-provided WCF bindings:

1.BasicHttpBinding:

A binding   suitable for communication with WS-Basic Profile conformant Web Services such as ASMX-based services. This binding uses HTTP as the transport and Text/XML for message encoding.

2. WSHttpBinding:

A secure and interoperable binding   suitable for non-duplex service contracts.

3. WSDualHttpBinding:

A secure and interoperable binding  suitable for duplex service contracts or communication through SOAP intermediaries.

4. WSFederationHttpBinding:

A secure and interoperable binding that supports the WS-Federation protocol, enabling organizations that are in a federation to efficiently authenticate and authorize users.

5. NetTcpBinding:

A secure and optimized binding suitable for cross-machine communication between WCF applications

6. NetNamedPipeBinding:

A  reliable, secure, optimized binding suitable for on-machine communication between WCF applications.

7. NetMsmqBinding:

A queued binding suitable for cross-machine communication between WCF applications.

8. NetPeerTcpBinding :

A binding which enables secure, multi-machine communication.

9. MsmqIntegrationBinding :

A binding that is suitable for cross-machine communication between a WCF application and existing MSMQ applications.

In this context Juval Lowry has presented a nice decision making diagram:

WCF Performance Tuning

It should be noted that WCF also allows us to define our own custom bindings.

Use Tracing:

Tracing can track all the events or specified events in a  program. By default it is off. For debugging purposes we have to make enable it explicitly either through code or using a config file setting which is preferable. If  debugging is not required we should disable tracing. For more details reader can read my article titled “Tracing in WCF”.

Close Proxy:

The proxy represents a service contract. It provides the same operations as service’s contract along with some additional methods for managing the proxy life cycle and the connection to the service. It is a recommended best practice to always close the proxy when the client is finished using it. When we close the proxy, the session with the service is terminated and the connection is closed as well and thus can serve to process new requests in better way.

It should be noted that calling a proxy in a using statement (see the below code snippet) is actually not the optimal  or safest method.

using (ServiceProxy proxyClient = new ServiceProxy())
{
proxyClient.SomeFunction();
}
The above code will be translated to something as follows:
ServiceProxy proxyClient = new ServiceProxy();
try
{
proxyClient.SomeFunction();
}
finally
{
if (proxyClient != null)
((IDisposable)proxyClient).Dispose();
}


The problem with this method is that proxyClient.Dispose() will throw an exception when the proxy is in a faulted state .So to close the proxy even under faulted state the below is the suggested approach:



ServiceProxy proxyClient = new ServiceProxy();
try
{
proxyClient.SomeFunction();
proxyClient.Close();
}
finally
{
if (proxyClient.State != System.ServiceModel.CommunicationState.Closed)
{
proxyClient.Abort();
}
}


Throttling:



Throttling is a way of mitigating potential DoS (denial of service) attacks. Using ServiceThrottlingBehavior we can set smooth loading and resource allocations on the server. In WCF, there are three service-level throttles that are controlled by ServiceThrottlingBehavior.



1. MaxConcurrentCalls: The maxConcurrentCalls attribute lets us specify the maximum number of simultaneous calls for a service. When the maximum number of simultaneous calls has been met and a new call is placed, the call is queued and will be processed when the number of simultaneous calls is below the specified maximum number. The default value is 16.



2. MaxconcurrentSessions: The maxconcurrentSessions attribute specifies the maximum     number of connections



to a single service. The channels below the specified limit will be active/open. It should be noted that this throttle is effectively disabled for non-sessionful channels (such as default BasicHttpBinding).The default value is 10.



3. MaxConcurrentInstance: The maxConcurrentInstance attribute specify the maximum number of simultaneous service instances. While receiving new instance request the maximum number has already been reached, the request is queued up and will be completed when the number of instances is below the specified maximum. The default value is total of the two attributes maxConcurrentSessions and maxConcurrentCalls.



From general feedback it is has been noted that the default settings for the above mentioned three attributes are very conservative and are insufficient in real production scenarios and thus developers need to increase those default settings.



Hence Microsoft has increased the default settings in WCF4.0 as follows:



1. MaxConcurrentSessions: default is 100 * ProcessorCount



2. MaxConcurrentCalls: default is 16 * ProcessorCount



3. MaxConcurrentInstances: default is the total of MaxConcurrentSessions and MaxConcurrentCalls



Now we have a new parameter which is the multiplier “ProcessorCount” for the settings. The main reason for this is that we do not need to change the settings in deployment from a low end system to a multiple processor based system. The value for MaxConcurrentSessions is also increased from 10 to 100.



Quotas:



There are three types of quotas in WCF transports:



1. Timeouts. Timeouts are used for the mitigation of DOS attacks which rely on tying up resources for an extended period of time.



2. Memory allocation limits: Memory allocation limits prevent a single connection from exhausting the system resources and denying service to other connections.



3. Collection size limits: Collection size limits restrict the consumption of resources which indirectly allocate memory or are in limited supply.



As per MSDN the transport quotas available for the standard WCF transports: HTTP(S), TCP/IP, and named pipes are



as follows:



image 


 xxx


Other quotas of the ReaderQuotas property that can be used to restrict message complexity to provide protection from denial of service (DOS) attacks, these are:




  1. MaxDepth: The maximum nested no depth per read. The default is 32.


  2. MaxStringContentLength: The maximum string length allowed by the reader.  The default is 8192.


  3. MaxArrayLength: The maximum allowed array length of data being received by WCF from a client. The default is 16384.


  4. MaxBytesPerRead: The maximum allowed bytes returned per read.  The default is 4096.


  5. MaxNameTableCharCount: The maximum characters in a table name. The default is 16384.



The maxConnections property setting of NetTcpBinding on the client indicates the maximum number of connections to be pooled/cached for subsequent reuse.  On the server, this setting is responsible for controlling the maximum number of connections.  The default is 10. This helps performance in cases where we are creating and disposing client channels.



maxItemsInObjectGraph: The maximum number of items which can be serialized or desterilized in an object is 65,536.But this can be increased to  Int32.MaxValue (2147483647) and can be configured through behaviors in configuration file as follows: Once this behavior is set, the WCF service and client can send and receive not only large



objects, but also highly complex ones. The  below is the sample configuration settings:



<behaviors>


<serviceBehaviors>


<behavior name="largeObjectGraph">


<dataContractSerializer maxItemsInObjectGraph=”100000″/>”


</behavior>


</serviceBehaviors>


<endpointBehaviors>


<behavior name=”largeObjectGraph”>


<dataContractSerializer maxItemsInObjectGraph=”100000″/>”


</behavior>


</endpointBehaviors>


</behaviors>



The value needs to be set in both the client and the server.



Reliable Session:



Reliable sessions provide low-latency (Latency is the time requires for the message to reach the destination from the source) reliable message transfers. When using a reliable session, we should set a reasonable value for InactivityTimeout which is added to the binding configuration to keep the connection alive. At the same time the ReceiveTimeout setting of the binding is also need to be set with a reasonable value. If either of these is triggered, then the connection is killed. The default for both of these timeouts is 10 minutes. Following is the sample configuration settings:



<reliableSession enabled="true" ordered="true" inactivityTimeout="00:10:00"/>


Ideal Hosting Environment:



It is best to use IIS or WAS for robust, highly scalable services and self-hosting is ideal for a Windows Service to have full control and light-weight hosting environment. For more details user can read Optimal Hosting Environment



Chunking Channel:



In case of large amounts of data chunking, channels is a very handy solution. For more user can visit the link:Chunking channel



Use Cache:



Use caching intensively (but wisely) to save unnecessary round trips specifically for static types of data.



Asynchronous WCF HTTP Module/Handler:



For optimal server scalability there is a new addition, namely asynchronous WCF HTTP Module/Handler for IIS7. For more details see: Asynchronous WCF HTTP Module/Handler



Conclusion:



So far we have seen a few best practices in our service based application using WCF. Last but not least, when getting timeout exceptions we should bump up the default conservative settings inthe  Bindings, Behaviors and Serializers but not blindly to int.MaxValue.



Unfortunately, there is no magic formula to use – it depends on the volume and structure of an application’s data .It is advisable to load data during testing and find out a reasonable setting trial and error.

WCF绑定类型选择(ZT)

From http://www.cnblogs.com/huyong/archive/2010/12/11/1903482.html

 

 

性能的要求也是在选择绑定方案时需要考虑的因素。通常情况下,在满足系统功能的前提下,建议挑选性能最佳的绑定。一般的,使用 IPC(即:netNamedPipeBinding)的绑定要优于使用TCP的绑定,而使用TCP(即:netTcpBinding)的绑定又优于使用 HTTP的绑定。使用针对WCF优化的绑定要优于参与非WCF系统交互的绑定。

 

 

image

 

 

image

Thursday, February 03, 2011

冒泡排序、插入排序、归并排序和基数排序 时间复杂度(ZT)

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/hkx1n/archive/2009/02/22/3922249.aspx

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

冒泡法: 
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:  复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。

直接插入排序:O(n*n)

选择排序:O(n*n)

快速排序:平均时间复杂度log2(n)*n,所有内部排序方法中最高好的,大多数情况下总是最好的。

归并排序:log2(n)*n

堆排序:log2(n)*n

希尔排序:算法的复杂度为n的1.2次幂

这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:

首先我们考虑最理想的情况
1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。
2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。
第一层递归,循环n次,第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大??呵呵,你完全不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。
如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢 于快速排序(因为要重组堆)。

这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些不是稳定的,做起来应该可以轻松搞定。

本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。

      首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。

     其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。

     回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

   (1)冒泡排序

        冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

(2)选择排序

      选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(3)插入排序
     插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

(4)快速排序
    快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序
    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

(6)基数排序
   基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

(7)希尔排序(shell)
    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

(8)堆排序
   我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法

1 快速排序(QuickSort)

快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。

(1) 如果不多于1个数据,直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。

2 归并排序(MergeSort)

归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。

3 堆排序(HeapSort)

堆排序适合于数据量非常大的场合(百万数据)。

堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。

堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

4 Shell排序(ShellSort)

Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

5 插入排序(InsertSort)

插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。

6 冒泡排序(BubbleSort)

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。

7 交换排序(ExchangeSort)和选择排序(SelectSort)

这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。

8 基数排序(RadixSort)

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。

9 总结

下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。

排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2)     O(n2) 稳定 O(1) n小时较好
交换     O(n2)     O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9),

R是基数(个十百)
Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

以下是一个基于模板的通用排序:
这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
    CMyData(int Index,char* strData);
    CMyData();
    virtual ~CMyData();

    int m_iIndex;
    int GetDataSize(){ return m_iDataSize; };
    const char* GetData(){ return m_strDatamember; };
    //这里重载了操作符:
    CMyData& operator =(CMyData &SrcData);
    bool operator <(CMyData& data );
    bool operator >(CMyData& data );

private:
    char* m_strDatamember;
    int m_iDataSize;
};
////////////////////////////////////////////////////////

MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}

CMyData::~CMyData()
{
    if(m_strDatamember != NULL)
      delete[] m_strDatamember;
    m_strDatamember = NULL;
}

CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
    m_iDataSize = strlen(strData);
    m_strDatamember = new char[m_iDataSize+1];
    strcpy(m_strDatamember,strData);
}

CMyData& CMyData::operator =(CMyData &SrcData)
{
    m_iIndex = SrcData.m_iIndex;
    m_iDataSize = SrcData.GetDataSize();
    m_strDatamember = new char[m_iDataSize+1];
    strcpy(m_strDatamember,SrcData.GetData());
    return *this;
}

bool CMyData::operator <(CMyData& data )
{
    return m_iIndex<data.m_iIndex;
}

bool CMyData::operator >(CMyData& data )
{
    return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"

template <class T>
void run(T* pData,int left,int right)
{
    int i,j;
    T middle,iTemp;
    i = left;
    j = right;
    //下面的比较都调用我们重载的操作符函数
    middle = pData[(left+right)/2]; //求中间值
    do{
      while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
        i++;     
      while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
        j--;
      if(i<=j)//找到了一对值
      {
        //交换
        iTemp = pData[i];
        pData[i] = pData[j];
        pData[j] = iTemp;
        i++;
        j--;
      }
    }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)

    //当左边部分有值(left<j),递归左半边
    if(left<j)
      run(pData,left,j);
    //当右边部分有值(right>i),递归右半边
    if(right>i)
      run(pData,i,right);
}

template <class T>
void QuickSort(T* pData,int Count)
{
    run(pData,0,Count-1);
}

void main()
{
    CMyData data[] = {
      CMyData(8,"xulion"),
      CMyData(7,"sanzoo"),
      CMyData(6,"wangjun"),
      CMyData(5,"VCKBASE"),
      CMyData(4,"jacky2000"),
      CMyData(3,"cwally"),
      CMyData(2,"VCUSER"),
      CMyData(1,"isdong")
    };
    QuickSort(data,8);
    for (int i=0;i<8;i++)
      cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
    cout<<"\n";
}

Wednesday, February 02, 2011

(ZT)Developing on SharePoint 2010 Intro Tutorial

 

 

 

Folks, this is a exciting news for SharePoint Geeks that the availability of Developing on SharePoint 2010 Tutorial can be access here.

image

You will find the following topics as the brief introduction on SharePoint 2010.

  • Getting Started Home Page
  • Module 1: Getting Started: Building Web Parts in SharePoint 2010
  • Module 2: What Developers Need to Know About SharePoint 2010
  • Module 3: Building Blocks for Web Part Development in SharePoint 2010
  • Module 4: Accessing SharePoint 2010 Data and Objects with Server-Side APIs
  • Module 5: Accessing SharePoint 2010 Data and Objects with Client-Side APIs
  • Module 6: Accessing External Data with Business Connectivity Services in SharePoint 2010
  • Module 7: Developing Business Processes with SharePoint 2010 Workflows
  • Module 8: Creating Silverlight User Interfaces for SharePoint 2010 Solutions
  • Module 9: Sandboxed Solutions for Web Parts in SharePoint 2010
  • Module 10: Creating Dialog Boxes and Ribbon Controls for SharePoint 2010

    Enjoy!