策略模式
Strategy，策略模式：定义一系列的算法，把他们一个个封装起来，并使他们可以互相替换，本模式使得算法可以独立于使用它们的客户。 应用场景：
http://www.cnblogs.com/zhili/p/StragetyPattern.html
http://www.cnblogs.com/PatrickLiu/p/8057654.html
抽象工厂(Abstract Factory)
Abstract Factory，抽象工厂：提供一个创建一系列相关或相互依赖对象的接口，而无须指定它们的具体类。 应用场景：一系列相互依赖的对象有不同的具体实现。提供一种“封装机制”来避免客户程序和这种“多系列具体对象创建工作”的紧耦合。
MySQL权限管理
2018年深度学习框架
1. OpenCV
https://github.com/opencv/opencv
OpenCV是迄今为止最古老也是最受欢迎的开源计算机视觉库，旨在为计算机视觉应用提供通用底层算法。
支持跨平台应用，支持Windows，Linux，Android和macOS。支持各种主流的开发语言，例如：Python，Java，C++等。OpenCV有一个Python Wrapper，支持GPU的CUDA模型。包含一些可以转换为TensorFlow模型的模型。最初由Intel开发，现在可以在开源BSD许可证下免费使用。
OpenCV的主要功能包括：
- 2D和3D图像工具包
- 人脸识别
- 手势识别
- 运动检测
- 人机交互
- 对象检测
- 图像分割和对象识别
2. Scikit-Image
https://github.com/scikit-image/scikit-image
Scikit-Image是公认的最方便的Python视觉库，它是Scikit-Learn的一个扩展库。是监督和无监督机器学习最常用的工具之一。可以用于将NumPy数组作为图像对象进行处理。
以下是使用Scikit-image进行硬币识别的例子。
1 | import skimage as ski image = ski.data.coins() # ... or any other NumPy array! edges = ski.filters.sobel(image) ski.io.imshow(edges) ski.io.show() |
3. Pillow (PIL Fork)
https://github.com/python-pillow/Pillow
Pillow是一个Python编写的图像处理库。它支持Windows、Mac OS X和Linux平台，可以在C和Python语言中使用Pillow库。主要用于阅读和保存不同格式的图像，Pillow还包括各种基本图像变换功能，例如：旋转、合并、缩放等。
4. TorchVision
https://pytorch.org/vision/stable/index.html
TorchVision是PyTorch库的一个扩展库，TorchVision拥有计算机视觉中最常见的图像转换功能，还包含计算机视觉神经网络的数据集和模型架构以及常见数据集。TorchVision旨在为方便使用PyTorch模型进行计算机视觉图像转换，而无需将图像转换为NumPy数组。TorchVision可以用于Python和C++语言开发环境。可以通过pip install将TorchVision与PyTorch库一起搭配使用。
以下是预训练分割模型的使用例子。
5. MMCV
https://github.com/open-mmlab/mmcv
MMCV是一个基于PyTorch的图像/视频处理和转换器。它支持Linux、Windows和macOS等系统，是计算机视觉研究人员最常用的包之一。支持Python和C++开发语音。
6.YOLO
https://github.com/ultralytics/ultralytics
YOLO是最快的计算机视觉工具之一，由Joseph雷德蒙和Ali Farhadi于2016年开发，专门用于实时图像对象检测。YOLO使用将神经网络，将图像划分为网格，然后同时预测每个网格，以提高识别效率。
目前YOLO已经发布V8。YOLOv8 是一款前沿、最先进（SOTA）的模型，基于先前 YOLO 版本的成功并引入了新的功能和改进，进一步提升了性能和灵活性。YOLOv8 的快速、准确且易于使用，使其成为各种对象检测与跟踪、实例分割、图像分类和姿态估计任务的绝佳选择。
7. TensorFlow
TensorFlow是由GoogleBrain团队开发并于2015年11月发布的AI框架，旨在促进构建AI模型的过程。它有一些扩展解决方案，如针对浏览器和Node.js的TensorFlow.js，以及针对终端设备的TensorFlow Lite。另外，TensorFlow还提供了一个更好的框架TensorFlow Hub。这是一个更易于使用的平台，可以使用TensorFlow Hub实现重复使用BERT和Faster R-CNN训练模型、查找可随时部署的模型、托管模型以供他人使用。
TensorFlow允许用户开发与计算机视觉相关的机器学习模型，例如：人脸识别、图像分类、目标检测等。与OpenCV一样，Tensorflow也支持各种语言，如Python、C、C++、Java或JavaScript。
8. Keras
Keras是一个基于Python的开源软件库，对初学者来说特别易用，它允许快速构建神经网络模型，是一个模块化的AI工具箱，计算机视觉工程师可以利用它来快速组装应用、训练模型。Keras的底层框架使用TensorFlow，并且拥有强大的社区支持，因此用户众多。可以使用Keras实现的内容例如：
- 图像分割和分类
- 手写识别
- 三维图像分类
- 语义图像聚类
9.MATLAB
https://ww2.mathworks.cn/products/matlab.html
MATLAB是Matrix Laboratory的缩写，但它是一个付费编程平台，适合用于如机器学习、深度学习、图像处理、视频信号处理等方面的应用，是一个受到工程师和科学家喜欢的编程平台。它配备了一个计算机视觉工具箱，包含许多算法能力，如：
- 视频目标检测与目标跟踪
- 物体识别
- 校准摄像机
- 处理三维视觉
10.NVIDIA CUDA-X
https://developer.nvidia.com/gpu-accelerated-libraries
CUDA是计算统一设备架构的首字母缩写，而NVIDIA CUDA-X是CUDA的更新版本。NVIDIA CUDA-X是一个GPU加速库和工具的集合，可以开始使用新的应用程序或GPA加速。它包含数学库、并行算法库、图像和视频库、通信库和深度学习库，可用于各种任务，例如：人脸识别、图像处理、3D图形渲染等。它兼容大多数操作系统，并且支持许多主流AI编程语言，如：C、C++、Python、Fortran、MATLAB等。
11.NVIDIA Performance Primitives
https://developer.nvidia.com/npp
CUDA（Compute Unified Device Architecture的缩写）是NVIDIA开发的并行计算平台和应用程序编程接口（API）模型。它允许开发人员使用GPU（图形处理单元）的强大功能来加快处理密集型应用程序的速度。
该工具包包含NVIDIA Performance Primitives（NPP）库，可为多个领域（包括计算机视觉）提供GPU加速的图像、视频处理和信号处理功能。此外，CUDA架构可用于各种开发任务，例如：人脸识别、图像处理、3D图形渲染等。它支持各种编程语言，包括C、C++、Python、Fortran或MATLAB，并且还与大多数操作系统兼容。
12.OpenVINO
OpenVINO是Open Visual Inference and Neural Network Optimization的缩写。它是一套非常全面的计算机视觉工具。它由英特尔开发，是一个可以免费使用的跨平台框架，具有多种视觉处理能力，包括：
- 对象检测
- 人脸识别
- 图像彩色化
- 运动识别
13.PyTorch
https://github.com/pytorch/pytorch
PyTorch是一个Python的开源机器学习框架，主要由Facebook的AI研究小组开发。在构建复杂体系结构时具有很大的灵活性。可以用于机器视觉方面开发图像评估模型、图像分割、图像分类等。
14.Caffe
https://caffe.berkeleyvision.org/
CAFFE是Convolutional Architecture for Fast Feature Embedding的缩写。是一个易于使用的开源深度学习和计算机视觉框架，由加州大学伯克利分校开发。它使用C++编写，支持多种开发语言，支持多种用于实现图像分类和图像分割的深度学习架构。Caffe可以用于视觉、语音和多媒体领域的应用，支持图像分割、分类等模型开发。
15.Detectron2
https://github.com/facebookresearch/detectron2
Detecrton 2是由Facebook AI Research（FAIR）开发的基于PyTorch的模对象检测库。Detectron 2是Detection的升级版；包括：Faster R-CNN、Mask R-CNN、RetinaNet、DensePose、Cascade R-CNN、Panoptic FPN和TensorMask等模型。Detecrton 2的功能包括：密集位姿预测、全景图像分割、联合分割、对象检测等。
16.SimpleCV
SimpleCV是一个开源免费的机器视觉框架。通这个框架，可以轻松访问OpenCV等几个高性能的计算机视觉库，而无需深入了解位深度、颜色空间、缓冲区管理或文件格式等复杂概念。
从TensorFlow 到 Caffe2：盘点深度学习框架 - allcloud - 博客园
Excerpt
机器之心报道 本文首先介绍GitHub中最受欢迎的开源深度学习框架排名，然后再对其进行系统地对比 下图总结了在GitHub中最受欢迎的开源深度学习框架排名，该排名是基于各大框架在GitHub里的收藏数，这个数据由MitchDeFelice在2017年5月初完成。 TensorFlow 地址：http
机器之心报道
本文首先介绍GitHub中最受欢迎的开源深度学习框架排名，然后再对其进行系统地对比
下图总结了在GitHub中最受欢迎的开源深度学习框架排名，该排名是基于各大框架在GitHub里的收藏数，这个数据由MitchDeFelice在2017年5月初完成。
TensorFlow
地址：https://www.tensorflow.org/
TensorFlow最开始是由谷歌一个称之为DistBeliefV2的库发展而来，它是一个公司内部的深度神经网络库，隶属于谷歌大脑项目。有一些人认为TensorFlow是由Theano彻底重构而来。
谷歌开源TensorFlow后，立即吸引了一大批开发爱好者。TensorFlow可以提供一系列的能力，例如图像识别、手写识别、语音识别、预测以及自然语言处理等。2015年11月9号，TensorFlow在Apache2.0协议下开源发布。
TensorFlow1.0版本已于2017年2月15日发布，这个版本是之前8个版本的优化改进版，其致力于解决Tensorflow之前遇到的一系列问题以及完善一些核心能力。TensorFlow获得成功的因素有：
TensorFlow提供了如下工具：
TensorBoard：对于网络模型和效果来说是一个设计优良的可视化工具。TensorFlowServing：可以保持相同的服务器架构和API，使得部署新算法和实验变得简单。TensorFlowServing提供了与TensorFlow模型开箱即用的整合，但同时还能很容易扩展到其它类型的模型和数据。
TensorFlow编程接口支持Python和C++。随着1.0版本的公布，Java、Go、R和HaskellAPI的alpha版本也将被支持。此外，TensorFlow还可在谷歌云和亚马孙云中运行。
随着0.12版本的发行，TensorFlow将支持Windows7、Windows10和Server2016。由于TensorFlow使用C++Eigen库，所以库可在ARM架构上编译和优化。这也就意味着你可以在各种服务器和移动设备上部署你的训练模型，而无需执行单独的模型解码器或者加载Python解释器。
TensorFlow支持细粒度的网格层，而且允许用户在无需用低级语言实现的情况下构建新的复杂的层类型。子图执行操作允许你在图的任意边缘引入和检索任意数据的结果。这对调试复杂的计算图模型很有帮助。
分布式TensorFlow（DistributedTensorFlow）被加进了0.8版本，它允许模型并行，这意味着模型的不同部分可在不同的并行设备上被训练。
自2016年3月，斯坦福大学、伯克利大学、多伦多大学和Udacity都将这个框架作为一个免费的大规模在线开放课程进行教授。
TensorFlow的缺点如下：
TensorFlow的每个计算流都必须构造为一个静态图，且缺乏符号性循环（symbolicloops），这会带来一些计算困难。没有对视频识别很有用的三维卷积（3-Dconvolution）。尽管TensorFlow现在比起始版本（v0.5）快了58倍，，但在执行性能方面依然落后于竞争对手。
Caffe
地址：http://caffe.berkeleyvision.org/
Caffe是贾扬清的杰作，目前他在FacebookAI平台担任首席工程师。Caffe可能是自2013年底以来第一款主流的工业级深度学习工具包。正因为Caffe优秀的卷积模型，它已经成为计算机视觉界最流行的工具包之一，并在2014年的ImageNet挑战赛中一举夺魁。Caffe遵循BSD2-Clause协议。
Caffe的快速使其完美应用于实验研究和商业部署。Caffe可在英伟达单个K40GPU上每天处理6000万张图像。这大概是1毫秒预测一张图片，4毫秒学习一张图片的速度，而且最新的版本处理速度会更快。
Caffe基于C++，因此可在多种设备上编译。它跨平台运行，并包含Windows端口。Caffe支持C++、Matlab和Python编程接口。Caffe拥有一个庞大的用户社区，人们在其中为被称为「ModelZoo（https://github.com/BVLC/caffe/wiki/Model-Zoo）」的深度网络库做贡献。AlexNet和GoogleNet就是社群用户构建的两个流行网络。
虽然Caffe在视频识别领域是一个流行的深度学习网络，但是Caffe却不能像TensorFlow、CNTK和Theano那样支持细粒度网络层。构建复杂的层类型必须以低级语言完成。由于其遗留架构，Caffe对循环网络和语言建模的支持总体上很薄弱。
Caffe2
目前，贾扬清和他在Facebook的团队正在开发新一代框架Caffe2。今年4月18日，Facebook开源了Caffe2。Caffe2与Caffe的区别是什么？Caffe2更注重模块化，在移动端、大规模部署上表现卓越。如同TensorFlow，Caffe2使用C++Eigen库，支持ARM架构。
用一个实用脚本，Caffe上的模型可轻易地被转变到Caffe2上。Caffe设计的选择使得它处理视觉类型的难题时很完美。Caffe2延续了它对视觉类问题的支持，且增加了对自然语言处理、手写识别、时序预测有帮助的RNN和LSTM支持。
期待不久之后能看到Caffe2超越Caffe，就像它宣称的那样在深度学习社区流行。
在本周三英伟达推出Volta架构的第一块加速卡TeslaV100后，Caffe的开发者第一时间展示了TeslaV100在Caffe2上运行ResNet-50的评测。数据显示在新框架和新硬件的配合下，模型每秒钟可以处理4100张图片。
链接：https://caffe2.ai/blog/2017/05/10/caffe2-adds-FP16-training-support.html
CNTK
链接：https://github.com/Microsoft/CNTK/wiki
微软的CNTK（MicrosoftCognitiveToolkit）最初是面向语音识别的框架。CNTK支持RNN和CNN类型的网络模型，从而在处理图像、手写字体和语音识别问题上，它是很好的选择。使用Python或C++编程接口，CNTK支持64位的Linux和Windows系统，在MIT许可证下发布。
与TensorFlow和Theano同样，CNTK使用向量运算符的符号图（symbolicgraph）网络，支持如矩阵加/乘或卷积等向量操作。此外，像TensorFlow和Theano一样，CNTK有丰富的细粒度的网络层构建。构建块（操作）的细粒度使用户不需要使用低层次的语言（如Caffe）就能创建新的复杂的层类型。
CNTK也像Caffe一样基于C++架构，支持跨平台的CPU/GPU部署。CNTK在AzureGPULab上显示出最高效的分布式计算性能。目前，CNTK不支持ARM架构，这限制了其在移动设备上的功能。
MXNet
MXNet（发音为mix-net）起源于卡内基梅隆大学和华盛顿大学的实验室。MXNet是一个全功能、可编程和可扩展的深度学习框架，支持最先进的深度学习模型。MXNet支持混合编程模型（命令式和声明式编程）和多种编程语言的代码（包括Python、C++、R、Scala、Julia、Matlab和JavaScript）。2017年1月30日，MXNet被列入ApacheIncubator开源项目。
MXNet支持深度学习架构，如卷积神经网络（CNN）、循环神经网络（RNN）和其包含的长短时间记忆网络（LTSM）。该框架为图像、手写文字和语音的识别和预测以及自然语言处理提供了出色的工具。有些人称MXNet是世界上最好的图像分类器。
MXNet具有可扩展的强大技术能力，如GPU并行和内存镜像、快速编程器开发和可移植性。此外，MXNet与ApacheHadoopYARN（一种通用分布式应用程序管理框架）集成，使MXNet成为TensorFlow有力的竞争对手。
MXNet不仅仅只是深度网络框架，它的区别在于支持生成对抗网络（GAN）模型。该模型启发自实验经济学方法的纳什均衡。
Torch
Torch由Facebook的RonanCollobert和SoumithChintala，Twitter的ClementFarabet（现任职于英伟达），以及GoogleDeepMind的KorayKavukcuoglu共同开发。很多科技巨头（如Facebook、Twitter和英伟达）都使用定制版的Torch用于人工智能研究，这大大促进了Torch的开发。Torch是BSD3协议下的开源项目。然而，随着Facebook对Caffe2的研究，以及其对移动设备的支持，Caffe2正成为主要的深度学习框架。
Torch的编程语言为Lua。Lua不是主流语言，在开发人员没有熟练掌握Lua之前，使用Torch很难提高开发的整体生产力。
Torch缺乏TensorFlow的分布式应用程序管理框架，也缺乏MXNet和Deeplearning4J对YARN的支持。缺乏多种编程语言的API也限制了开发人员。
PyTorch
PyTorch由AdamPaszke、SamGross与SoumithChintala等人牵头开发，其成员来自FacebookFAIR和其他多家实验室。它是一种Python优先的深度学习框架，在今年1月被开源，提供了两种高层面的功能：
使用强大的GPU加速的Tensor计算（类似numpy）
构建于基于tape的autograd系统的深度神经网络
该框架结合了Torch7高效灵活的GPU加速后端库与直观的Python前端，它的特点是快速成形、代码可读和支持最广泛的深度学习模型。如有需要，你可以复用你最喜欢的Python软件包（如numpy、scipy和Cython）来扩展PyTorch。该框架因为其灵活性和速度，在推出以后迅速得到了开发者和研究人员的青睐。随着GitHub上越来越多代码的出现，PyTorch作为新框架缺乏资源的问题已经得以缓解。
Deeplearning4J
地址：https://deeplearning4j.org/
Deeplearning4J（DL4J）是用Java和Scala编写的Apache2.0协议下的开源、分布式神经网络库。DL4J最初由SkyMind公司的AdamGibson开发，是唯一集成了Hadoop和Spark的商业级深度学习网络，并通过Hadoop和Spark协调多个主机线程。DL4J使用Map-Reduce来训练网络，同时依赖其它库来执行大型矩阵操作。
DL4J框架支持任意芯片数的GPU并行运行（对训练过程至关重要），并支持YARN（Hadoop的分布式应用程序管理框架）。DL4J支持多种深度网络架构：RBM、DBN、卷积神经网络（CNN）、循环神经网络（RNN）、RNTN和长短时间记忆网络（LTSM）。DL4J还对矢量化库Canova提供支持。
DL4J使用Java语言实现，本质上比Python快。在用多个GPU解决非平凡图像（non-trivialimage）识别任务时，它的速度与Caffe一样快。该框架在图像识别、欺诈检测和自然语言处理方面的表现出众。
Theano
地址：http://deeplearning.net/software/theano/
Theano由蒙特利尔大学算法学习人工智能实验室（MILA）维护。以Theano的创始人YoshuaBengio为首，该实验室是深度学习研究领域的重要贡献者，拥有约30至40名学生和教师。Theano支持快速开发高效的机器学习算法，在BSD协议下发布。
Theano的架构如同一个黑箱；整个代码库和接口使用Python，其中C/CUDA代码被打包成Python字符串。这使得开发人员很难导航（navigate）、调试和重构。
Theano开创了将符号图用于神经网络编程的趋势。Theano的符号式API支持循环控制（即scan），这使得实现RNN容易且高效。
Theano缺乏分布式应用程序管理框架，只支持一种编程开发语言。Theano是很好的学术研究工具，在单个CPU上运行的效率比TensorFlow更有效。然而，在开发和支持大型分布式应用程序时，使用Theano可能会遇到挑战。
在了解这些深度学习框架的基本内容后，下面我们可以看看它们之间在库资源、建模能力、速度等度量下的对比情况。
这组对比参考了多种公开基准评测，以及我们在图像/语音识别应用时对这些技术的主观印象。此外，你需要注意：
语言
当你开始一个深度学习项目时，你最好使用一个支持你所会语言的框架。比如Caffe（C++）和Torch（Lua）只能支持有限的语言（最近，随着PyTorch的出现，情况有所改观）。所以如果你希望选用上述两个框架，我们建议你事先熟悉C++或Lua语言。相比之下，TensorFlow与MXNet具有丰富的多语言支持，即使你对C++感到陌生也可以使用它们。
教程和资源
目前，各类深度学习框架的教程与可利用的资源在质量和数量上有着显著的不同。Theano，TensorFlow，Torch和MXNet有着很详尽的文档教程，很容易被初学者理解和实现。与此相比，虽然微软的CNTK和英特尔的NervanaNeon也是强大的工具，我们却很少能见到有关它们的新手级资料。此外，在研究过程中，我们发现GitHub社区的参与度不仅可以用于准确地评价不同工具的开发水平，而且还是在搜索StackOverflow或repo的GitIssues时能否快速解决问题的参考性指标。当然，作为谷歌提供的框架，TensorFlow理所当然地在教程，资源，开发者和社区贡献者的数量上遥遥领先。
CNN建模能力
卷积神经网络（CNN）经常被用于图像识别、推荐引擎和自然语言识别等方向的应用。CNN由一组多层的神经网络组成，在运行时会将输入的数据进行预定义分类的评分。CNN也可用于回归分析，例如构成自动驾驶汽车中有关转向角的模型。在横评中，我们评价一种框架的CNN建模能力考虑到以下几个特性：定义模型的机会空间、预构建层的可用性、以及可用于连接这些层的工具和功能。我们发现，Theano，Caffe和MXNet都有很好的CNN建模能力。其中，TensorFlow因为易于建立的InceptionV3模型，Torch因为其丰富的CNN资源——包括易于使用的时间卷积集使得这两种框架在CNN建模能力上脱颖而出。
RNN建模能力
循环神经网络（RNN）常用于语音识别，时间序列预测，图像字幕和其他需要处理顺序信息的任务。由于预建的RNN模型不如CNN数量多，因此，如果你已经有一个RNN深度学习项目，优先考虑旧RNN模型是在哪种框架里实现的最重要。目前，Caffe上的RNN资源最少，而Microsoft的CNTK和Torch有丰富的RNN教程和预构建模型。当然，最流行的TensorFlow中也有一些RNN资源，TFLearn和Keras中更有很多使用TensorFlow的RNN示例。
架构
为在特定框架中构建和训练新模型，易于使用和模块化的前端是至关重要的。TensorFlow，Torch和MXNet都有直观而模块化的架构，让开发相对变得简单。相比之下，我们在Caffe这样的框架上需要进行大量的工作才能创建一个新层。另外我们发现在开发过程中，因为有TensorBoardwebGUI等应用的存在，TensorFlow极易在训练中和训练后进行debug和监控。
速度
Torch和Nervana具有开源卷积神经网络基准测试的最佳性能：
https://github.com/soumith/convnet-benchmarks/blob/master/README.md
Tensorflow的性能在大多数测试中是具有竞争力的，而Caffe和Theano稍稍落后：
https://github.com/tobigithub/tensorflow-deep-learning/wiki/tf-benchmarks
微软声称他们的CNTK在一些RNN训练任务中有最快的速度。
在另一项对比Theano、Torch和TensorFlow的RNN性能的研究中，Theano是其中最快的：
https://arxiv.org/abs/1511.06435
多GPU支持
大多数深度学习应用都需要用到巨量的浮点运算（FLOP）。例如，百度的DeepSpeech识别模型需要10sExaFLOPs用于训练，这是大于10e18的计算量：
https://arxiv.org/abs/1512.02595
考虑到目前英伟达Pascal架构的TitanX等顶级显卡可以每秒执行10e9FLOP：
https://www.nvidia.com/en-us/geforce/products/10series/titan-x-pascal/
因此，假如需要在大型数据集上训练一个新模型——用单GPU机器的话——可能会需要一个星期之久。为了减少构建模型所需的时间，我们需要使用多GPU并联的方式组建自己的机器。幸运的是，上述大部分架构都可以很好地支持多GPU运算。其中，据报道MXNet有着最好的多GPU优化引擎：
http://www.allthingsdistributed.com/2016/11/mxnet-default-framework-deep-learning-aws.html
Keras兼容性
Keras是一个用于快速构建深度学习原型的高级库。我们在实践中发现，它是数据科学家应用深度学习的好帮手。Keras目前支持两种后端框架：TensorFlow与Theano，而且Keras再过不久就会成为TensorFlow的默认API：
http://www.fast.ai/2017/01/03/keras/
尽管如此，Keras的作者表示，这一高级库在未来仍会作为支持多种框架的前端存在：
https://github.com/fchollet/keras/issues/5050#issuecomment-272945570
总结
如果你想要开始深度学习，你应该从评估自己的团队技能和业务需求开始。例如，如果一个以Python为中心的团队想开发图像识别的应用程序，你应该使用TensorFlow，因为它有丰富的资源，较好性能和完整的原型工具。如果一个有Lua能力的团队希望将RNN大规模应用到生产环境中去，他们则会受益于Torch的高速和强大的RNN建模能力。
未来，我们将继续讨论在更大规模的应用中这些框架的表现。这些挑战包括多机并联时的多GPU优化，多种开源库的兼容性，如CMUSphinx和Kaldi等，尽请期待。
深度学习领域发展迅猛，江湖风起云涌。在此，咪博士为大家细细盘点、比较，各大深度学习框架。也祝大家都能训出好模型，调出好参数。
以下是咪博士的观点，供大家参考：
- 如果你是初学者，那么推荐选择 Keras 或 Gluon 这样简单易用的接口入门。至于是 Keras 还是 Gluon 就不必太纠结了，因为二者都很容易上手，完全可以都学一下。如果非要分个先后的话，可以先试试 Gluon 毕竟开发者是中国人，有官方出品的中文教程带你入门。
- 学完 Keras 或 Gluon “前端”框架之后，再选择一个“后端”框架深入学习，TensorFlow (Keras 后端) 或 MXNet (Gluon 后端) 是咪博士推荐的 2 个后端框架。TensorFlow 谷歌 (Google) 出品，MXNet 有 亚马逊 (Amazon) 支持，它们都是非常优秀的深度学习框架。至于是 TensorFlow 还是 MXNet，那就得看你的需求了。TensorFlow 受众更广，但是性能较差，而且不支持动态计算图；MXNet 目前还比较小众，但性能较好，而且支持动态计算图，十分方便搞自然语言处理 (NLP) 的朋友。
- 学习完后端框架之后，你就可以非常灵活地定制自己的神经网络，自由地在深度学习的世界里翱翔了。这里候，如果你有兴趣（或需要），可以试试其他的一些框架，如 PyTorch (灵活多变，适合研究), Caffe2 (性能优化，手机也能跑), Deeplearning4j (Java 首选，整合 Hadoop, Spark), 以及 ConvNetJS (Js 开发，浏览器上玩深度学习)。
- 其他一些深度学习框架，诸如 Theano (Lasagne, 以及 Blocks), Torch, Caffe, CNTK, Chainer, Paddle, DSSTNE, DyNet, BigDL, Neon 等，由于众多原因，咪博士就不给大家推荐了。
下面是详细的比较和说明：
一、推荐使用
受到 Torch 启发，Keras 提供了简单易用的 API 接口，特别适合初学者入门。其后端采用 TensorFlow, CNTK，以及 Theano。另外，Deeplearning4j 的 Python 也是基于 Keras 实现的。Keras 几乎已经成了 Python 神经网络的接口标准。
亚马逊 (Amazon) 和 微软 (Microsoft) 于 2017 年 10 月联合推出的深度学习 API。Gluon 类似 Keras，提供了简单易用的 API 接口。但和 Keras 不一样的地方是，Gluon 还支持动态计算图（对自然语言处理特别有用）。Gluon 后端目前采用 MXNet，未来还将支持微软的 CNTK。
谷歌 (Google) 大厂出品，追随者众多。相比其他框架，TensorFlow 速度较慢，但它提供的 TensorBoard 可视化工具还是很不错的。
已被 亚马逊 (Amazon) 选为 AWS 上的深度学习框架，支持动态图计算。MXNet 有许多中国开发者，因而有非常良好的中文文档支持。Gluon 接口使得 MXNet 像 Keras 一样简单易用。
二、值得一试
背后金主是 脸书 (Facebook) ，同样支持动态计算图，提供很好的灵活性，适合研究。
同样是 脸书 (Facebook) 出品，为生产环境设计，提供在各种平台（包括移动设备）的运行时。
与其他（大多数）基于 Python 的深度学习框架不同，Deeplearning4j 基于 Java 开发，与 Hadoop, Spark 生态结合得很好。尤其令人称道的是其优秀的文档，官司方文档直接就有中文版本。另外，虽然是面向 Java 的框架，Deeplearning4j 也提供了 Python 的接口（基于 Keras 实现）
基于 Javascript 的深度学习框架，可以在浏览器中训练深度神经网络。最重要的用途是帮助学习 Deep Learning
三、不推荐
Theano, Lasagne, 以及 Blocks
Yoshua Bengio 于 2017 年 09 月宣布不再维护 Theano，所以这个项目事实上已经宣告死亡了。其他基于 Theano 的库，如 Lasagne 和 Blocks，也可以散了。
Torch
虽然设计精良（Keras 就是参考 Torch 设计的），但它基于 Lua 语言，太过小众了。而且 Facebook 已经推出了 Python 版本的 PyTorch 了。
Caffe
Caffe2 已经正式发布了，彻底取代 Caffe 只是时间问题罢了。
CNTK
微软出品，授权协议有一些特别，而且似乎也没有什么特别亮眼的地方。
Chainer
曾经是动态计算图的首选框架，特别适用于自然语言处理。但是，现在许多其他的框架，如 MXNet, PyTorch, 以及 DyNet 也支持该特性，所以 Chainer 的这一优势也就不复存在了。
Paddle
百度的深度学习框架，受众太小。
DSSTNE
曾是亚马逊的深度学习引擎，但是很小众，而且现在亚马逊又选择了 MXNet，所以 DSSTNE 的前途就更渺茫了。
DyNet
源自卡耐基梅隆大学，支持动态计算图，但是太小众了。
BigDL
Intel 基于 spark 的深度学习库，但只能运行在 Intel 芯片之上。
Neon
据说速度很快，但太过小众，而且发展还不完善，许多特性还不支持。
参考
- https://deeplearning4j.org/compare-dl4j-tensorflow-pytorch
- http://docs.chainer.org/en/stable/comparison.html
- http://www.ipaomi.com/2017/11/06/2018-年-深度学习框架-盘点-比较-推荐/
【坚信技术技术改变世界】 【欢迎学习交流】 【免费】【视频教程】【问答社区】 【爱跑咪】【http://www.iPaoMi.com】 【QQ交流: 57148911】
8种主要排序算法的CSharp实现
8种主要排序算法的C#实现
Excerpt
8种主要排序算法的实现及优化，包含选择排序，冒泡排序，插入排序，快速排序，归并排序，堆排序，希尔排序，基数排序。文末实际测试并比较。
新的一年到了，很多园友都辞职要去追求更好的工作环境，我也是其中一个，呵呵！
最近闲暇的时候我开始重温一些常用的算法。老早就买了《算法导论》，一直都没啃下去。
这本书确实很好，只是太难读了，总是读了几章就又读不下去了！工作上也几乎用不到。
我这段时间发现看这些排序算法比以前容易了很多，就借此机会将它们整理总结起来。
一是方便以后重温，二是可以应对笔试面试。同时也希望这篇博文可以帮助各位刚辞职和正在学习排序算法的园友。
PS：有可能实现的代码并不是最优的，如果有什么错误或者值得改进的地方，还请大家帮忙指出。
简介
排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。
平均时间复杂度从高到低依次是：
冒泡排序（o(n2)），选择排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)），
归并排序（o(nlogn)），快速排序（o(nlogn)）， 希尔排序（o(n1.25)），基数排序（o(n)）
这些平均时间复杂度是参照维基百科排序算法罗列的。
是计算的理论平均值，并不意味着你的代码实现能达到这样的程度。
例如希尔排序，时间复杂度是由选择的步长决定的。基数排序时间复杂度最小，
但我实现的基数排序的速度并不是最快的，后面的结果测试图可以看到。
本文代码实现使用的数据源类型为IList
List
选择排序
选择排序是我觉得最简单暴力的排序方式了。
以前刚接触排序算法的时候，感觉算法太多搞不清，唯独记得选择排序的做法及实现。
原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头） 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> SelectSort(IList<<span>int</span>><span> data) |
过程解析：将剩余数组的最小数交换到开头。
冒泡排序
冒泡排序是笔试面试经常考的内容，虽然它是这些算法里排序速度最慢的（汗），后面有测试为证。
原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。
这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值
冒到最后。 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleSort(IList<<span>int</span>><span> data) |
过程解析：中需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。
很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1，这样会增加比较次数。
通过标识提升冒泡排序
在维基上看到，可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思，可以试试。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleSortImprovedWithFlag(IList<<span>int</span>><span> data) |
过程解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。
我起初也以为这个方法是应该有不错效果的，可是实际测试结果并不如想的那样。和未优化耗费时间一样（对于随机数列）。
由果推因，那么应该是冒泡排序对于随机数列，当剩余数列有序的时候，也没几个数要排列了！？
不过如果已经是有序数列或者部分有序的话，这个冒泡方法将会提升很大速度。
鸡尾酒排序（来回排序）
对冒泡排序进行更大的优化
冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。
原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BubbleCocktailSort(IList<<span>int</span>><span> data) |
过程解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值
向左冒泡至开头。对于剩余数列，n为始，data.Count-1-m为末。
来回冒泡比单向冒泡：对于随机数列，更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。
插入排序
插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。
原理：通过构建有序数列，将未排序的数从后向前比较，找到合适位置并插入。维基入口
第一个数当作有序数列。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> InsertSort(IList<<span>int</span>><span> data) |
过程解析：将要排序的数（索引为i）存储起来，向前查找合适位置j+1，将i-1到j+1的元素依次向后
移动一位，空出j+1，然后将之前存储的值放在这个位置。
这个方法写的不如维基上的简洁清晰，由于合适位置是j+1所以多出了对j==0的判断，但实际效率影响无差别。
建议比照维基和我写的排序，自行选择。
二分查找法优化插入排序
插入排序主要工作是在有序的数列中对要排序的数查找合适的位置，而查找里面经典的二分查找法正可以适用。
原理：通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时，大于前一个数，小于后一个数。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> InsertSortImprovedWithBinarySearch(IList<<span>int</span>><span> data) |
过程解析：需要注意的是二分查找方法实现中high-low==1的时候mid==low，所以需要33行
mid-1<0即mid==0的判断，否则下行会索引越界。
快速排序
快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。
原理：从数列中挑选一个数作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。将要排序是数列递归地分割到
最小数列，每次都让分割出的数列符合“哨兵”的规则，自然就将数列变得有序。 维基入口
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList<<span>int</span>><span> data) |
过程解析：取的哨兵是数列的第一个值，然后从第二个和末尾同时查找，左侧要显示的是小于哨兵的值，
所以要找到不小于的i，右侧要显示的是大于哨兵的值，所以要找到不大于的j。将找到的i和j的数交换，
这样可以减少交换次数。i>=j时，数列全部查找了一遍，而不符合条件j必然是在小的那一边，而哨兵
是第一个数，位置本应是小于自己的数。所以将哨兵与j交换，使符合“哨兵”的规则。
这个版本的缺点在于如果是有序数列排序的话，递归次数会很可怕的。
另一个版本
这是维基上的一个C#版本，我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”
以及“哨兵”思想融入其中，代码简洁。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList<<span>int</span>><span> data) |
过程解析：取的哨兵是数列中间的数。将数列分成两波，左侧小于等于哨兵，右侧大于等于哨兵。
也就是说，哨兵不一定处于两波数的中间。虽然哨兵不在中间，但不妨碍“哨兵”的思想的实现。所以
这个实现也可以达到快速排序的效果。但却造成了每次递归完成，要排序的数列数总和没有减少（除非i==j）。
针对这个版本的缺点，我进行了优化
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList<<span>int</span>><span> data) |
过程解析：定义了一个变量Index，来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆，
那就与j交换，否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。
归并排序
归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式，我还一直以为是一种需要意会的思想呢。
不好意思了，孤陋寡闻了，哈哈！
原理：将两个有序的数列，通过比较，合并为一个有序数列。 维基入口
为方便理解，此处实现用了List
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> List<<span>int</span>> MergeSortOnlyList(List<<span>int</span>> data, <span>int</span> low, <span>int</span><span> high) |
过程解析：将数列分为两部分，分别得到两部分数列的有序版本，然后逐个比较，将比较出的小数逐个放进
新的空数列中。当一个数列放完后，将另一个数列剩余数全部放进去。
IList版本
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> IList<<span>int</span>> MergeSort(IList<<span>int</span>><span> data) |
过程原理与上个一样，此处就不赘述了。
堆排序
堆排序是根据堆这种数据结构设计的一种算法。堆的特性：父节点的值总是小于（或大于）它的子节点。近似二叉树。
原理：将数列构建为最大堆数列（即父节点总是最大值），将最大值（即根节点）交换到数列末尾。这样要排序的数列数总和减少，
同时根节点不再是最大值，调整最大堆数列。如此重复，最后得到有序数列。 维基入口 有趣的演示
实现准备：如何将数列构造为堆——父节点i的左子节点为2i+1，右子节点为2i+2。节点i的父节点为floor((i-1)/2)。
实现如下（这个实现判断和临时变量使用太多，导致效率低，评论中@小城故事提出了更好的实现）：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> HeapSort(IList<<span>int</span>><span> data) |
过程解析：BuildMaxHeapify为排序前构建的最大堆数列方法，主要内容为从最后一个父节点开始往前将每个三角组合
（即父节点与它的两个子节点）符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大，
并返回该值之前的索引，用来判断是否进行了交换，以及原来的父节点值交换到了什么位置。在HeapSort里首先
构建了最大堆数列，然后将根节点交换到末尾，根节点不是最大值了，在while语句中对最大堆数列进行调整。
插曲：自从看了Martin Fowler大师《重构》第三版，我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切，
即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊！？上面的代码注释都是写博客的时候现加的（源代码很干净的。汗!）。
希尔排序
希尔排序是插入排序的一种更高效的改进版本。
在前面介绍的插入排序，我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。
希尔排序正是利用第一点，改善第二点，达到更理想的效果。
原理：通过奇妙的步长，插入排序间隔步长的元素，随后逐渐缩短步长至1，实现数列的插入排序。 维基入口
疑问：可以想象到排序间隔步长的数，会逐渐让数列变得有序，提升最后步长为1时标准插入排序的效率。在维基上看到这么
一句话“可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是
这是个正确的命题吗？如何证明呢？看维基上也是由果推因，说是如果不是这样，就不会排序那么快了。可这我感觉还是太牵强了，
哪位大哥发现相关资料，希望能分享出来，不胜感激。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> ShellSort(IList<<span>int</span>><span> data) |
过程解析：采用的步长是N/2，每次取半，直至1。循环内部就是标准的插入排序。
——————
修正：修正后希尔排序才是真正牛叉的希尔啊！感谢@390218462的提出
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> ShellSortCorrect(IList<<span>int</span>><span> data) |
——————
这里实现的貌似是最差的希尔排序。主要源于步长的选择。维基上有各种牛叉的“凌波微步”，极限在哪里，
喜欢挑战的同学可以去学习学习。看维基排序算法里六种排序的测试，希尔最快，比快速排序还快！！我没实现啊！
只是对于神奇的步长更充满了敬畏。
基数排序
基数排序是一种非比较型整数排序。
“非比较型”是什么意思呢？因为它内部使用的是桶排序，而桶排序是非比较型排序。
这里就要说说桶排序了。一个非常有意思的排序。
桶排序
原理：取一定数量（数列中的最大值）的编好序号的桶，将数列每个数放进编号为它的桶里，然后将不是空的桶依次倒出来，
就组成有序数列了。 维基入口
好吧！聪明的人一眼就看出桶排序的破绽了。假设只有两个数1,10000，岂不是要一万个桶！？这确实是个问题啊！我也
没想出解决办法。我起初也以为桶排序就是一个通过牺牲空间来换取时间的排序算法，它不需要比较，所以是非比较型算法。
但看了有趣的演示的桶排序后，发现世界之大，你没有解决，不代表别人没解决，睿智的人总是很多。
1，9999的桶排序实现：new Int[2];总共有两个数，得出最大数9999的位数4，取10的4次幂即10000作为分母，
要排序的数（1或9999）作为分子，并乘以数列总数2，即1*2/10000,9999*2/10000得到各自的位置0,1，完成排序。
如果是1,10000进行排序的话，上面的做法就需要稍微加一些处理——发现最大数是10的n次幂，就将它作为分母，并
放在数列末尾就好了。
如果是9999,10000进行排序的话，那就需要二维数组了，两个都在位置1，位置0没数。这个时候就需要在放
入每个位置时采用其它排序（比如插入排序）办法对这个位置的多个数排序了。
为基数排序做个过渡，我这里实现了一个个位数桶排序
涉及到了当重复的数出现的处理。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>void</span> BucketSortOnlyUnitDigit(IList<<span>int</span>><span> data) |
过程解析：indexCounter进行对每个数出现的频率的统计。indexBegin存储每个数的起始索引。
比如 1 1 2，indexCounter统计到0个0,2个1,1个2。indexBegin计算出0,1,2的起始索引分别为
0,0,2。当1个1已取出排序，那索引将+1,变为0,1,2。这样就通过提前给重复的数空出位置，解决了
重复的数出现的问题。当然，你也可以考虑用二维数组来解决重复。
下面继续基数排序。
基数排序原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。
取得最大数的位数，从低位开始，每个位上进行桶排序。
实现如下：
1 | <span> 1</span> <span>public</span> <span>static</span> IList<<span>int</span>> RadixSort(IList<<span>int</span>><span> data) |
过程解析：得出最大数的位数，从低位开始桶排序。我写的这个实现代码并不简洁，但逻辑更清晰。
后面测试的时候我们就会发现，按理来说这个实现也还行吧！ 但并不如想象的那么快！
循环的次数太多？（统计频率n次+9次计算+n次放到新的数组）*位数。
创建的新实例太多？(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数
测试比较
添加随机数组，数组有序校验，微软Linq排序
代码如下：
1 | <span> 1</span> <span>public</span> <span>static</span> <span>int</span>[] RandomSet(<span>int</span> length, <span>int</span><span> max) |
测试主体如下：
1 | <span> 1</span> <span>static</span> <span>void</span> Main(<span>string</span><span>[] args) |
剩余代码折叠在此处
View Code
测试设备：win8(64位)，i7-3630QM,8G内存，vs2012
测试结果：
100000,50000,10000,5000,1000,100依次是：
结果分析：可以看出在大数组的时候，微软自带排序更接近快速排序。而当数组变小时，速度却没有明显提升，甚至变得更慢，
比如1000和100。可以推断出在数组足够小的时候，比较已经不是影响这个方法主要因素。而根据它对大数组的表现。我们可以
推断出它应该用的是快速排序。反编译验证下：
在System.Linq.EnumerableSorter下。有兴趣的同学可以去看下详细实现。
维基上也有个测试。硬件没我的好。时间是我测试结果时间的几百倍。有兴趣的同学可以比较下。
在上面的测试中，我们可以看到快速最快，归并其次，冒泡最慢（维基上是希尔最快，估计使用的是某种神奇的步长）。
在我这里，以前实现的希尔还不如二分查找优化版的快，修正后希尔快了相当多，上面测试的希尔排序是以前错误的实现。
修正后的实现测试效果请点击右侧导航到希尔排序查看。希尔排序是一种神奇又有潜力的算法。步长不好会很挫！
而基数排序却是比平均时间复杂度为o(nlogn)的堆排序，归并排序，快速排序还要慢的，虽然它的平均时间复杂度为o(n)。
冒泡标识优化版对随机数列结果优化不明显，鸡尾酒版优化可以看到，但也不是很厉害。
插入排序二分查找优化版优化比较明显。我优化的快速排序QuickSortRelaxImproved优化也不明显。
以上是随机数列的测试结果，最大值为99999。
而对于有序数列，这些方法表现又会如何呢？
我这里就不演示了。本文末尾会附上demo，大家可以自行测试。
有意思的是:
我在测试有序数列的时候，QuickSortStrict方法栈溢出了（stack overflow exception）。这个异常
是让我去stackoverflow搜寻答案吗？哈哈！我确信我的方法不是无限循环。跳过一堆链接。。。我是
在测试10000个数排序的时候发生的错误。我跟踪后发现大约在9400多次递归的时候，栈溢出。找啊找
终于找见了一个类似的问题。上面说如果一个递归9000多次而没有返回值，也会报栈溢出的。而这个方法
对于10000个有序数列，确实每次减少一个数地递归，次数会超过限制。
我的算法理论不怎么好，对于时间复杂度和空间复杂度，还有稳定度，搞得也不怎么清楚，只知道个大致的
意思。各位要笔试面试的朋友可以去维基百科这个表来了解学习。
总结
我觉得使用IList
或者int[]来调用微软封装的方法。这样说来，题目说C#实现倒快有点名不副实了。不过这样却也方便了其它语言
朋友。比如将我这篇博文里的实现随便改改，就可以说是另一个语言版本的8种排序算法了。哈哈！在这里，
我想说下这次学习排序对我的意义：老久不怎么动脑了，突然动起来，磨磨唧唧地得出结果，最后倒也有点成就感！
在学习过程中，经常会脑子转不过弯，想不通的，只是走在路上或者睡觉前突然灵感一现，有点小惊喜的感觉！
这大概就是进步的特征吧！哈哈！这次写demo+写博客花费了不少时间，倒也收获颇多，尤其在我将8种
排序都实现之前，没进行过一次测试，全部实现完成后，测试时各种索引越界+无限循环+各种问题，没几个
能跑通的，到后来的几乎都没有问题，也算是锻炼了思维，找出错原因的能力。本篇是自我学习的一个总结，
要学习及锻炼的园友，还望一定自己实现一下，可以和我的比较一下，解除疑惑或者提出改进。
主要参考：维基百科，有趣的演示
Demo源码
PS:我打算三月份去广州发展，主要会Asp.net mvc+jquery（不介意学习新的技术[除了webform]及语言[除了java]）。
CSharp排序算法小结
前言
算法这个东西其实在开发中很少用到，特别是web开发中，但是算法也很重要，因为任何的程序，任何的软件，都是由很多的算法和数据结构组成的。但是这不意味着算法对于每个软件设计人员的实际工作都是很重要的。每个项目特点和需求特殊也导致算法运用场景上不同。但是个人觉得算法运用的好的话会给自己在程序设计的时候提供比较好的思路。下面就对一些排序算法小结一下，就当做自己的一个笔记吧。
插入排序
1.简介
插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2.算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。
3.使用插入排序为一列数字进行排序的过程
最差时间复杂度 
最优时间复杂度 
平均时间复杂度
4.C#实现
/// <summary>
/// 插入排序 /// </summary>
public class InsertionSorter
{ public void Sort(int\[\] list)
{ for (int i = 1; i < list.Length; ++i)
{ int t = list\[i\]; int j = i; while ((j > 0) && (list\[j - 1\] > t))
{
list\[j\] \= list\[j - 1\]; \--j;
}
list\[j\] \= t;
}
}
}
数组
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
希尔排序
1.简介
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
2.算法实现
原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1] 对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。
3.排序过程
最差时间复杂度 根据步长串行的不同而不同。
最优时间复杂度 O(n)
平均时间复杂度 根据步长串行的不同而不同。
4.C#实现
/// <summary>
/// 希尔排序 /// </summary>
public class ShellSorter
{ public void Sort(int\[\] list)
{ int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 \* inc + 1) ; for (; inc > 0; inc /= 3)
{ for (int i = inc + 1; i <= list.Length; i += inc)
{ int t = list\[i - 1\]; int j = i; while ((j > inc) && (list\[j - inc - 1\] > t))
{
list\[j \- 1\] = list\[j - inc - 1\];
j \-= inc;
}
list\[j \- 1\] = t;
}
}
}
}
选择排序
1.简介
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
2.实现过程
最差时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
3.C#实现
/// <summary>
/// 选择排序 /// </summary>
public class SelectionSorter
{ // public enum comp {COMP\_LESS,COMP\_EQUAL,COMP\_GRTR};
private int min; // private int m=0;
public void Sort(int\[\] list)
{ for (int i = 0; i < list.Length - 1; ++i)
{
min \= i; for (int j = i + 1; j < list.Length; ++j)
{ if (list\[j\] < list\[min\])
min \= j;
} int t = list\[min\];
list\[min\] \= list\[i\];
list\[i\] \= t; // Console.WriteLine("{0}",list\[i\]);
}
}
}
冒泡排序
1.简介
冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n^{2})），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。
2.算法实现
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3.实现过程
最差时间复杂度
最优时间复杂度
平均时间复杂度
4.C#实现
/// <summary>
/// 冒泡排序 /// </summary>
public class bubblesort
{ public void BubbleSort(int\[\] R)
{ int i, j, temp; //交换标志
bool exchange; for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序
{
exchange = false; //本趟排序开始前，交换标志应为假
for (j = R.Length - 2; j >= i; j–)
{ if (R[j + 1] < R[j]) //交换条件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //发生了交换，故将交换标志置为真
}
} if (!exchange) //本趟排序未发生交换，提前终止算法
{ break;
}
}
}
}
CSharp设计模式(10)——组合模式（Composite Pattern）
一、引言
在软件开发过程中，我们经常会遇到处理简单对象和复合对象的情况，例如对操作系统中目录的处理就是这样的一个例子，因为目录可以包括单独的文件，也可以包括文件夹，文件夹又是由文件组成的，由于简单对象和复合对象在功能上区别，导致在操作过程中必须区分简单对象和复合对象，这样就会导致客户调用带来不必要的麻烦，然而作为客户，它们希望能够始终一致地对待简单对象和复合对象。然而组合模式就是解决这样的问题。下面让我们看看组合模式是怎样解决这个问题的。
二、组合模式的详细介绍
2.1 组合模式的定义
组合模式允许你将对象组合成树形结构来表现”部分-整体“的层次结构，使得客户以一致的方式处理单个对象以及对象的组合。下面我们用绘制的例子来详细介绍组合模式，图形可以由一些基本图形元素组成（如直线，圆等），也可以由一些复杂图形组成（由基本图形元素组合而成），为了使客户对基本图形和复杂图形的调用保持一致，我们使用组合模式来达到整个目的。
组合模式实现的最关键的地方是——简单对象和复合对象必须实现相同的接口。这就是组合模式能够将组合对象和简单对象进行一致处理的原因。
2.2 组合模式的实现
介绍完组合模式的定义之后，让我们以图形的例子来实现组合模式，具体代码如下：
// 通过一些简单图形以及一些复杂图形构建图形树来演示组合模式 // 客户端调用
class Client
{ static void Main(string[] args)
{
ComplexGraphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);
complexGraphics.Add(new Line(“线段A”));
ComplexGraphics CompositeCG = new ComplexGraphics(“一个圆和一条线组成的复杂图形”);
CompositeCG.Add(new Circle(“圆”));
CompositeCG.Add(new Circle(“线段B”));
complexGraphics.Add(CompositeCG);
Line l = new Line(“线段C”);
complexGraphics.Add(l); // 显示复杂图形的画法
Console.WriteLine(“复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.WriteLine(); // 移除一个组件再显示复杂图形的画法
complexGraphics.Remove(l);
Console.WriteLine(“移除线段C后，复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.Read();
}
} ///
/// 图形抽象类， ///
public abstract class Graphics
{ public string Name { get; set; } public Graphics(string name)
{ this.Name = name;
} public abstract void Draw(); public abstract void Add(Graphics g); public abstract void Remove(Graphics g);
} ///
/// 简单图形类——线 ///
public class Line : Graphics
{ public Line(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
} // 因为简单图形在添加或移除其他图形，所以简单图形Add或Remove方法没有任何意义 // 如果客户端调用了简单图形的Add或Remove方法将会在运行时抛出异常 // 我们可以在客户端捕获该类移除并处理
public override void Add(Graphics g)
{ throw new Exception(“不能向简单图形Line添加其他图形”);
} public override void Remove(Graphics g)
{ throw new Exception(“不能向简单图形Line移除其他图形”);
}
} ///
/// 简单图形类——圆 ///
public class Circle : Graphics
{ public Circle(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
} public override void Add(Graphics g)
{ throw new Exception(“不能向简单图形Circle添加其他图形”);
} public override void Remove(Graphics g)
{ throw new Exception(“不能向简单图形Circle移除其他图形”);
}
} ///
/// 复杂图形，由一些简单图形组成,这里假设该复杂图形由一个圆两条线组成的复杂图形 ///
public class ComplexGraphics : Graphics
{ private List
: base(name)
{ } ///
/// 复杂图形的画法 ///
public override void Draw()
{ foreach (Graphics g in complexGraphicsList)
{
g.Draw();
}
} public override void Add(Graphics g)
{
complexGraphicsList.Add(g);
} public override void Remove(Graphics g)
{
complexGraphicsList.Remove(g);
}
}
由于基本图形对象不存在Add和Remove方法，上面实现中直接通过抛出一个异常的方式来解决这样的问题的，但是我们想以一种更安全的方式来解决——因为基本图形根本不存在这样的方法，我们是不是可以移除这些方法呢？为了移除这些方法，我们就不得不修改Graphics接口，我们把管理子对象的方法声明放在复合图形对象里面，这样简单对象Line、Circle使用这些方法时在编译时就会出错，这样的一种实现方式我们称为安全式的组合模式，然而上面的实现方式称为透明式的组合模式，下面让我们看看安全式的组合模式又是怎样实现的，具体实现代码如下：
/// 安全式的组合模式 /// 此方式实现的组合模式把管理子对象的方法声明在树枝构件ComplexGraphics类中 /// 这样如果叶子节点Line、Circle使用了Add或Remove方法时，就能在编译期间出现错误 /// 但这种方式虽然解决了透明式组合模式的问题，但是它使得叶子节点和树枝构件具有不一样的接口。 /// 所以这两种方式实现的组合模式各有优缺点，具体使用哪个，可以根据问题的实际情况而定
class Client
{ static void Main(string[] args)
{
ComplexGraphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);
complexGraphics.Add(new Line(“线段A”));
ComplexGraphics CompositeCG = new ComplexGraphics(“一个圆和一条线组成的复杂图形”);
CompositeCG.Add(new Circle(“圆”));
CompositeCG.Add(new Circle(“线段B”));
complexGraphics.Add(CompositeCG);
Line l = new Line(“线段C”);
complexGraphics.Add(l); // 显示复杂图形的画法
Console.WriteLine(“复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.WriteLine(); // 移除一个组件再显示复杂图形的画法
complexGraphics.Remove(l);
Console.WriteLine(“移除线段C后，复杂图形的绘制如下：”);
Console.WriteLine(“-——————–”);
complexGraphics.Draw();
Console.WriteLine(“复杂图形绘制完成”);
Console.WriteLine(“-——————–”);
Console.Read();
}
} ///
/// 图形抽象类， ///
public abstract class Graphics
{ public string Name { get; set; } public Graphics(string name)
{ this.Name = name;
} public abstract void Draw(); // 移除了Add和Remove方法 // 把管理子对象的方法放到了ComplexGraphics类中进行管理 // 因为这些方法只在复杂图形中才有意义
} ///
/// 简单图形类——线 ///
public class Line : Graphics
{ public Line(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
}
} ///
/// 简单图形类——圆 ///
public class Circle : Graphics
{ public Circle(string name)
: base(name)
{ } // 重写父类抽象方法
public override void Draw()
{
Console.WriteLine(“画 “ + Name);
}
} ///
/// 复杂图形，由一些简单图形组成,这里假设该复杂图形由一个圆两条线组成的复杂图形 ///
public class ComplexGraphics : Graphics
{ private List
: base(name)
{ } ///
/// 复杂图形的画法 ///
public override void Draw()
{ foreach (Graphics g in complexGraphicsList)
{
g.Draw();
}
} public void Add(Graphics g)
{
complexGraphicsList.Add(g);
} public void Remove(Graphics g)
{
complexGraphicsList.Remove(g);
}
}
2.3 组合模式的类图
看完了上面两者方式的实现之后，让我们具体看看组合模式的类图来理清楚组合模式中类之间的关系。
透明式的组合模式类图：
安全式组合模式的类图：
组合模式中涉及到三个角色：
- 抽象构件（Component）角色：这是一个抽象角色，上面实现中Graphics充当这个角色，它给参加组合的对象定义出了公共的接口及默认行为，可以用来管理所有的子对象（在透明式的组合模式是这样的）。在安全式的组合模式里，构件角色并不定义出管理子对象的方法，这一定义由树枝结构对象给出。
- 树叶构件（Leaf）角色：树叶对象时没有下级子对象的对象，上面实现中Line和Circle充当这个角色，定义出参加组合的原始对象的行为
- 树枝构件（Composite）角色：代表参加组合的有下级子对象的对象，上面实现中ComplexGraphics充当这个角色，树枝对象给出所有管理子对象的方法实现，如Add、Remove等。
三、组合模式的优缺点
优点：
- 组合模式使得客户端代码可以一致地处理对象和对象容器，无需关系处理的单个对象，还是组合的对象容器。
- 将”客户代码与复杂的对象容器结构“解耦。
- 可以更容易地往组合对象中加入新的构件。
缺点：使得设计更加复杂。客户端需要花更多时间理清类之间的层次关系。（这个是几乎所有设计模式所面临的问题）。
注意的问题：
- 有时候系统需要遍历一个树枝结构的子构件很多次，这时候可以考虑把遍历子构件的结构存储在父构件里面作为缓存。
- 客户端尽量不要直接调用树叶类中的方法（在我上面实现就是这样的，创建的是一个树枝的具体对象，应该使用Graphics complexGraphics = new ComplexGraphics(“一个复杂图形和两条线段组成的复杂图形”);），而是借用其父类（Graphics）的多态性完成调用，这样可以增加代码的复用性。
四、组合模式的使用场景
在以下情况下应该考虑使用组合模式：
- 需要表示一个对象整体或部分的层次结构。
- 希望用户忽略组合对象与单个对象的不同，用户将统一地使用组合结构中的所有对象。
五、组合模式在.NET中的应用
组合模式在.NET 中最典型的应用就是应用与WinForms和Web的开发中，在.NET类库中，都为这两个平台提供了很多现有的控件，然而System.Windows.Forms.dll中System.Windows.Forms.Control类就应用了组合模式，因为控件包括Label、TextBox等这样的简单控件，同时也包括GroupBox、DataGrid这样复合的控件，每个控件都需要调用OnPaint方法来进行控件显示，为了表示这种对象之间整体与部分的层次结构，微软把Control类的实现应用了组合模式（确切地说应用了透明式的组合模式）。
六、总结
到这里组合模式的介绍就结束了，组合模式解耦了客户程序与复杂元素内部结构，从而使客户程序可以向处理简单元素一样来处理复杂元素。
本文中所有源码：设计模式之组合模式
CSharp设计模式(12)——享元模式（Flyweight Pattern）
一、引言
在软件开发过程，如果我们需要重复使用某个对象的时候，如果我们重复地使用new创建这个对象的话，这样我们在内存就需要多次地去申请内存空间了，这样可能会出现内存使用越来越多的情况，这样的问题是非常严重，然而享元模式可以解决这个问题，下面具体看看享元模式是如何去解决这个问题的。
二、享元模式的详细介绍
在前面说了，享元模式可以解决上面的问题了，在介绍享元模式之前，让我们先要分析下如果去解决上面那个问题，上面的问题就是重复创建了同一个对象，如果让我们去解决这个问题肯定会这样想：“既然都是同一个对象，能不能只创建一个对象，然后下次需要创建这个对象的时候，让它直接用已经创建好了的对象就好了”，也就是说——让一个对象共享。不错，这个也是享元模式的实现精髓所在。
2.1 定义
介绍完享元模式的精髓之后，让我们具体看看享元模式的正式定义：
享元模式——运用共享技术有效地支持大量细粒度的对象。享元模式可以避免大量相似类的开销，在软件开发中如果需要生成大量细粒度的类实例来表示数据，如果这些实例除了几个参数外基本上都是相同的，这时候就可以使用享元模式来大幅度减少需要实例化类的数量。如果能把这些参数（指的这些类实例不同的参数）移动类实例外面，在方法调用时将他们传递进来，这样就可以通过共享大幅度地减少单个实例的数目。（这个也是享元模式的实现要领）,然而我们把类实例外面的参数称为享元对象的外部状态，把在享元对象内部定义称为内部状态。具体享元对象的内部状态与外部状态的定义为：
内部状态：在享元对象的内部并且不会随着环境的改变而改变的共享部分
外部状态：随环境改变而改变的，不可以共享的状态。
2.2 享元模式实现
分析完享元模式的实现思路之后，相信大家实现享元模式肯定没什么问题了，下面以一个实际的应用来实现下享元模式。这个例子是：一个文本编辑器中会出现很多字面，使用享元模式去实现这个文本编辑器的话，会把每个字面做成一个享元对象。享元对象的内部状态就是这个字面，而字母在文本中的位置和字体风格等其他信息就是它的外部状态。下面就以这个例子来实现下享元模式，具体实现代码如下：
///
/// 客户端调用 ///
class Client
{ static void Main(string[] args)
{ // 定义外部状态，例如字母的位置等信息
int externalstate = 10; // 初始化享元工厂
FlyweightFactory factory = new FlyweightFactory(); // 判断是否已经创建了字母A，如果已经创建就直接使用创建的对象A
Flyweight fa = factory.GetFlyweight(“A”); if (fa != null)
{ // 把外部状态作为享元对象的方法调用参数
fa.Operation(–externalstate);
} // 判断是否已经创建了字母B
Flyweight fb = factory.GetFlyweight(“B”); if (fb != null)
{
fb.Operation(--externalstate);
} // 判断是否已经创建了字母C
Flyweight fc = factory.GetFlyweight(“C”); if (fc != null)
{
fc.Operation(--externalstate);
} // 判断是否已经创建了字母D
Flyweight fd= factory.GetFlyweight(“D”); if (fd != null)
{
fd.Operation(--externalstate);
} else {
Console.WriteLine(“驻留池中不存在字符串D”); // 这时候就需要创建一个对象并放入驻留池中
ConcreteFlyweight d = new ConcreteFlyweight(“D”);
factory.flyweights.Add(“D”, d);
}
Console.Read();
}
} /// <summary>
/// 享元工厂，负责创建和管理享元对象 /// </summary>
public class FlyweightFactory
{ // 最好使用泛型Dictionary<string,Flyweighy> //public Dictionary<string, Flyweight> flyweights = new Dictionary<string, Flyweight>();
public Hashtable flyweights = new Hashtable(); public FlyweightFactory()
{
flyweights.Add("A", new ConcreteFlyweight("A"));
flyweights.Add("B", new ConcreteFlyweight("B"));
flyweights.Add("C", new ConcreteFlyweight("C"));
} public Flyweight GetFlyweight(string key)
{
// 更好的实现如下
//Flyweight flyweight = flyweights[key] as Flyweight;
//if (flyweight == null)
//{
// Console.WriteLine(“驻留池中不存在字符串” + key);
// flyweight = new ConcreteFlyweight(key);
//}
//return flyweight;
return flyweights[key] as Flyweight;
}
} ///
/// 抽象享元类，提供具体享元类具有的方法 ///
public abstract class Flyweight
{ public abstract void Operation(int extrinsicstate);
} // 具体的享元对象，这样我们不把每个字母设计成一个单独的类了，而是作为把共享的字母作为享元对象的内部状态
public class ConcreteFlyweight : Flyweight
{ // 内部状态
private string intrinsicstate ; // 构造函数
public ConcreteFlyweight(string innerState)
{ this.intrinsicstate = innerState;
} ///
/// 享元类的实例方法 ///
/// 外部状态
public override void Operation(int extrinsicstate)
{
Console.WriteLine(“具体实现类: intrinsicstate {0}, extrinsicstate {1}”, intrinsicstate, extrinsicstate);
}
}
在享元模式的实现中，我们没有像之前一样，把一个细粒度的类实例设计成一个单独的类，而是把它作为共享对象的内部状态放在共享类的内部定义，具体的解释注释中都有了，大家可以参考注释去进一步理解享元模式。
2.3 享元模式的类图
看完享元模式的实现之后，为了帮助大家理清楚享元模式中各类之间的关系，下面给出上面实现代码中的类图，如下所示：
（摘自http://www.cnblogs.com/zhenyulu/articles/55793.html）
在上图中，涉及的角色如下几种角色：
抽象享元角色（Flyweight）:此角色是所有的具体享元类的基类，为这些类规定出需要实现的公共接口。那些需要外部状态的操作可以通过调用方法以参数形式传入。
具体享元角色（ConcreteFlyweight）：实现抽象享元角色所规定的接口。如果有内部状态的话，可以在类内部定义。
享元工厂角色（FlyweightFactory）：本角色复杂创建和管理享元角色。本角色必须保证享元对象可以被系统适当地共享，当一个客户端对象调用一个享元对象的时候，享元工厂角色检查系统中是否已经有一个符合要求的享元对象，如果已经存在，享元工厂角色就提供已存在的享元对象，如果系统中没有一个符合的享元对象的话，享元工厂角色就应当创建一个合适的享元对象。
客户端角色（Client）：本角色需要存储所有享元对象的外部状态。
注：上面的实现只是单纯的享元模式，同时还有复合的享元模式，由于复合享元模式较复杂，这里就不给出实现了。
三、享元模式的优缺点
分析完享元模式的实现之后，让我们继续分析下享元模式的优缺点：
优点：
- 降低了系统中对象的数量，从而降低了系统中细粒度对象给内存带来的压力。
缺点：
- 为了使对象可以共享，需要将一些状态外部化，这使得程序的逻辑更复杂，使系统复杂化。
- 享元模式将享元对象的状态外部化，而读取外部状态使得运行时间稍微变长。
四、使用场景
在下面所有条件都满足时，可以考虑使用享元模式：
- 一个系统中有大量的对象；
- 这些对象耗费大量的内存；
- 这些对象中的状态大部分都可以被外部化
- 这些对象可以按照内部状态分成很多的组，当把外部对象从对象中剔除时，每一个组都可以仅用一个对象代替
- 软件系统不依赖这些对象的身份，
满足上面的条件的系统可以使用享元模式。但是使用享元模式需要额外维护一个记录子系统已有的所有享元的表，而这也需要耗费资源，所以，应当在有足够多的享元实例可共享时才值得使用享元模式。
注：在.NET类库中，string类的实现就使用了享元模式，更多内容可以参考字符串驻留池的介绍，同时也可以参考这个博文深入理解.NET中string类的设计——http://www.cnblogs.com/artech/archive/2010/11/25/internedstring.html
五、总结
到这里，享元模式的介绍就结束了，享元模式主要用来解决由于大量的细粒度对象所造成的内存开销的问题，它在实际的开发中并不常用，可以作为底层的提升性能的一种手段。
CSharp设计模式(14)——模板方法模式（Template Method）
一、引言
提到模板，大家肯定不免想到生活中的“简历模板”、“论文模板”、“Word中模版文件”等，在现实生活中，模板的概念就是——有一个规定的格式，然后每个人都可以根据自己的需求或情况去更新它，例如简历模板，下载下来的简历模板的格式都是相同的，然而我们下载下来简历模板之后我们可以根据自己的情况填充不同的内容要完成属于自己的简历。在设计模式中，模板方法模式中模板和生活中模板概念非常类似，下面让我们就详细介绍模板方法的定义，大家可以根据生活中模板的概念来理解模板方法的定义。
二、模板方法模式详细介绍
2.1 模板方法模式的定义
模板方法模式——在一个抽象类中定义一个操作中的算法骨架（对应于生活中的大家下载的模板），而将一些步骤延迟到子类中去实现（对应于我们根据自己的情况向模板填充内容）。模板方法使得子类可以不改变一个算法的结构前提下，重新定义算法的某些特定步骤，模板方法模式把不变行为搬到超类中，从而去除了子类中的重复代码。
2.2 模板方法模式的实现
理解了模板方法的定义之后，自然实现模板方法也不是什么难事了，下面以生活中炒蔬菜为例来实现下模板方法模式。在现实生活中，做蔬菜的步骤都大致相同，如果我们针对每种蔬菜类定义一个烧的方法，这样在每个类中都有很多相同的代码，为了解决这个问题，我们一般的思路肯定是把相同的部分抽象出来到抽象类中去定义，具体子类来实现具体的不同部分，这个思路也正式模板方法的实现精髓所在，具体实现代码如下：
// 客户端调用
class Client
{ static void Main(string[] args)
{ // 创建一个菠菜实例并调用模板方法
Spinach spinach = new Spinach();
spinach.CookVegetabel();
Console.Read();
}
} public abstract class Vegetabel
{ // 模板方法，不要把模版方法定义为Virtual或abstract方法，避免被子类重写，防止更改流程的执行顺序
public void CookVegetabel()
{
Console.WriteLine(“抄蔬菜的一般做法”); this.pourOil(); this.HeatOil(); this.pourVegetable(); this.stir_fry();
} // 第一步倒油
public void pourOil()
{
Console.WriteLine(“倒油”);
} // 把油烧热
public void HeatOil()
{
Console.WriteLine(“把油烧热”);
} // 油热了之后倒蔬菜下去，具体哪种蔬菜由子类决定
public abstract void pourVegetable(); // 开发翻炒蔬菜
public void stir_fry()
{
Console.WriteLine(“翻炒”);
}
} // 菠菜
public class Spinach : Vegetabel
{ public override void pourVegetable()
{
Console.WriteLine(“倒菠菜进锅中”);
}
} // 大白菜
public class ChineseCabbage : Vegetabel
{ public override void pourVegetable()
{
Console.WriteLine(“倒大白菜进锅中”);
}
}
在上面的实现中，具体子类中重写了导入蔬菜种类的方法，因为这个真是烧菜方法中不同的地方，所以由具体子类去实现它。
2.3 模板方法模式的类图
实现完模板方法模式之后，让我们看看模板方法的类图结构，以理清该模式中类之间的关系，具体类图如下：
模板方法模式中涉及了两个角色：
- 抽象模板角色（Vegetable扮演这个角色）：定义了一个或多个抽象操作，以便让子类实现，这些抽象操作称为基本操作。
- 具体模板角色（ChineseCabbage和Spinach扮演这个角色）：实现父类所定义的一个或多个抽象方法。
三、模板方法模式的优缺点
下面让我们继续分析下模板方法的优缺点。
优点：
- 实现了代码复用
- 能够灵活应对子步骤的变化，符合开放-封闭原则
缺点：因为引入了一个抽象类，如果具体实现过多的话，需要用户或开发人员需要花更多的时间去理清类之间的关系。
附：在.NET中模板方法的应用也很多，例如我们在开发自定义的Web控件或WinForm控件时，我们只需要重写某个控件的部分方法。
四、总结
到这里，模板方法的介绍就结束了，模板方法模式在抽象类中定义了算法的实现步骤，将这些步骤的实现延迟到具体子类中去实现，从而使所有子类复用了父类的代码，所以模板方法模式是基于继承的一种实现代码复用的技术。