[读书笔记]算法导论2.1

知识点

  1. 循环不变式
    需要证明个性质:

    1. 初始化:循环的第一次迭代之前,它为真。
    2. 保持:如果循环的末次迭代之前它为真,那么下次迭代之前它仍为真
    3. 终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法的正确性。

习题

1.1

31,41,59,26,41,58
31,41,59,26,41,58
31415926,41,58
26,31,41,5941,58
26,31,41,41,5958
26,31,41,41,58,59
1.2

INSERTION-STOP(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

1-3

LINEARSEARCH-STOP(A,u)
    for i = 1 to A.length
        key = A[i]
        if key == u 
            return i
    return nil

1-4

形式化描述:对于二进制的相加,是低位数相加,为2进一位,当前位为当前位-2,进的一位参加下一位的相加。

BINARYADD-STOP(A,B)
    C[1] = 0
    for i = 1 to n
        keyc = C[i]
        keya = A[i]
        keyb = B[i]
        sum = keyc + keya + keyb
        if sum > 1 
            C[i+1] =1
            C[i] = sum - 2
        else
            C[i+1] = 0
            C[i] = sum
    return C

[读书笔记]算法导论1.2

知识点

  1. 为什么研究算法:计算时间是一种有限的资源,存储器的空间也是一种有限的资源。使用算法就是为了能最有效的利用这些资源

  2. 算法的效率为什么比硬件和软件的效率更重要:
    计算机A 每秒执行效率为百亿级别的:10^10条指令/秒,算法执行效率为2n^2,当执行一千万的时候需要20000秒
    计算机B 每秒执行效率为千万级别的:10^7条指令/秒,算法执行效率为50nlgn,当执行一千万的时候需要1163秒
    从上面可以知道,就算一台计算机的执行效率为另一台机器的一千倍时候,但算法的效率有差距的时候,在执行运算次数很多的时候,两个之间的执行时间相差将很大。

  3. 算法在系统中的用处:我们应当像计算机硬件一样吧算法当成一种技术,整个系统的性能不但依赖于快速的硬件而且还依赖于选择有效的算法。当解决较大问题规模的时候,算法之间的差距会特别的明显。

重要的一句话

是否具有算法知识与技术的坚实基础是区分真正熟练的程序员和初学者的特征。

思考题

在思考题中,lgn = t ,算出来 n = 2^t 但是nlgn却怎么也计算不出来公式推导。这个题目放置等以后回来解

[读书笔记]算法导论1.1

知识点

  1. 算法的定义:任何良定义的计算过程;输入一个值或者值的集合,输入一个值或者值的结合,这个过程可以就叫做算法;算法可以用自然语言说明,也可以说明成计算机程序,甚至说明成硬件设计。唯一的要求是这个说明必须精确的描述所要遵循的计算过程。

  2. 算法有用的定义:对每个输入都是以正确的输出来停止;这个是正确的算法。当输出的错误率是可控的情况下,有时候这种算法也是有用的。

  3. 有趣算法特性:存在许多候选解,绝大多数候选解都没有解决手头的问题;存在时机应用。

  4. 数据结构:是一种存储和组织数据的方式,旨在便于访问和修改。没有一种单一的数据结构对所有用途都有效的。

  5. 效率:一般量度是速度。

  6. 并行性:随着计算机发展,多核计算机普及。为了从多核计算机获得最佳性能,设计算法时必须考虑并行性。

[编程基础].NET中的c#stack和heap(四)

引用https://www.c-sharpcorner.com/article/C-Sharp-heaping-vs-stacking-in-net-part-iv/

本文中我们将研究垃圾收集(GC)以及保持应用程序有效运行的一些方法

标记

让我们从GC的角度来看这件事。如果我们负责“清除垃圾”,我们需要好好设计一个方案。首先,我们需要确定什么是垃圾,什么不是垃圾。
为了确定需要保留的内容,我们首先假设所有未使用的都是垃圾。想象一下,我们与两个好朋友住在一起, Joseph Ivan Thomas(JIT)和 Cindy Lorraine Richmond (CLR)。Joe和Cindy会跟踪他们在使用什么,并向我们提供他们需要保留的物品清单。我们将初始列表称为“root”列表,因为我们将其当成作用起点。我们将保留一个主列表,以图形化我们要保留的房间中所有物体的位置。使列表中的内容在正常工作时所需要的内容都添加到图表中。这也就是GC确定保留哪些内容的方式。它接受一个“Root”对象引用列表,以使其免受即时(JIT)编译器和公共语言运行时(CLR)的影响,然后递归搜索对象引用以构建应包含哪些内容的图形需要保留。
root包括:

  • 全局/静态指针。通过在静态变量中保留对对象的引用来确保它不会被垃圾回收。
  • 堆栈上的指针。我们不会想要去抛弃掉我们应用程序的线程仍然需要执行的东西。
  • CPU寄存器指针。CPU中内存地址指向的托管堆中的所有内容都应该要保留下来。

    从上图我们可以看到,从roots直接引用了我们托管堆中的object1和object5,而我们的object1引用了我们的object3,所以在递归搜索中,我们roots也引用到了object3,现在我们知道所使用到的物体后,下一步进行压缩。

    压缩

    现在我们已经标识了需要保留的物体对象,我们现在只需要移动下需要保留的对象,即可压缩空间。

    在我们的内存中,我们还不需要放置一个对象之前,我们就先清理空间,由于不需要object2,因此作为GC,我们将object3往下移动,固定在object1的附近,把object2给清理掉。

    接下来我们按照和上面一样的方式,把object5给复制下来。

    现在我们已经清理了所有的内容了,我们只需要写一个便签并将其放置在压缩堆的顶部即可让Claire知道新的对象放在哪里。

    了解GC的本质可以帮助您理解,移动对象是非常消耗的。所以我们可以减少所要移动的内容的大小,那么我们将改善下GC流程,因为复制的内容将减少。

    处理托管堆之外的东西

    作为负责垃圾收集的人,我们在打扫房间的时候遇见一个问题是如何清理掉汽车中的物体。清洁时,我们需要清洁的所有东西,如果笔记本电脑在家而电池在车里该怎么办呢?
    在某些情况下,GC需要执行代码以清理非托管资源,例如文件,数据库连接,网络连接等等。一种解决方法是通过终结器

    class Sample{
    ~Sample(){
        //
    }
    }

    在对象创建期间,所有带有终结器的对象都将添加到终结队列中,假设object1,4,5都具有终结器的话,并且位于终结队列中。让我们看看当应用程序不再引用object2和4并且做垃圾回收时候会发生什么。

    object2以通常方法处理掉,但是,当我们处理到object4的时候,GC看到它在终结队列中,然后就先不回收掉object4的所拥有的内存,而是移动object4并把它的终结器添加到名为freachable的特殊队列中。

    有一个专用线程用于执行freachable队列中的对象。一档终结器由对象4上的该线程执行了,它将从freachable队列中删除。然后只有这样,object4才能准备好被GC;

    然后,object4会在下一个GC循环中被回收掉。
    因此在我们的类中添加终结器会为GC增加工作量,这个消耗是非常昂贵的,并且会对垃圾回收的性能和程序产生不利的影响,仅在绝对确定需要终结器的时候才使用它们。
    更好的做法是确保清理非托管资源。可以想象,最好是显式关闭链接并且使用IDisposable接口进行清理,而不是尽可能的用终结器。

    IDisposable

    实现IDisposable的类再Dispose()方法(接口的唯一签名)中执行清除。因此如果我们有一个ResourceUser类而使用using来追踪finalizer,代码如下:

    public class ResourceUser{
    ~ResourceUser(){
        //
    }
    }

    我们可以用IDisposable作为实现相同功能的更好方法:

    public class ResourceUser:IDisposable{
    public void Dispose(){
        //
    }
    }

    IDisposable与using关键字集成在一起。在using块的末尾,对using()中声明的对象调用Dispose()。在using块之后不应引用该对象,因为该对象的本质上应被视为“已消失”并已准备好由GC清除。

    public static void DoSomething(){
    ResourceUser rec = new ResourceUser();
    using(rec){
        //
    }
    }

    还有一种写法是把对象放在using块中,这样从表面上看它更有意义,因为rec不在using块的范围以外可用。这种模式更符合IDisposible接口的意图

    public static void DoSomething(){
    using(ResourceUser rec = new ResourceUser()){
        //
    }
    }

    通过using()和实现IDisposible的类一起使用,我们可以执行清理操作,而不会通过强制终结对象来增加GC的额外开销。

    静态变量:当心

    class Counter{
    private static int s_Number = 0;
    public static int GetNextNumber(){
        int newNumber = s_Number;
        s_Number = newNumber + 1;
        return newNumber;
    }
    }

    如果两个线程同时调用GetNextNumber(),并且在s_Number之前都为newNumber分配了相同的值。
    则他们将返回相同的结果。word是确保一次仅一个线程可以访问代码块的一种方法。最佳的做法是:您应锁定尽可能少的代码,因为线程必须在队列中等待才能执行lock()块中的代码,并且效率低下。

    class Counter{
    private static int s_Number = 0;
    public static int GetNextNumber(){
        lock(typeof(Counter)){
            int newNumber = s_Number;
            newNumber += 1;
            s_Number = newNumber;
            return newNumber;
        }
    }
    }

    静态变量当心的第二种情况

    接下来,我们必须注意静态变量引用的对象。请记住,如何清理“roots”引用的任何内容。请看下面的例子:

    class Olympics{
    public static Collection<Runner> TryoutRunners;
    }
    class Runner{
    private string _fileName;
    private FileStream _fStream;
    public void GetStats(){
        FileInfo fInfo = new FileInfo(_fileName);
        _fStream = _fileName.OpenRead();
    }
    }

    因为Runner集合对于Olympics类是静态的,所以不仅将不释放集合中的对象让它们做垃圾回收(它们全部都是通过roots间接引用),并且您可能已经注意到,每次我们运行GetStats()时,Fileinfo都将打开文件。因为它没有关闭,也没有被GC释放,所以这段代码实际上的运行将是一场等待着发生的灾难。想象一下,我们有1000000个Runner在Olympics中。我们最终将会有许多不可收集的对象,每个对象都有一个开放的资源。

    单例模式

    保持现状不变的技巧是始终在内存中有一个使用程序类的实例。一种简单的方法就是使用GOF单例模式。应该谨慎的使用单例,因为它们确实是“全局变量”,并且在多线程应用程序中有很多让我们感到头疼和“奇怪”的行为,在这种情况下,不同的线程可能会改变对象的状态。如果我们使用单例模式(或任何全局变量),则我们应该能够证明其合理性。

    public class Earth{
    private static Earth _instance = new Earth();
    private Earth(){}
    public static Earth GetInstance(){return _instance;}
    }

    我们有一个私有的构造函数,因此只有Earth可以执行它的构造函数并制作一个Earth。我们有一个Earth的静态实例和一个获取实例的静态方法。该特定实现是线程安全的,因为CLR确保线程安全地创建静态变量。这是一种优雅的实现单例模式的方法。

    结论

    我们可以做以下的一些事情来提高GC性能:

    1. 清理。不要保留资源,确保关闭所有打开的链接,并尽快清理所有非托管对象。作为使用非托管对象的一般规则,请尽可能的延迟实例化并尽快清理。
    2. 不要过度引用。使用引用对象时候需要合理。请记住,我们的对象如果还活着,那它所引用的所有对象都不会被收集。当我们完成了类所引用的操作后,可以通过将引用设置为null来删除它。还有一个技巧是肩为使用的引用设置为自定义轻量级的NullObject,以避免获取空引用异常。启动GC时候引用到的文件越少,标记过程中的压力就越少。
    3. 使用finalizer很轻松,但是在GC时候代价却非常的大。我们只能在合理的情况下使用它们。如果我们使用IDisposible而不是finalizer,则效率是非常高的。因为可以通过一次GC就回收掉对象而不需要来两次GC。
    4. 把object和其子类放在一起。在GC上将大块内存复制到一起比较容易,而不是每次通过堆时都必须对堆进行碎片整理,因此我们声明一个由许多其他对象组成的对象时候,应该将他们尽可能的放在一起实例化。

[编程基础].NET中的c#stack和heap(三)

引用链接:https://www.c-sharpcorner.com/article/C-Sharp-heaping-vs-stacking-in-net-part-iii/

前言

在使用.NET框架的时候,我们可以不必主动担心内存管理和垃圾回收(GC),但是仍然要牢记内存管理和垃圾回收的机制,以优化应用程序的性能。另外,对内存管理的工作原理有一个基本的了解将有助于我们理解所编写程序中使用变量的行为。在这个文章中,我们将讨论堆中具有引用变量以及如何使用ICloneable修复引用变量引起的问题。

副本不是副本

为了清楚定义这个问题,我们来检查一下当堆上有一个值类型而不是堆上有一个引用类型的时候,会发生什么。首先,我们来定义一个值类型,采取一下的类和结构。我们有一个Dude类,其中包含Name元素和两个Shoe结构。我们有一个CopyDude()方法,可以轻松的制作一个新的Dudes。

public struct Shoe{
public string Color;
}
public class Dude{
public string Name;
public Shoe RightShoe;
public Shoe LeftShoe;
public Dude CopyDude(){
Dude newPerson = new Dude();
newPerson.Name = Name;
newPerson.LeftShoe = LeftShoe;
newPerson.RightShoe = RightShoe;
return newPerson;
}
public override string ToString(){
return (Name + ": Dude!,I have a"+RightShoe.Color+" shoe on my right foot , and a" + LeftShoe.Color+"on my left foot");
}
}

我们的Dude类是一个引用类型,因此shoe结构是该类的成员元素,所以它们都最终出现在堆上。

当我们执行以下方法时候:

public static void Main(){
Dude bill = new Dude();
bill.Name = "Bill";
bill.LeftShoe = new Shoe();
bill.RightShoe = new Shoe();
bill.LeftShoe.Color = Bill.RightShoe.Color = "Blue";
Dude Ted = Bill.CopyDude();
Ted.Name = "Ted";
Ted.LeftShoe.Color = Ted.RightShoe.Color = "Red";
Console.WriteLine(Bill.ToString());
Console.WriteLine(Ted.ToString());
}

输出为:
Bill:Dude!I have a Blue shoe on my right foot, and a blue on my left foot.
Ted:Dude!I have a Red shoe on my right foot, and a Red on my left foot.

如果将Shoe设置为引用类型会怎样呢?

public class Shoe{
    public string Color;
}

并且在Main()中运行完全相同的代码,看看我们的输入如何变化。
Bill:Dude!I have a Red shoe on my right foot, and a Red on my left foot.
Ted:Dude!I have a Red shoe on my right foot, and a Red on my left foot.
这显然是一个错误,但是你知道为什么会出现这样的错误吗?这就是我们最终在堆中得到的结果

因为我们使用的Shoe作为引用类型而不是值类型,并且在复制引用类型的内容时仅仅复制了指针(而不是实际对象),所以我们必须做一些额外的工作来制作Shoe引用类型的行为像值类型。
刚好我们有一个可以帮我们实现这个方案的接口:ICloneable。这个接口基本是是所有Dudes都会用到的方法,并且定义了如何复制引用类型,以避免我们的“鞋子共享”错误。我们所有需要“clone”的引用类型都应该使用ICloneable接口,包括Shoe类。
ICloneable包含一种方法:Clone()

public object Clone(){
    //
}

这是我们在Shoe类中实现它的方式:

public class Shoe:ICloneable{
    public string Color;
    public object Clone(){
        Shoe newShoe = new Shoe();
        newShoe.Color = Color.Clone() as string;
        return newShoe;
    }
}

在clone()方法内部,我们仅制作了一个新的Shoe,克隆所有引用类型并复制所有值类型,然后返回新对象。string类已经实现了ICloneable,因此我们可以调用Color.Clone()方法,由于Clone()返回对象的引用,因此在设置鞋子颜色之前,我们必须“重新赋值”引用。
接下来我们的CooyDude()方法中,我们需要克隆鞋子而不是复制它们:

public Dude CopyDude(){
    Dude newPerson = new Dude();
    newPerson.Name = Name;
    newPerson.LeftShoe = LeftShoe.Clone() as Shoe;
    newPerson.RightShoe = RightShoe.Clone() as Shoe;
    return newPerson;
}

现在,当我们运行Main时。

public static void Main(){
    Dude Bill = new Dude();
    Bill.Name = "Bill";
    Bill.LeftShoe = new Shoe();
    Bill.RightShoe = new Shoe();
    Bill.LeftShoe.Color = Bill.RightShoe.Color = "Blue";
    Dude Ted = Bill.CopyDude();
    Ted.Name = "Ted";
    Ted.LeftShoe.Color = Ted.RightShoe.Color = "Red";
    Console.WriteLine(Bill.ToString());
    Console.WriteLine(Ted.ToString());
}

打印出来:
Bill : Dude!, I have a Blue shoe on my right foot, and a Blue on my left foot
Ted : Dude!, I have a Red shoe on my right foot, and a Red on my left foot
这才是我们需要输出的内容。

总结

因此,作为常规方法,我们总是希望克隆引用类型并复制值类型。因此,本着减少额外影响的原则,我们来更进一步的清理Dude类以实现ICloneable。使用CopyDude()方法。

public class Dude:ICloneable{
    public string Name;
    public Shoe RightShoe;
    public Shoe LeftShoe;
    public override string ToString(){
        return(Name + ":Dude! I have a"+RightShoe.Color+" shoe on my right foot ,and a"+LeftShoe.Color+" on my left foot.");}
        public object Clone(){
            Dude newPerson = new Dude();
            newPerson.Name = Name.Clone() as string;
            newPerson.LeftShoe = LeftShoe.Clone() as Shoe;
            newPerson.RightShoe = RightShoe.Clone() as Shoe;
            return newPerson;
        }
}

然后我们在将Main()中的方法改成Dude.Clone()

public static void Main(){
    Dude Bill = new Dude();
    Bill.Name = "Bill";
    Bill.LeftShoe = new Shoe();
    Bill.RightShoe = new Shoe();
    Bill.LeftShoe.Color = Bill.RightShoe.Color = "Blue";
    Dude Ted = Bill.Clone() as Dude;
    Ted.Name = "Ted";
    Ted.LeftShoe.Color = Ted.RightShoe.Color = "Red";
    Console.WriteLine(Bill.ToString());
    Console.WriteLine(Ted.ToString());
}

输出如下:
Bill : Dude!, I have a Blue shoe on my right foot, and a Blue on my left foot.
Ted : Dude!, I have a Red shoe on my right foot, and a Red on my left foot.
输出的值如我们所预期的。
实际上,System.String类的赋值运算符(“=”符号)实际上就是克隆String,因此不必担心重复引用的问题,因此你必须主要到我们内存的膨胀。实际上由于字符串是引用类型,所以它实际上在图中应该指向堆中的另一个对象的指针,但是为了方便理解,我们把它显示成值类型

结论

通常我们计划复制对象,则应该实现(并使用)ICloneable这个接口,这使我们的引用类型可以在某种程度上模仿值类型的复制行为。由于值类型和引用类型分配内存的方式有所不同,因此跟踪我们要处理的变量类型非常重要。

[编程基础].NET中的c#stack和heap(二)

引用 https://www.c-sharpcorner.com/article/C-Sharp-heaping-vs-stacking-in-net-part-ii/

前言

使用.NET框架,我们不必主动考虑内存管理和垃圾回收(GC),但仍必须牢记内存管理和垃圾回收,以优化应用程序的性能。另外,对内存管理的工作原理有一个基本的了解将有助于解释我们在编写的每个程序中使用的变量的行为。在本文中,我将介绍将参数传递给方法时需要注意的一些行为。

参数,重点

这是代码执行过程中发生的情况的详细视图。在第一部分中,我们介绍了进行方法调用时发生的情况。现在让我们更详细的介绍一下。。。
当我们进行方法调用时,会发生以下的情况:

  1. 给堆栈上我们所执行的方法所需要的信息分配空间(称为堆栈框架)。这包括调用地址(指针),该地址基本上是GOTO指令,因此当线程完成运行我们的方法时,它知道要返回到哪里才能继续执行。
  2. 我们的方法参数被复制。这是我们需要更仔细研究的地方。
  3. 控制权传递给JIT'ted方法,线程开始执行代码,因此,我们有另外一种犯法,由“调用堆栈”上的堆栈帧表示。
public int AddFive(int pValue){
    int result;
    result = pValue + 5;
    return result;
}

使用的堆栈如下图所示

注意:这个方法不存在与堆栈中,在这里只作为参考来说明堆栈框架的开始。
和第一部分讨论的那样,根据参数的类型是引用类型还是值类型,对堆栈上的参数的处理方式将有所不同。值类型将被整体复制,引用类型将被复制引用。

传递值类型

这是传递值类型
首先,当我们传递值类型时,将分配空间,并将类型中的值复制到堆栈上的新空间。
示例代码:

class Class1
{
    public void Go(){
        int x = 5;
        AddFive(x);
        Console.WriteLine(x.ToString());
    }
    public int AddFive(int pValue){
        pValue += 5;
        return pValue;
    }
}

执行该方法时,将“x”的空间放置在堆栈上,其值为5。

接下来,将AddFive()放置在堆栈上,并为其参数留出空间,并从x逐位复制值。

当AddFive()完成执行后,线程将被传递回Go(),并且由于AddFive()已经完成,因此pValue本质上是已经被抛弃了的数据:

因此,我们的代码输出的值为“5”,其中的关键点是:传递给方法的任何值类型参数都是复本,我们依靠原始变量的值来拷贝。
要记住的一件事:如果我们传递一个非常大的值类型(列如一个非常大的结构)并将其传递给堆栈,则每次复制它的空间和处理周期都会非常消耗。堆栈没有无限的空间,就像往一个杯子里一直倒水,最后它就可能会溢出。struct是一个可以变得非常大的值类型,我们必须了解我们如何处理它。
这是一个很大的结构:

public struct MyStruct{
    long a,b,c,d,e,f,g,h,i,j,k,l,m;
}

看一下我们执行Go()并转到下面的DoSomething()方法时会发生什么:

public void Go(){
    MyStruct x = new MyStruct();
    DoSomething(x);
}
public void DoSomeThing(MyStruct pValue){
    //
}


这就能看到低效的地方了。想想一下,如果我们通过MyStruct数千次,你就可以知道它是怎么拖累你程序的效率了。
那我们改怎么改善上述问题呢?可以通过传递对原始值类型的引用,如下所示:

public void Go(){
    MyStruct x = new MyStruct();
    DoSomething(ref x);
}
public struct MyStruct{
    long a,b,c,d,e,f,g,h,i,j,k,l,m;
}
public void DoSomething(ref MyStruct pValue){
    //
}

这样,我们最终可以在内存中更加有效的分配对象。

通过引用传递值类型时,我们唯一需要注意的是,我们对值类型的值的访问。
pValue中的任何更改都将x中的值进行了修改。使用下面的示例代码

public void Go(){
    MyStruct x = new MyStruct();
    x.a = 5;
    DoSomething(ref x);
    Console.WriteLine(x.a.ToString());
}
public void DoSomething(ref MyStruct pValue){
    pValue.a = 12345;
}

上述代码的打印值为“12345”,因为pValue.a实际上使用的是原始数据x变量里的内存空间。

传递引用类型

作为引用类型的传递参数类似于在上一个示例中通过引用传递值类型。
如果我们需要使用值类型

public class MyInt{
    public int MyValue;
}

并且调用Go()方法,因为MyInt是引用类型,所以它会出现在堆上。

如果按照以下代码来执行Go()

public void Go(){
    MyInt x = new MyInt();
    x.MyValue = 2;
    DoSomething(x);
    Console.WriteLine(x.MyValue.ToString());
}
public void DoSomething(MyInt pValue){
    pValue.MyValue = 12345;
}

这个时候发生了以下的事情。

  1. 从对Go()的调用开始,变量x进入堆栈。
  2. 从对DoSomething()的调用开始,参数pValue进入堆栈。
  3. x的值(堆栈上MyInt的地址)被复制到pValue

因此,当我们使用pValue更改堆中MyInt对象的MyValue属性并稍后使用x引用堆上对象时,我们得到的值是“12345”。
所以有一个有趣的地方,当我们通过引用传递引用类型的时候会发生什么呢?
看看这个。如果我们有Thing类,Animal和Vegetable继承自它

public class Thing{

}
public class Animal:Thing{
    public int Weight;
}
public class Vegetable:Thing{
    public int Length;
}

然后再执行下面Go()方法:

public void Go(){
    Thing x = new Animal();
    Switcharoo(ref x);
    Console.WriteLine("x is Animal : "+(x is Animal).ToString());
    Console.WriteLine("x is Vegetable : "+(x is Vegetable).ToString());
}
public void Switcharoo(ref Thing pValue){
    pValue = new Vegetable();
}

我们的x就变成的Vegetable。
如果不加ref那x还是Animal
让我们看看发生了什么;

  1. 从Go()方法调用开始,x指针进入堆栈
  2. Animal对象在堆上
  3. 对Switcharoo方法调用开始,pValue进入堆栈并指向x

  1. Vegetable在堆上
  2. x的值通过pValue更改为Vegetable的地址。

如果不通过ref传递Thing,则保留对Animal引用的并从代码获得相反的结果。

[编程基础].NET中的c#stack和heap(一)

引用

https://www.c-sharpcorner.com/article/C-Sharp-heaping-vs-stacking-in-net-part-i/

前言

这段时间在巩固c#基础的时候,发现有些基础性的东西在以前是没有仔细去想过的,比如值类型,和引用类型的区分,究竟值类型保存在哪里,引用类型保存在哪里,两个究竟是啥区别。在说到这个问题的时候,我们需要巩固一下堆和堆栈的信息。这个知识点在前面讲GC的时候有带过一点,但是没有详细去了解过,所以现在开始做一次总结。

Stack 和 Heap 有什么区别

堆栈(stack)一般来负责跟踪代码中正在执行的内容(即所谓的“调用”)。而堆(Heap)一般来说负责跟踪我们的对象。
可以将堆栈想想成一系列盒子堆叠在一起。每次调用方法的时候,都是从顶部叠放一个盒子,从而跟踪应用程序中发生的事情。我们只能使用堆栈顶部盒子里面的内容。当我们完成顶部盒子里的后,我们就把这个盒子给丢掉并继续使用推上来的顶部盒子里的内容。堆是类似的,它的主要用途是保存信息,以便可以随时随地的访问堆中的任何内容。和堆栈相比堆没有任何访问限制
堆栈是自我维护的,这就意味着我们可以不用去管理它的内存情况,顶部的数据不再使用就丢弃掉。堆就必须去考虑垃圾回收的情况(GC)。

以上图片并不是内存中真实的表现形式,但是能够帮助我们区分堆栈和堆。

堆栈和堆上发生了什么

我们将在执行代码时将四种主要类型的东西放入堆栈和堆中:值类型,引用类型,指针和指令。

值类型

在c#中,使用以下类型声明列表表明的所有“事物”均为值类型(因为它们来自System.ValueType):

  • bool
  • byte
  • char
  • decimal
  • double
  • enum
  • float
  • int
  • long
  • sbyte
  • short
  • stuct
  • uint
  • ulong
  • ushort

    引用类型

    所有被声明为以下类型的事物都被称为引用类型:

  • class
  • interface
  • delegate
  • object
  • string

    指针

    放在内存管理方案“事件”的第三种类型是对类型的引用。引用通常被称为指针。在c#中尽量不要明确使用指针,他们是由公共语言运行时(CLR)管理的。指针(或引用)与引用类型的不同之处在于,当我们说某个对象是引用类型时,意味着我们能够通过指针访问它。指针是内存中的一大块空间,指向内存中的另一个空间。指针占用的空间与我们放入堆栈和堆中的其他任何东西一样。其值可以是内存地址或null。

    指针是可以在堆栈中也可以在堆中的。

    如何决定是放在哪里的

    这是我们的两个黄金法则:

    1. 引用类型总放在堆上。
    2. 值类型和指针总是放在声明它们的地方。
      正如我们前面提到的,堆栈(stack)负责跟踪代码执行过程中每个线程的位置。您可以将其视为线程“状态”,并且每个线程都有自己的堆栈。当我们的代码调用执行一个方法时,线程开始执行经过JIT编译并存放在于方法表中的指令,它还将方法的参数放在线程堆栈中。然后当我们遍历代码并在方法中遇到变量时,将它们放置在堆栈的顶部。

      public int AddFive(int pValue){
      int result;
      result = pValue + 5;
      return result;
      }

      这是堆栈顶部的情况。在查看的内容已经位于堆栈的的其他项目之上了。
      一旦执行executin ghte方法,该方法的参数将被放置在堆栈上。
      注意
      该方法不存在与堆栈中,仅作参考说明

      首先入栈的是方法体,然后入栈我们方法的参数。
      将控制(执行该方法的线程)传递给位于我们类型方法表中的AddFive()方法的指令,如果这是我们第一次点击该方法,将执行JIT编译

      该方法执行时,我们使用一些内存来存储“结果”变量,并将其分配在堆栈上。

      该方法完成执行并返回我们的结果。

      通过将指针移到AddFive()开始的可用内存地址来清理堆栈上分配的所有内存,然后我们转到堆栈上的上一个方法。

      在此实例中,我们的“结果”变量被放置在堆栈上。事实上,每次在方法主体中声明值类型时,它将被放置在堆栈中。
      现在,值类型有时也放置在堆上。在规则中:值类型总是去声明它们的地方。所以,如果在方法外部但是在引用类型内部声明了值类型,那么将其放置在堆的引用类型内。
      现在来看另一个例子:
      如果我们定义以下的MyInt类:

      public class MyInt{
      public int MyValue;
      }

      并且正在执行以下方法:

      public MyInt AddFive(int pValue){
      MyInt result = new MyInt();
      result.MyValue = pValue + 5;
      return result;
      }

      与之前一样,线程开始执行该方法,并且其参数被放置在该线程的堆栈中。

      现在开始变得有趣了。
      由于MyInt是引用类型,因此将其放置在堆上,并且由堆栈上的指针引用。

      在AddFive()完成执行之后,我们正在清理

      我们在堆中只剩下一个孤零零的MyInt(堆栈中不再有任何人指向MyInt)

      这个时候就是垃圾回收集(GC)发挥作用的地方。一单程序达到一定内存阈值并且需要更多的堆空间时候,便会启动GC。GC将停止所有正在运行的线程(FULL STOP),在堆中找到主程序未访问的所有对象并将其删除。然后,GC将压缩堆中剩余的所有对象以腾出空间,并调整指针指向堆栈和堆中的这些对象。可以想象,这在性能方面可能是非常昂贵的。因此现在您可以了解为什么在尝试编写高性能代码时,注意堆栈和堆中内容是很重要。
      那这是怎么影响我的呢?
      当使用引用类型时,我们要处理类型的指针,而不是该类型本身。当我们使用值类型时,我们使用的是值类型本身。这是不是十分明确呢?
      那我们看下实例代码
      如果我们执行以下方法:

      public int ReturnValue(){
      int x = new int();
      x = 3;
      int y = new int();
      y = x;
      y = 4;
      return x;
      }

      这上面返回的值是3,这个很简单对吧。
      但是我们如果使用的是MyInt类:

      public class MyInt{
      public int MyValue;
      }

      并且我们正在执行以下方法:

      public int ReturnValue2(){
      MyInt x = new MyInt();
      x.MyValue = 3;
      MyInt y = new MyInt();
      y = x;
      y.MyValue = 4;
      return x.MyValue;
      }

      现在我们得到的返回值是几呢:是4。
      可能有人想不通为啥这个值是4
      我们先来先第一个例子中的内存图

      后面我们看下第二个例子的内存图,因为x,y都是指向堆中的同一个对象,所以我们就没办法获得3

      希望以上内容能使您更好的了解c#中“值类型”和“引用类型”变量之间的基本区别,以及对什么是指针以及何时使用它的基本理解。

[编程基础]闭包

前言

在一个机缘巧合之下,了解到了闭包概念,当时对里面的实现感觉没有头绪,所以就暂时放过不去研究了。前段时间看到一本《代码的未来》里面系统性的介绍了一下闭包概念,感觉自己找到点头绪,然后就开始仔细研究一波。

闭包所需要的知识点

  • 函数对象
  • 作用域
  • 生存周期

函数对象

所谓的函数对象:就是作为对象来使用的函数,在c#中为委托(delegate),这里的对象不是面向对象中的那个对象,而是编程语言中的数据对象。

delegate void dhello();
void hello (){
    Console.WriteLine("Hello");
}
dhello d = hello;
d();

上述代码为简单的定义一个委托,然后给委托对象赋值一个函数,然后执行这个对象。在delegate的定义中签名必须和被委托的方法的签名一致,形参也必须得一致。就可以直接调用该方法,或者把它当成参数传递给另一个方法调用。在.NET Framework 2.0引入了匿名委托

delegate void dhello();
dhello d = delegate{
    Console.WriteLine("Hellp");
}
d();

在这里委托正文就是一直表达式,可以不用定义方法名。这样叫做创建的“内联”委托,无需指定任何其他类型或者方法,只需在所需位置内联委托定义就好。
在c# 3.0版本中,我们对上述代码还能在简易点,我们引入lambda表达式来实现上述功能

delegate void dhello();
dhello d = ()=>{
    Console.WriteLine("Hello");
}
d();

这个只是使用委托的更方便的语法。它们将声明签名和方法正文,但在分配到委托之前没有自己的正式标识。与委托不同,可将其作为事件注册的左侧内容或在各种LINQ子句和方法中直接分配。

高阶函数

函数对象最大的用途就是高阶函数。所谓的高阶函数,就是用函数作为参数的函数。

delegate void hello();
delegate void hello1(hello h);
void hello2 (hello h){
h()
}
hello1 h1 = hello2;
hl(()=>{Console.WriteLine("Hello");});

通过将一部分处理以函数对象的形式转移到外部,从而实现了算法的通用性。

函数指针的局限

函数指针的方法体是不能访问外部的局部变量的,如果把这个变量变成全局的是可以的,但是只是为了能访问到而变成一个全局变量是不划算的。

作用域

作用域是指变量的有效范围,也就是某个变量可以被访问的范围。作用域是嵌套的,因此位于内侧的代码块可以访问以其自身为作用域的变量,以及以外侧代码块为作用域的变量。

delegate void hello2(int n);
delegate void hello3(List<int> l, hello2 h2);
void foreached(List<int> list1, hello2 h2)
{
   int i = 0;
   while (i < list1.Count)
   {
      h2(list1[i]);
      i++;
    }
}
 List<int> a1 = new List<int>() { 1, 2, 3, 4, 5 };
 int i = 0;
 hello3 h3 = foreached;
 h3(a1, (int c) => { Console.WriteLine("index" + i + "=" + c);i++; });

在函数对象中能对外部变量i进行访问(引用,更新),这就是闭包的构成要件之一。
按照作用域的思路,可能大家觉得上述闭包性质也是理所当然的。但是我们如果加入另外一个概念-生存周期,结果可能就会出乎意料了。

生存周期

所谓的生存周期,就是变量的寿命。相对于表示程序中变量可见范围的作用域来说,生存周期这个概念指的是一个变量可以在多长的周期范围内存在并被能够被访问。

delegate void hello();
 hello extent()
            {
                int n = 0;
                return () => { n++; Console.WriteLine("n=" + n); };
            }
 hello h = extent();
                h();
                h();
输出:n = 1
      n = 2

这个函数变量在每次执行的时候,局部变量n都会被更新,从而输出逐次累加的的结果。按道理n是在extent函数中声明的,函数都已经执行完毕了。变量脱离了作用域之后不应该就消失吗?从这个结果来看,这个变量在函数执行完毕以后没有消失,还在某一个地方继续存活下来的。
这就是生命周期。也就是说,这个从属于外部作用域的局部变量,被函数对象给“封闭”在里面了。
闭包这个词原本就是封闭的意思。被封闭起来的变量的寿命,与封闭它的函数对象寿命相等。也就是说,当封闭这个变量的函数对象不再被访问,被垃圾回收器回收的以后,这个变量的寿命也就同时终结了。
在函数对象中,将局部变量这一环境封闭起来的结构被称为闭包。

[编程基础]c#托管资源和非托管资源

前言

GC(垃圾回收)实现的时候,对引用资源管理都是对托管资源的管理,而在c#中还有一些非托管资源,现在简单讲下,两者的区别,和对非托管资源是怎么释放内存的。

托管资源

.NET中的类型都是从System.Object类型派生出来的。
分为两大类:
引用类型(reference type),分配在内存堆上。
值类型(value type),分配在堆栈上。

分配内存

值类型在栈里,先进后出,值类型变量的生命有先有后,这个确保了值类型变量在退出作用域以前会释放资源。比引用类型更简单和高效。堆栈是从高地址往低地址分配内存。
引用类型分配在托管堆上,声明一个变量在栈上保存,当实例化一个对象的时候,会把对象的地址存储在这个变量里。托管堆相反,从低地址往高地址分配内存。
初始化新进程的时候,CLR会为进程保留一个连续的地址空间区域。这个保留的地址空间被称为托管堆。托管堆维护着一个指针,用它指向将在堆中分配的下一个对象的地址。一开始该指针指向托管堆的基址。托管堆上包含了所有的引用类型。从托管堆中分配内存要比非托管内存分配速度快。由于CLR通过为指针添加值来为对象分配内存,所以这几乎和从堆栈中分配内存一样快。另外由于连续分配的新对象在托管堆中是连续存储,所以应用程序可以快速访问这些对象。

释放内存

这个就是GC所做的事情了,参考c#GC。

非托管资源

应用使用完非托管资源后,必须要显式释放这些资源。最常见的非托管资源类型是包装操作系统资源的对象。虽然垃圾回收器可以跟踪封装非托管资源的对象的生存期,但是无法了解如何发布并清理这些非托管资源。所以清理需要做以下操作:

  • 实现清理模式:需要提供IDisposable.Dispose实现以启用非托管资源的确定性释放。当不再需要此对象时,类型使用者可以调用Dispose。Dispose方法立即释放非托管资源。

  • 在类型使用者忘记调用Dispose的情况下,准备释放非托管资源。有两种方法可实现此目的:

    • 使用安全句柄包装非托管资源。安全句柄派生自System.Runtime.InteropServices.SafeHandle类并包含可靠的Finalize方法。在使用安全句柄时,只需要实现IDisposable接口并在Dispose实现中调用安全句柄的IDisposable.Dispose方法。如果未调用安全句柄Dispose方法,则垃圾回收器将自动调用安全句柄的终结器。
    • 重写Object.Finalize方法。当类型使用者无法调用IDisposable.Dispose以确定性地释放非托管资源时,终止会启动对非托管资源的非确定性释放。

然后,类型使用者可直接调用IDisposable.Dispose实现以释放非托管资源使用的内存。在正确实现Dispose方法时,安全句柄的Finalize方法或Object.Finalize方法的重写会在未调用Dispose方法的情况下阻止清理资源。

[编程基础]c#GC简介

GC的前世今生

GC的概念并非才诞生不久,早在1958年,由大名鼎鼎的图灵奖得主john mccarthy所实现的lisp语言就已经提供了GC的功能,这是GC的第一次出现。lisp的程序员认为内存管理太重要的,所以不能由程序员自己来管理。
但是后来的日子里lisp却没有成气候,采用内存手动管理的语言占据了上风,以c为代表。出于同样的理由,不同的人却又不同的看法,c程序员也认为内存管理太重要的,所以不能由系统来管理,并且讥笑lisp程序慢如乌龟的运行速度。的确,在那个对每一个byte都要精心计算的年代GC的速度和对系统资源的大量占用使很多人都无法接受。而后,1984年由dave ungar开发的smalltalk语言第一次采用了Generational garbage collection的技术,但是amalltalk也没有得到十分广泛的应用。
直到20世纪90年代中期GC才以主角的身份登上历史的舞台,这不得不归功于Java的进步,今日的GC已非吴下阿蒙。Java采用VM(virtual machine)机制,由VM来管理程序的运行当然也包括对GC管理。90年代末期.net出现了,.net采用了和Java类似由CLR(Common Language Runtime)来管理。这两大阵营的出现将人们引入了以虚拟平台为基础的开发时代,GC也在这个时候越来越得到大众的关注。
为什么要使用GC呢?也可以说为什么要使用内存自动管理?有以下一个原因:
1. 提高了软件开发的抽象度;
2. 程序员可以将精力集中在实际的问题上而不用分心来管理内存的问题;
3. 可以使用模块的接口更加的清晰,减少模块间的耦合;
4. 大大减少了内存人为管理不当所带来的bug;
5. 使内存管理更加高效。
总的来说就是GC可以使程序员可以从复杂的内存问题中摆脱出来,从而提高了软件开发的速度,质量和安全性。

什么是GC

GC就是垃圾收集,这里仅就内存而言。Garbage Collector以应用程序的root为基础,遍历应用程序在Heap上动态分配的所有对象,通过识别它们是否被引用来确定哪些对象是已经死亡的,哪些仍然需要被使用。已经不再被引用程序root引用或者别的对象所引用的对象就是已经死亡的对象,即所谓的垃圾,需要被回收。

1,Mark-Compact 标记压缩算法

简单的吧.NET的GC算法看作Mark-Compact算法。阶段1:Mark—Sweep 标记清除阶段,先假设heap中所有对象都可以回收,然后找出不能回收的对象,给这些对象打上标记,最后heap中没有打标记的对象都是可以被回收的;阶段2:Compact 压缩阶段,对象回收之后heap内存空间变得不连续,在heap中移动这些对象,使它们重新从heap基地址开始连续排列,提高局部性。
<a href="https://i.loli.net/2019/10/08/TLm9Uy5Kaq2frvF.png"><img src="https://i.loli.net/2019/10/08/TLm9Uy5Kaq2frvF.png" alt="" /></a>
Heap内存经过回收,压缩之后,可以继续采用前面的heap内存分配方法,即仅用一个指针记录heap分配的起始地址就可以。主要处理步骤:将线程挂起->确定roots->创建reachable objects graph->对象回收->heap压缩->指针修复。可以这样理解roots:heap中对象的引用关系错综复杂(交叉引用,循环引用),形成复杂的graph,roots是CLR在heap之外可以找到的各种入口。
GC搜索roots的地方包括全局对象,静态变量,局部对象,函数调用参数,当前CPU寄存器中的对象指针等。主要可以归为两类:已经初始化了的静态变量,线程仍在使用的对象。Reachable objects:指根据对象引用关系,从roots出发可以到达的对象。从roots出发可以创建reachable objects graph,剩余对象即为unreachable,可以被回收。
发现无法访问的对象时,它就使用内存复制功能来压缩内存中可以访问的对象,释放分配给不可访问对象的地址空间块。
指针修复是因为compact过程中移动了heap对象,对象地址发生变化,需要修复所有引用指针,包括stack,cpu register中的指针以及heap中其他对象的引用指针。传给COM+的托管对象也会成为root,并且具有一个引用计数以兼容COM+的内存管理机制,引用计数为0时,这些对象才可能成为被回收对象。Pinned objects指分配之后不能移动的对象,GC在指针修复时无法修改非托管代码中的引用指针。pinned objects会导致heap出现碎片。

2,托管堆

在垃圾回收器由CLR初始化以后,它会分配一段内存用于存储和管理对象。此内存为托管堆。
每个托管进程都有一个托管堆,进程中的所有线程都在同一个托管堆上为对象分配内存。
堆上分配的对象越小,垃圾回收器必须执行的工作就越少。分配对象时,请勿使用超出你需求的舍入值。
当触发垃圾回收时,垃圾回收器将回收由死对象占用的内存。回收进程会对活动对象进行压缩,以便将它们一起移动,并移除死空间,从而使堆更小一些。这将确保一起分配的对象都位于托管堆上,从而保留它们的局部性。
GC分配两个托管堆:一个用于小型对象(小型对象堆或SOH),一个用于大型对象(大型对象堆或LOH)
对象小于85000字节分配到小型SOH上,大于则分配到LOH上。
触发垃圾回收后,GC将寻找存在的对象并将它们压缩。但是由于压缩成本很高,GC会扫过LOH,列出没有被清除的对象列表以供以后重新使用,从而满足大型对象的分配请求。相邻的被清除对象将组成一个自由对象。

3,代数

虽然对象的生命周期因应用而异,但对于大多数应用来说,大部分的对象在创建不久即变成垃圾。因此针对不同age的对象也就不难理解了。
在.NET垃圾回收器中分三代,0,1,2。
小对象始终在第0代中进行分配,或者根据它们的生存期,可能会提升为第一代或者第二代。
大型对象始终在第二代中分配。
回收一代时,同时也会回收它前面所有代。
用户代码分配只能在SOH中的第0代或LOH中分配。只有GC可以在第一代和第二代中分配对象。
在mono中为写屏障来记录老代对新代的引用。

4,Finalization Queue和Freachable Queue

这两个队列和.NET对象所提供的Finalize方法有关。这两个队列并不用于存储真正的对象。而是存储一组指向对象的指针。当程序中使用new操作符在Managed Heap上分配空间时,GC会对其进行分析,如果该对象含有Finalize方法则在Finalization Queue中添加一个指向该对象的指针。
在GC被启动以后,经过Mark阶段分辨出哪些是垃圾。再在垃圾中搜索,如果发现垃圾中有被Finalization Queue中的指针所指向的对象。则把这个对象从垃圾中分离出来,并将指向它的指针移动到Freachable Queue中。这个过程被称为对象的复生(Resurrecction)。那为什么要救活它呢?因为这个对象的Finalize方法还没有被执行,所以还不能死去。当Freachable Queue中的指针指向的对象执行完Finalize方法以后,这个指针就会从队列中剔除,这个对象就能在下一次GC中被回收了。
.NET Framework的System.GC类提供了控制Finalize的两个方法,ReRegisterForFinalize和SuppressFinalize。前者是请求系统完成对象的Finalize方法,后者是请求系统不要完成对象的Finalize方法。ReRegisterForFinalize方法其实就是将指向对抗的指针重新添加到Finalization Queue中。如果在对象的Finalize方法中调用ReRegisterForFinzlize方法,这样就会形成一个在堆上永远不会死去的对象。

5,弱引用

如果应用程序代码访问一个正由该程序使用的对象时,垃圾回收器就不能回收该对象,那么就认为这个应用程序对该对象有强引用。
弱引用允许应用程序访问对象,同时也允许垃圾回收器收集相应的对象。如果不存在强引用,则弱引用的作用时间只限于收集对象前的一个不确定时间段。使用弱引用时,应用程序仍可以对该对象进行强引用,这样做可防止该对象被收集。但始终存在这样的风险:垃圾回收器在重新建立强引用之前先处理改对象。
若要对某对象建立弱引用,请使用要跟踪的对象实例创建WeakRefernce。然后将Target属性设置为该对象,将该对象的原始引用设置为null。

 aa a = new aa();
            a.a = 2;
            WeakReference c = new WeakReference(a);
            a = null;
            GC.Collect();
            Console.WriteLine(c.Target != null);
            Console.WriteLine(c.IsAlive);
            Console.WriteLine(c.Target);
/*
延时执行if判断的时候,c.Target是为null的
 var t1 = Task.Run(async delegate { await Task.Delay(5000); if (c.IsAlive)
                {
                }
            });
*/
/*
这段代码如果执行的话,在上一个GC期间c.Target是不为Null的,但是如果不执行的话,c.Target是null
  if (c.IsAlive)
                {
            }
*/
            GC.Collect();
/*
在GC调用完以后c.target为null。
*/
          Console.WriteLine(c.IsAlive);
            Console.ReadKey();

WeakRefernce也是一个引用对象,当这个对象也在被引用的时候,期内部的target是不会被回收的。

短弱引用和长弱引用

  • 短弱引用:
    垃圾回收功能回收对象后,短弱引用的目标将会变成null。弱引用本身是托管对象,与其他任何托管对象一样需要经过垃圾回收。
  • 长弱引用:
    在对象的Finalize方法已调用后,长弱引用获得保留。这样,便可以重新创建该对象,但该对象仍保持不可预知的状态,仍然可能在下一次的GC中被回收掉。若要使用长弱引用,请在WeakReference构造函数中指定true。
    如果对象类型不包含Finalize方法,或者Finalize方法没有被执行(调用了GC.SuppressFinalize();),那么将被应用为短弱引用。弱引用只在目标被收集前有效,运行终结器后可以随时收集目标。
    如果要建立强引用并重新使用对象,请将WeakReference的Target属性强行转换为对象类型。使用前请先判断Target是否为null。