数据结构,面向对象2

2019-11-06 11:30 来源:未知

成员和嵌套(组合)

c#常用数据结构解析

谈谈在平时使用U3D时经常用到的数据结构和各种数据结构的应用场景吧。
1.几种常见的数据结构 
这里主要总结下小匹夫在工作中常碰到的几种数据结构:Array,ArrayList,List<T>,LinkedList<T>,Queue<T>,Stack<T>,Dictionary<K,T>
数组Array:  
数组是最简单的数据结构。其具有如下特点:
数组存储在连续的内存上。
数组的内容都是相同类型。
数组可以直接通过下标访问。
  数组Array的创建:

int size = 5;
int[] test = new int[size];

  创建一个新的数组时将在 CLR 托管堆中分配一块连续的内存空间,来盛放数量为size,类型为所声明类型的数组元素。如果类型为值类型,则将会有size个未装箱的该类型的值被创建。如果类型为引用类型,则将会有size个相应类型的引用被创建。
  由于是在连续内存上存储的,所以它的索引速度非常快,访问一个元素的时间是恒定的也就是说与数组的元素数量无关,而且赋值与修改元素也很简单。

string[] test2 = new string[3];

//赋值
test2[0] = "chen";
test2[1] = "j";
test2[2] = "d";

//修改
test2[0] = "chenjd";

  但是有优点,那么就一定会伴随着缺点。由于是连续存储,所以在两个元素之间插入新的元素就变得不方便。而且就像上面的代码所显示的那样,声明一个新的数组时,必须指定其长度,这就会存在一个潜在的问题,那就是当我们声明的长度过长时,显然会浪费内存,当我们声明长度过短的时候,则面临这溢出的风险。这就使得写代码像是投机,小匹夫很厌恶这样的行为!针对这种缺点,下面隆重推出ArrayList。
ArrayList:  
为了解决数组创建时必须指定长度以及只能存放相同类型的缺点而推出的数据结构。ArrayList是System.Collections命名空间下的一部分,所以若要使用则必须引入System.Collections。正如上文所说,ArrayList解决了数组的一些缺点。
不必在声明ArrayList时指定它的长度,这是由于ArrayList对象的长度是按照其中存储的数据来动态增长与缩减的。
ArrayList可以存储不同类型的元素。这是由于ArrayList会把它的元素都当做Object来处理。因而,加入不同类型的元素是允许的。
  ArrayList的操作:

ArrayList test3 = new ArrayList();

//新增数据
test3.Add("chen");
test3.Add("j");
test3.Add("d");
test3.Add("is");
test3.Add(25);

//修改数据
test3[4] = 26;

//删除数据
test3.RemoveAt(4);

 

  说了那么一堆”优点“,也该说说缺点了吧。为什么要给”优点”打上引号呢?那是因为ArrayList可以存储不同类型数据的原因是由于把所有的类型都当做Object来做处理,也就是说ArrayList的元素其实都是Object类型的,辣么问题就来了。

ArrayList不是类型安全的。因为把不同的类型都当做Object来做处理,很有可能会在使用ArrayList时发生类型不匹配的情况。
如上文所诉,数组存储值类型时并未发生装箱,但是ArrayList由于把所有类型都当做了Object,所以不可避免的当插入值类型时会发生装箱操作,在索引取值时会发生拆箱操作。这能忍吗?
注:为何说频繁的没有必要的装箱和拆箱不能忍呢?且听小匹夫慢慢道来:所谓装箱 (boxing):就是值类型实例到对象的转换(百度百科)。那么拆箱:就是将引用类型转换为值类型咯(还是来自百度百科)。下面举个栗子~

//装箱,将String类型的值FanyoyChenjd赋值给对象。

String  info = ”FanyoyChenjd”;  
object obj=(object)info; 
 
//拆箱,从Obj中提取值给info
object obj = "FanyoyChenjd";
String info = (String)obj;

那么结论呢?显然,从原理上可以看出,装箱时,生成的是全新的引用对象,这会有时间损耗,也就是造成效率降低。

List<T>泛型List  
为了解决ArrayList不安全类型与装箱拆箱的缺点,所以出现了泛型的概念,作为一种新的数组类型引入。也是工作中经常用到的数组类型。和ArrayList很相似,长度都可以灵活的改变,最大的不同在于在声明List集合时,我们同时需要为其声明List集合内数据的对象类型,这点又和Array很相似,其实List<T>内部使用了Array来实现。

List<string> test4 = new List<string>(); 
 
//新增数据 
test4.Add(“Fanyoy”); 
test4.Add(“Chenjd”); 

//修改数据 
test4[1] = “murongxiaopifu”;  
   
//移除数据 
test4.RemoveAt(0);

 这么做最大的好处就是即确保了类型安全。也取消了装箱和拆箱的操作。
它融合了Array可以快速访问的优点以及ArrayList长度可以灵活变化的优点。
假设各位和小匹夫一样,在工作中最常使用的一种数据结构就是它。那么我们是否能再多一点好奇心呢?那就是探究一下,如果我们自己实现一个类似的数据结构,该从何处下手呢?

刚才说过了,List<T>的内部其实也是一个Array,且是强类型的,所以我们的简单实现(暂且称之为EggArray<T>)也秉承这个特点,内部通过一个Array来实现,且需要声明类型。但是同时我们也看到List<T>继承和实现了很多接口,比如IEnumerable接口等,而且值类型和引用类型通吃。这里为了EggArray<T>实现起来轻装简行,我们不继承List<T>继承的各种接口,同时我们的EggArray只服务于引用类型。
那么首先明确了,它是一个处理引用类型,且实现了泛型的。那么定义就出来了:

//EggArray类
//定义

public
class 
EggArray<T> where T : class
{
}

那么下一步呢?该确定它的内部成员了,就先从字段和属性开始吧。
属性&变量
属性
说明
Capacity EggArray的容量
Count EggArray中的元素个数
items T[],一个Array,因为上一篇文章说过List<T>的内部其实还是Array,所以内部我们也使用Array

//EggArray<T>的属性&&变量

private int capacity;
private int count;
private T[] items;
public int Count
{
    get
    {
        return this.count;
    }
}
 
public int Capacity
{
    get
    {
        return this.capacity;
    }
}

之后呢?好像是需要一个构造函数了。上文也说了,貌似new的时候不需要指定容量呀。那么我们就把构造函数做成这样吧。
构造函数:
构造函数 说明
EggArray() 初始化 EggArray<T> 类的新实例,该实例为空并且具有默认初始容量。
EggArray(int32) 初始化 EggArray<T> 类的新实例,该实例为空并且具有指定的初始容量。

//EggArray的构造函数,默认容量为8

public
EggArray() : this(8)
{

}

 
public
EggArray(int
capacity)
{

    this.capacity
 = capacity;

    this.items
 = new

T[capacity];

}

好了,构造函数也说完了,那么就介绍一下私有方法,因为运行机制全部是有私有方法来运筹的,公共方法只不过是开放给我们的使用的罢了。小匹夫对公共方法的实现没有兴趣,这里就不做演示了。
刚刚也说了,List<T>是无所谓初始长度的,可以用Add()方法往里面添加元素,同时也不可能是有一个无限大的空间让它来存储,那么究竟它究竟为何能做到这一点呢?因为有一个能动态调整内部数组大小的方法存在,且调整大小是按照原有长度成倍增长的。我们姑且称之为Resize。
那么在进行下面的内容之前,小匹夫还想先问各位一个问题:

List<int>
 test = new

List<int>(){0,1,2,3,4,5,6,7,8,9};

                int
count = 0;

                for(int
i = 0; i < test.Count; i++)
                {
                        if(i == 1)
                                test.Remove(test[i]);
                        count++;
                }
                Debug.Log (count);

上面这段代码会输出什么呢?答案是9。可能有的盆油会感到奇怪,test进去时长度明明是10啊。就算你中间Remove了一个元素,可为什么会影响后面的元素呢?(比如把index为1的元素remove掉,原来index为2的元素现在的index就成1了。)感觉乱套有木有?其实这里List<T>在执行remove的同时,也把内部的数组压缩了。所以也肯定有一个方法用来压缩咯。我们姑且称为Compact。
私有方法
私有方法
说明
Resize 当数组元素个数大于或等于数组的容量时,调用该方法进行扩容,会创建一个新的Array存放数据,“增长因子”为2
Compact 压缩数组,在Remove时候默认调用

//当数组元素个[/size][/backcolor][/color][i][color=White][backcolor=DarkGreen][size=2]数不小于数组容量时,需要扩容,增长因子growthFactor为2

private

void 
Resize()

{

    int

capacity = this.capacity
 * growthFactor;

    if

(this.count
 > capacity)

    {

        this.count
 = capacity;

    }

    T[]
 destinationArray = new

T[capacity];

    Array.Copy(this.items,
 destinationArray, this.count);

    this.items
 = destinationArray;

    this.capacity
 = capacity;

}

 private

void 
Compact()

        {

            int

num = 0;

            for

(int

i = 0; i < this.count;
 i++)

            {

                if

(this.items[i]
 == null)

                {

                    num++;

                }

                else

if 
(num > 0)

                {

                    this.items[i
 - num] = this.items[i];

                    this.items[i]
 = null;

                }

            }

            this.count
 -= num;

        }[i][i][i]

LinkedList<T>  
也就是链表了。和上述的数组最大的不同之处就是在于链表在内存存储的排序上可能是不连续的。这是由于链表是通过上一个元素指向下一个元素来排列的,所以可能不能通过下标来访问。如图

  既然链表最大的特点就是存储在内存的空间不一定连续,那么链表相对于数组最大优势和劣势就显而易见了。
向链表中插入或删除节点无需调整结构的容量。因为本身不是连续存储而是靠各对象的指针所决定,所以添加元素和删除元素都要比数组要有优势。
链表适合在需要有序的排序的情境下增加新的元素,这里还拿数组做对比,例如要在数组中间某个位置增加新的元素,则可能需要移动移动很多元素,而对于链表而言可能只是若干元素的指向发生变化而已。
有优点就有缺点,由于其在内存空间中不一定是连续排列,所以访问时候无法利用下标,而是必须从头结点开始,逐次遍历下一个节点直到寻找到目标。所以当需要快速访问对象时,数组无疑更有优势。
  综上,链表适合元素数量不固定,需要两端存取且经常增减节点的情况。
  关于链表的使用,MSDN上有详细的例子。
Queue<T>  
在Queue<T>这种数据结构中,最先插入在元素将是最先被删除;反之最后插入的元素将最后被删除,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。通过使用Enqueue和Dequeue这两个方法来实现对 Queue<T> 的存取。

  一些需要注意的地方:
先进先出的情景。
默认情况下,Queue<T>的初始容量为32, 增长因子为2.0。
当使用Enqueue时,会判断队列的长度是否足够,若不足,则依据增长因子来增加容量,例如当为初始的2.0时,则队列容量增长2倍。
乏善可陈。
  关于Queue<T>的使用方法,MSDN上也有相应的例子。
Stack<T>
  
  与Queue<T>相对,当需要使用后进先出顺序(LIFO)的数据结构时,我们就需要用到Stack<T>了。
  一些需要注意的地方:
后进先出的情景。
默认容量为10。
使用pop和push来操作。
乏善可陈。
  同样,在MSDN你也可以看到大量Stack<T>的例子。
Dictionary<K,T>  
字典这东西,小匹夫可是喜欢的不得了。看官们自己也可以想想字典是不是很招人喜欢,创建一个字典之后就可以往里面扔东西,增加、删除、访问那叫一个快字了得。但是直到小匹夫日前看了一个大神的文章,才又想起了那句话“啥好事咋能让你都占了呢”。那么字典背后到底隐藏着什么迷雾,拨开重重迷雾之后,是否才是真相?且听下回分。。。等等,应该是下面就让我们来分析一下字典吧。
  提到字典就不得不说Hashtable哈希表以及Hashing(哈希,也有叫散列的),因为字典的实现方式就是哈希表的实现方式,只不过字典是类型安全的,也就是说当创建字典时,必须声明key和item的类型,这是第一条字典与哈希表的区别。关于哈希表的内容推荐看下这篇博客哈希表。关于哈希,简单的说就是一种将任意长度的消息压缩到某一固定长度,比如某学校的学生学号范围从00000~99999,总共5位数字,若每个数字都对应一个索引的话,那么就是100000个索引,但是如果我们使用后3位作为索引,那么索引的范围就变成了000~999了,当然会冲突的情况,这种情况就是哈希冲突(Hash Collisions)了。扯远了,关于具体的实现原理还是去看小匹夫推荐的那篇博客吧,当然那篇博客上面那个大大的转字也是蛮刺眼的。。。
  回到Dictionary<K,T>,我们在对字典的操作中各种时间上的优势都享受到了,那么它的劣势到底在哪呢?对嘞,就是空间。以空间换时间,通过更多的内存开销来满足我们对速度的追求。在创建字典时,我们可以传入一个容量值,但实际使用的容量并非该值。而是使用“不小于该值的最小质数来作为它使用的实际容量,最小是3。”(老赵),当有了实际容量之后,并非直接实现索引,而是通过创建额外的2个数组来实现间接的索引,即int[] buckets和Entry[] entries两个数组(即buckets中保存的其实是entries数组的下标),这里就是第二条字典与哈希表的区别,还记得哈希冲突吗?对,第二个区别就是处理哈希冲突的策略是不同的!字典会采用额外的数据结构来处理哈希冲突,这就是刚才提到的数组之一buckets桶了,buckets的长度就是字典的真实长度,因为buckets就是字典每个位置的映射,然后buckets中的每个元素都是一个链表,用来存储相同哈希的元素,然后再分配存储空间。

因此,我们面临的情况就是,即便我们新建了一个空的字典,那么伴随而来的是2个长度为3的数组。所以当处理的数据不多时,还是慎重使用字典为好,很多情况下使用数组也是可以接受的。

2.几种常见数据结构的使用情景
Array 需要处理的元素数量确定并且需要使用下标时可以考虑,不过建议使用List<T>
ArrayList 不推荐使用,建议用List<T>
List<T>泛型List 需要处理的元素数量不确定时 通常建议使用
LinkedList<T> 链表适合元素数量不固定,需要经常增减节点的情况,2端都可以增减
Queue<T> 先进先出的情况
Stack<T> 后进先出的情况

线程池概述

由系统维护的容纳线程的容器,由CLR控制的所有AppDomain共享。线程池可用于执行任务、发送工作项、处理异步 I/O、代表其他线程等待以及处理计时器。

 

成员

Dictionary<K,T> 需要键值对,快速操作

线程池与线程

性能:每开启一个新的线程都要消耗内存空间及资源(默认情况下大约1 MB的内存),同时多线程情况下操作系统必须调度可运行的线程并执行上下文切换,所以太多的线程还对性能不利。而线程池其目的是为了减少开启新线程消耗的资源(使用线程池中的空闲线程,不必再开启新线程,以及统一管理线程(线程池中的线程执行完毕后,回归到线程池内,等待新任务))。

时间:无论何时启动一个线程,都需要时间(几百毫秒),用于创建新的局部变量堆,线程池预先创建了一组可回收线程,因此可以缩短过载时间。

线程池缺点:线程池的性能损耗优于线程(通过共享和回收线程的方式实现),但是:

1.线程池不支持线程的取消、完成、失败通知等交互性操作。

2.线程池不支持线程执行的先后次序排序。

3.不能设置池化线程(线程池内的线程)的Name,会增加代码调试难度。

4.池化线程通常都是后台线程,优先级为ThreadPriority.Normal。

5.池化线程阻塞会影响性能(阻塞会使CLR错误地认为它占用了大量CPU。CLR能够检测或补偿(往池中注入更多线程),但是这可能使线程池受到后续超负荷的印象。Task解决了这个问题)。

6.线程池使用的是全局队列,全局队列中的线程依旧会存在竞争共享资源的情况,从而影响性能(Task解决了这个问题方案是使用本地队列)。

 

1.类的成员:变量,方法,属性

变量:

  实例变量(字段)

    公有实例变量(字段)

1 class Foo:
2     def __init__(self,name):
3         self.name = name#公有实例变量
4     
5      def func(self):
6         return self.name

 

    私有实例变量(字段)

1 class Foo:
2     def __init__(self):
3         pass
4     def __func(self):
5         print("私有实例变量")
6 
7 obj = Foo()
8 obj.func()#此处无法调用

 

  类变量(静态字段)

    公有类变量(静态字段)

 1 class Foo:
 2     a = 1#公有类变量
 3     def __init__(self):
 4         pass
 5     def func(self):
 6         return self.a
 7 
 8 obj = Foo()
 9 print(obj.a)
10 print(Foo.a)

 

    私有类变量(静态字段)

1 class Foo:
2     __a = 1
3     def __init__(self):
4         pass
5     def func(self):
6         print(self.a)#不能引用,错
7 
8 obj = Foo()
9 obj.func()

总结:

  公有实例变量可以在类的方法中使用,也可以用实例化的对象调用

  私有实例变量不能在对象调用,只能在类中用其他方法调用后,再使用对象调用

  公有类变量可以在类中调用,也可以用对象调用

  私有类变量只能在类中使用其他方法调用,不能使用对象调用,子类也不能调用(如果必须要用,先在父类中使用方法来调用这个私有类变量,再在子类中调用这个方法)

 

方法:

  实例方法

  

1 class Foo:
2     def __init__(self,name):
3         self.name = name
4     def func(self):#实例方法
5         print(self.name)
6 
7 obj = Foo("abc")
8 obj.func()

 

  静态方法

1 class Foo:
2     def __init__(self,name)
3         self.name = name
4     @staticmethod#静态方法
5     def display(a1,a2):
6         return a1 + a2
7 
8 Foo.display(1,2)
#如果无需使用对象中封装的值,就可以使用静态方法

 

  类方法

1 class Foo:
2     @classmethod
3     def show(cls,x1,x2):#默认第一个参数是类(cls)
4         print(cls,x1,x2)
5 
6 ret = Foo.show(1,2)
7 print(ret)

总结:

  实例方法:至少有一个参数,第一个参数必须是实例对象,默认是self

  静态方法:可以没有参数,也无需使用对象中封装的值,方法上面需要加@staticmethod

  类方法:至少有一个参数,第一个参数必须是类,默认是cls,方法上面需要加@classmethod

 

属性(通过方法改造出来):

  

 1 class Foo:
 2     def __init__(self):
 3         pass
 4     @property
 5     def start(self):
 6         return 1
 7     @property
 8     def end(self):
 9         return 2
10 
11 obj = Foo()
12 print(obj.start)
13 print(obj.end)

总结:属性编写时,方法上面写@property,方法中只有一个参数self

  调用时,无需加括号,直接是对象.方法

  对于简单的方法,当无需传参且有返回值时,可以使用属性

 

C#数据结构一:基础知识

 

在学习数据结构之前先要学习几个相关的概念及术语1、数据(Data):数据是外部世界信息的载体,它能被计算机识别、存储和加工处理,是计算机程序加工的原料。2、数据元素(Data Element)和数据项:数据元素是数据的基本单位,有时也被称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项组成;数据项是不可分割的、含有独立意义的最小数据单位,数据项有时也称为字段(Field)或域(Domain).之间关系为数据项组成数据元素,数据元素组成数据(,数据组成文件)。使用数据库模型来举例说明:3、数据对象(Data Object):性质相同的数据元素的集合,是数据的一个子集,例如字母表对象{a,b,c,…x,y,z}4、数据类型(Data Type):数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性;程序中每个变量、常量或表达式的结果都应该属于某种确定的数据类型。数据类型可分可两类:一类是非结构的原子类型,如C#的基本类型;另一类是结构类型,其成分由多个结构类型组成,可以分解;如C#的数组类型。5、数据结构(Data Struct):相互之间存在一种或多种关系 的数据元素的集合。通常有4类基本数据结构:1)集合(Set)2)线性结构(Linear Structure)3)树形结构(True Structure)4)图状结构(Graphic Structure)数据结构(Data Structrue)简记为DS,是一个二元组,DS=(D,S),其中D为数据元素的有限集合,R是数据元素之间关系的有限集合。6、算法(Algorithm):是对某一特定类型的问题的求解步骤的一种描述,是指令的有限序列。它具有有穷性(Finity)、确定性(Unambiguousness)、输入(Input)、输出(Output)和有效性(Realizability)。针对算法优劣的评价标准包括正确性(Correctness)、可读性(Readability)、健壮性(Robustness鲁棒性)、运行时间(Running Time)和占用空间(Storage Space)。7、算法的时间复杂度(Time Complexity):指算法的运行时间与问题规模的对应关系。通常把算法中基本操作重复执行的次数作为算法的时间复杂度。它是与问题规模n相关的函数。记作T(n)=O(f(n)),例如T(n)=n(n+1),推荐一篇好文 Function):5!=5*4*3*2*1=120,特别地,0!=1取下整和取上整(Floor and Ceiling):⌊3.4⌋=3(下整) ,⌈3.4⌉=4(上整)取模操作符(Modulus):n=q*m+r ⇒m=n/q对数(Logarithm):若ab=N,那么数b叫做以a为底N的对数,记作logaN=b,其中a叫做对数的底数,N叫做真数。递归(Recursive):算法调用自己或间接调用自己。
在学习数据结构之前先要学习几个相关的概念及术语

1、数据(Data):数据是外部世界信息的载体,它能被计算机识别、存储和加工处理,是计算机程序加工的原料。

2、数据元素(Data Element)和数据项:数据元素是数据的基本单位,有时也被称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项组成;数据项是不可分割的、含有独立意义的最小数据单位,数据项有时也称为字段(Field)或域(Domain).之间关系为数据项组成数据元素,数据元素组成数据(,数据组成文件)。使用数据库模型来举例说明:

3、数据对象(Data Object):性质相同的数据元素的集合,是数据的一个子集,例如字母表对象{a,b,c,…x,y,z}

4、数据类型(Data Type):数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性;程序中每个变量、常量或表达式的结果都应该属于某种确定的数据类型。数据类型可分可两类:一类是非结构的原子类型,如C#的基本类型;另一类是结构类型,其成分由多个结构类型组成,可以分解;如C#的数组类型

。5、数据结构(Data Struct):相互之间存在一种或多种关系 的数据元素的集合。通常有4类基本数据结构:

1)集合(Set)

2)线性结构(Linear Structure)

3)树形结构(True Structure)

4)图状结构(Graphic Structure)

数据结构(Data Structrue)简记为DS,是一个二元组,DS=(D,S),其中D为数据元素的有限集合,R是数据元素之间关系的有限集合。

6、算法(Algorithm):是对某一特定类型的问题的求解步骤的一种描述,是指令的有限序列。它具有有穷性(Finity)、确定性(Unambiguousness)、输入(Input)、输出(Output)和有效性(Realizability)。针对算法优劣的评价标准包括正确性(Correctness)、可读性(Readability)、健壮性(Robustness鲁棒性)、运行时间(Running Time)和占用空间(Storage Space)。

7、算法的时间复杂度(Time Complexity):指算法的运行时间与问题规模的对应关系。通常把算法中基本操作重复执行的次数作为算法的时间复杂度。它是与问题规模n相关的函数。记作T(n)=O(f(n)),例如T(n)=n(n+1)。

常见时间复杂度举例:

1)、O(n) 

x=n;
y=0;
while(y<x){
 y=y+1;
}
 2)、O(n2) 

for(int i=1;i<n;++i){
  for(int j=0;j<n;++j){
    A[i][j]=i*j;
  }
}
 
3)、O(sqrt{n})
 
x=n;
y=0;
while(x>=(y+1)*(y+1)){//即x=y2+1
 y=y+1;
}
 
关于算法复杂度,推荐一篇好文

8、高等数学相关基础知识

计量单位(Unit):字节为B,位缩写为b,兆字节为MB,千字节缩写为KB

阶乘函数(Factorial Function):5!=5*4*3*2*1=120,特别地,0!=1

取下整和取上整(Floor and Ceiling):⌊3.4⌋=3(下整) ,⌈3.4⌉=4(上整)

取模操作符(Modulus):n=q*m+r ⇒m=n/q

对数(Logarithm):若ab=N,那么数b叫做以a为底N的对数,记作logaN=b,其中a叫做对数的底数,N叫做真数。

递归(Recursive):算法调用自己或间接调用自己。

C#数据结构系列文章:
1、基础知识
2、顺序表Sequence List
3、单链表Singly Linked List
4、双向链表Double Linked List
5、循环链表Circular Linked List
6、栈Stack
7、队列Queue
8、串
9、数组Array
10、树Tree

线程池工作原理

CLR初始化时,线程池中是没有线程的。在内部,线程池维护了一个操作请求队列。应用程序执行一个异步操作时,会将一个记录项追加到线程池的队列中。线程池的代码从这个队列中读取记录将这个记录项派发给一个线程池线程。如果线程池没有线程,就创建一个新线程。当线程池线程完成工作后,线程不会被销毁,相反线程会返回线程池,在那里进入空闲状态,等待响应另一个请求,由于线程不销毁自身,所以不再产生额外的性能损耗。

程序向线程池发送多条请求,线程池尝试只用这一个线程来服务所有请求,当请求速度超过线程池线程处理任务速度,就会创建额外线程,所以线程池不必创建大量线程。

如果停止向线程池发送任务,池中大量空闲线程将在一段时间后自己醒来终止自己以释放资源(CLR不同版本对这个事件定义不一)。

 

嵌套(组合):

 1 class Student(object):
 2     def __init__(self,name,age)
 3         self.name = name
 4         self.age = age
 5 #创建三个人
 6 obj1= Student("a",18)
 7 obj2= Student("b",20)
 8 obj3= Student("c",21)
 9 
10 class School(object):
11     def __init__(self,name,address)
12         self.name = name
13         self.address = address
14 
15 #创建三个学校
16 s1 = School("学校1","北京")
17 s2 = School("学校2","上海")
18 s3 = School("学校3","深圳")
19 
20 
21 #给每个学生分配学校
22 obj1.school = s1
23 obj2.school = s2
24 obj3.school = s3
25 
26 print(obj1.school.name)
27 print(obj2.school.name)
28 print(obj3.school.name)

 

工作者线程&I/O线程

线程池允许线程在多个CPU内核上调度任务,使多个线程能并发工作,从而高效率的使用系统资源,提升程序的吞吐性。

CLR线程池分为工作者线程与I/O线程两种:

工作者线程(workerThreads):负责管理CLR内部对象的运作,提供”运算能力“,所以通常用于计算密集(compute-bound)性操作。

I/O线程(completionPortThreads):主要用于与外部系统交换信息(如读取一个文件)和分发IOCP中的回调。

注意:线程池会预先缓存一些工作者线程因为创建新线程的代价比较昂贵。

 

IO完成端口(IOCP)

IO完成端口(IOCP、I/O completion port):IOCP是一个异步I/O的API(可以看作一个消息队列),提供了处理多个异步I/O请求的线程模型,它可以高效地将I/O事件通知给应用程序。IOCP由CLR内部维护,当异步IO请求完成时,设备驱动就会生成一个I/O请求包(IRP、I/O Request Packet),并排队(先入先出)放入完成端口。之后会由I/O线程提取完成IRP并调用之前的委托。

I/O线程&IOCP&IRP:

当执行I/O操作时(同步I/O操作 and 异步I/O操作),都会调用Windows的API方法将当前的线程从用户态转变成内核态,同时生成并初始化一个I/O请求包,请求包中包含一个文件句柄,一个偏移量和一个Byte[]数组。I/O操作向内核传递请求包,根据这个请求包,windows内核确认这个I/O操作对应的是哪个硬件设备。这些I/O操作会进入设备自己的处理队列中,该队列由这个设备的驱动程序维护。

如果是同步I/O操作,那么在硬件设备操作I/O的时候,发出I/O请求的线程由于”等待“(无人任务处理)被Windows变成睡眠状态,当硬件设备完成操作后,再唤醒这个线程。所以性能不高,如果请求数很多,那么休眠的线程数也很多,浪费大量资源。

如果是异步I/O操作(在.Net中,异步的I/O操作都是以Beginxxx形式开始,内部实现为ThreadPool.BindHandle,需要传入一个委托,该委托会随着IRP一路传递到设备的驱动程序),该方法在Windows把I/O请求包发送到设备的处理队列后就会返回。同时,CLR会分配一个可用的线程用于继续执行接下来的任务,当任务完成后,通过IOCP提醒CLR它工作已经完成,当接收到通知后将该委托再放到CLR线程池队列中由IO线程进行回调。

所以:大多数情况下,开发人员使用工作者线程,I/O线程由CLR调用(开发者并不会直接使用)。

 

TAG标签:
版权声明:本文由澳门金莎娱乐网站发布于澳门金莎唯一指定官网,转载请注明出处:数据结构,面向对象2