工具 --- IL指令集解释

## 引言

先不论什么是闭包，什么是闭包陷阱，我们开篇先看一段代码：

```csharp
static void Main(string[] args)
{
    List<Action> lists = new List<Action>();

    for (int i = 0; i < 5; i++)
    {
        Action action = () => { Console.WriteLine(i); };

        lists.Add(action);
    }

    foreach (var action in lists)
    {
        action();
    }

    Console.ReadLine();
}
```
那么思考一下，控制台输出是什么？



## 闭包陷阱

上述代码的本意是想让 `Action`声明的匿名委托方法接收 `i` 的值，并输出

```csharp
0
1
2
3
4
```
但实际上，上述代码输出的是

```csharp
5
5
5
5
5
```
为什么会这样？就需要提到两个个概念，**变量作用域**和**闭包**。

**变量作用域就不说了，就是指变量可以被访问的范围。例如全局变量，局部变量等**。

**闭包：简单点说，就是函数和其引用的上下文的组合体，就是一个闭包。**，例如上文代码中，`for` 循环内部，匿名方法内引用了变量 `i` ，那么变量 `i` 和匿名方法 `() => { Console.WriteLine(i); }` 就组合成了一个闭包，在 `for` 循环中，变量 `i` 就是一个局部变量，但是在闭包中，变量 `i` 对于匿名方法来说就是全局变量。相当于这样：

```csharp
int i;

public void AnonymousMethod()
{
    Console.WriteLine(i);
}
```
所以，当 `for` 循环结束时，在闭包内的全局变量 `i` 的值就已经变成了5。则下面 `foreach` 代码每次执行输出均为5。

## 根据IL探究原理

实际上，编译器在执行的时候，也确实为闭包生成了一个类，这个类只包含了一个方法和一个全局变量。

来验证一下，将上述代码编译为dll后，通过ILDasm.exe工具查看生成的IL代码

![image.png](https://niuery.com/static/img/8b51e449c9ac390de9f60a9f9349e796.image.png)

可以看到IL为闭包生成了一个类 `<>c_DisplayClass0_0` ,这个类只包含了一个变量 `i`，如下：

![image.png](https://niuery.com/static/img/a4254f46e6e9af97aeac5968dc052107.image.png)

还包含了一个匿名方法`<Main>b_0:void`，从IL中，也可以看出，先取 `<>c_DisplayClass0_0` 的变量 `i` ，再调用控制台输出方法。如下：

![image.png](https://niuery.com/static/img/8fb799edead362055a7e26b6139deed3.image.png)

接下来，在看一下整个控制台程序 `Main` 方法的IL代码：

![image.png](https://niuery.com/static/img/b8db9ab5aa10eaf5a6a6f59be4e8415a.image.png)

在IL_0007行，可以看到，声明创建一个 `Action` 后就紧接着创建了一个 `<>c_DisplayClass0_0` 对象。且 `for` 循环的变量 `i` 就是 `<>c_DisplayClass0_0` 对象的变量 `i` （注意这里指的是引用，并不是值），这样，在循环结束的时候，对象的变量 `i` 就变成了5。

这样就可以解释为什么输出会是5了。

:::info{title="相关信息"}
需要注意的是，`Action action = () => { Console.WriteLine(i); };`这句代码只是声明了一个委托，委托绑定的是一个匿名方法，并没有真正执行，只有调用该委托的时候才真正执行。比如 `action()` 或 `action.Invoke()`。
:::

## 如何避免闭包陷阱

在上面的探究原理的过程中，其实也发现了追根究底的问题其实就是，在创建闭包对象的时候，引用的局部变量，在外部被修改（比如上面代码中的`for` 循环的变量 `i` 就是闭包对象的变量 `i`，指的是指针是同一个），那么可以在创建闭包对象的时候，重新创建一个指针对象，将预期值赋值给它就可以了，比如上面的示例代码可以这样修改：

```csharp
static void Main(string[] args)
{
    List<Action> lists = new List<Action>();

    for (int i = 0; i < 5; i++)
    {
        int temp = i;
        Action action = () => { Console.WriteLine(temp); };
        lists.Add(action);
    }

    foreach (var action in lists)
    {
        action();
    }

    Console.ReadLine();
}

```
这样，闭包对象的变量就不再是 `for` 循环的 `i` 了，也就不会再被修改。输出结果为：

```csharp
0
1
2
3
4
```

编码技巧 --- 谨防闭包陷阱

## 引言

**dynamic** 是 `Framework 4.0` 就出现特性，它的出现让 C# 具有了弱语言类型的特性。编译器在编译的时候不再对类型进行检查，默认 **dynamic** 对象支持开发者想要的任何特性。



## dynamic 介绍

在C#中，dynamic是一种类型，它允许你在运行时动态地确定对象的类型。

使用dynamic类型可以使代码更加灵活，因为不需要在编译时知道对象的确切类型，而可以在运行时根据需要确定类型。

### 确保dynamic对象调用有效

但是正因为你不知道对象的确切类型，所以在编码时一定要注意，确保对象的类型和属性和方法的存在，否则代码可能会引发运行时异常。

比如以下代码：

```csharp
static void Main(string[] args)
{
    dynamic dynamicObject = new Person();
    
    var attr1 = dynamicObject.Name;
    
    var attr2 = dynamicObject.GetAge();

    Console.ReadLine();
}


public class Person
{
    public string Gender { get; set; }
    
    public string Name { get; set; }
    
    public int MakeMoney()
    {
        return 200;
    }
}
```

上述在编译时是不会报错的，但是在运行时，执行第二句是没问题的，因为得到的 `dynamicObject` 对象是有 `Name` ，`Gender` 两个属性的，但是执行第三句时就会抛出异常 `Microsoft.CSharp.RuntimeBinder.RuntimeBinderException` ，并提示 `does not contain a definition for 'GetAge'`。

### dynamic 与 var

有时候会将 `var` 关键字与 `dynamic` 进行对比，那么我觉得主要有以下几点：
1.  `var` 用于在编译时推断变量类型，可以将其视为一种简写方式，将变量类型的声明推迟到编译时。而 `dynamic` 则是一种在运行时动态确定对象类型的类型。它允许您在运行时调用对象的属性和方法，而不需要在编译时确定对象的确切类型。
2.  `var`声明的变量在Visual Studio编译器中能够使用IntelliCode进行“智能提示”，因为Visual Studio编译器在此阶段是可以推断出其实际类型，而`dynamic` 类型的变量不可以进行”智能提示“。
3.  `var` 类型的变量可以使代码更加简洁和易于阅读，而使用 `dynamic` 类型的变量则可以使代码更加灵活和动态。 

## 使用 dynamic 简化反射

常规使用反射，调用上文中 `Person` 类 `MakeMoney()`方法，如下：

```csharp
Person person = new Person();

var method = typeof(Person).GetMethod("MakeMoney");

int moneys = (int)method.Invoke(person, null);
```
那如果使用 **dynamic** 进行简化，则像这样：

```csharp
dynamic person = new Person();

int moneys = person.MakeMoney();
```
这样使用 **dynamic** 后，代码更简洁，而且也减少了一次拆箱操作。

[基准测试工具 --- BenchmarkDotNet](https://niuery.com/post/58)这篇文章中，介绍了使用 **BenchmarkDotNet** 来测试性能，接下来依然使用 **BenchmarkDotNet** 来测试以下，测试一下执行100000次，上述两种方式的区别：

```csharp
static void Main(string[] args)
{
    BenchmarkRunner.Run<BenchmarkTest>();
}

[SimpleJob(RunStrategy.ColdStart, iterationCount: 100000)]
[MemoryDiagnoser]
public class BenchmarkTest
{
    [Benchmark()]
    public int UseReflection()
    {
        Person person = new Person();

        var method = typeof(Person).GetMethod("MakeMoney");

        int moneys = (int)method.Invoke(person, null);

        return moneys;
    }

    [Benchmark()]
    public int UseDynamic()
    {
        dynamic person = new Person();

        int moneys = person.MakeMoney();

        return moneys;
    }
}

```

看一下 **BenchmarkDotNet** 测试结果，从报告中能看出来，使用 Dynamic 方式的方法的平均执行时间（Mean）和内存分配（AllLocated）时远小于使用反射实现的。

![image.png](https://niuery.com/static/img/6525a4af3162ab178d8351644358b473.image.png)


## 结论

在相同数量级的反射实现和使用 Dynamic 方式实现， Dynamic 方式在执行时间或内存分配或代码简洁都是有优势的，所以**推荐使用 dynameic 来简化反射实现**。

编码技巧 --- 使用dynamic简化反射

## 介绍

今天介绍一个非常强大的基于.Net 的基准测试工具[BenchmarkDotNet](https://github.com/dotnet/BenchmarkDotNet)。

**BenchmarkDotNet** 已经被14300多个项目采用，包括非常多的知名开源项目，例如
- dotnet/performance（.Net所有运行时的基准测试项目）
- dotnet/runtime（.Net 运行时库），
- Roslyn (c#和Visual Basic编译器)，
- Mono、 ASP.NET Core、 ML.NET、 Entity Framework Core、 PowerShell SignalR、 f#、 Orleans, Newtonsoft.Json、Elasticsearch.Net、Dapper等诸多知名开源项目。



**BenchmarkDotNet**能够自动在所有运行时运行基准，汇总测试结果，并打印一个汇总表，其中包含众多基准信息：

![image.png](https://niuery.com/static/img/88011dbb5e07b75259d13fa4c02d71e4.image.png)

这些测试数据也可以导出为不同的格式(md, html, csv, xml, json等)，包括图片:

![image.png](https://niuery.com/static/img/c88bdd3cc5033da6d139913e4ebba4b3.image.png)

最主要的是它可以非常容易的编写基准测试，只需要安装好NuGet包之后，给需要测试的方法标注 `Attribute`，就可以执行测试。

## Demo
这里可以使用控制台或单元测试来进行测试。

官方GitHub上分别提供了基于控制台和基于XUnit单元测试的基准测试：
- [基于控制台Demo](https://github.com/dotnet/BenchmarkDotNet/tree/master/samples/BenchmarkDotNet.Samples)(https://github.com/dotnet/BenchmarkDotNet/tree/master/samples/BenchmarkDotNet.Samples)
- [基于Xunit单元测试Demo](https://github.com/dotnet/BenchmarkDotNet/tree/master/tests/BenchmarkDotNet.IntegrationTests)(https://github.com/dotnet/BenchmarkDotNet/tree/master/tests/BenchmarkDotNet.IntegrationTests)

接下来，以一个基于控制台的基准测试来讲解一下：

```csharp
class Program
{
    static void Main(string[] args)
    {
        BenchmarkRunner.Run<BenchmarkTest>();
    }
}

[SimpleJob(RunStrategy.ColdStart, iterationCount: 100000)]
public class BenchmarkTest
{
    [Benchmark()]
    public void CreateTuple()
    {
        var temp = new Tuple<int, string>(1, "");
    }
}
```

上述代码中，创建了一个 `BenchmarkTest` 类用于做基准测试，然后创建了一个 `CreateTuple()`方法，该方法创建一个 `Tuple` 对象，然后我们给这个方法标记 `[Benchmark()]` ,标记该方法用于做基准测试，然后在`BenchmarkTest` 类上标记 `[SimpleJob(RunStrategy.ColdStart, iterationCount: 100000)]`，表示是以冷启动的方式，执行该类要测试的基准方法100000次。

接下来，来看一下测试结果，输出：

![image.png](https://niuery.com/static/img/c2a7420ee028fcb436120ed92fbba760.image.png)

## 讲解

可以看到控制台输出分为了几个部分。

### Summary

可以看到控制台输出中黄色部分加下方表格，就是该报告主要内容，能看到当前执行测试时的运行环境，测试条件（IterationCount=100000  RunStrategy=ColdStart），表格中也能看到具体性能，比如，
1. Method(测试方法的名称为CreateTuple)。
2. Mean（测试运行的平均时间为420.7纳秒）。
3. Error(测试运行的标准误差为16.96纳秒)。
4. StdDev(所有测试运行的标准偏差为1630纳秒)。
5. Median(所有测试运行的中位数为300纳秒)。



### Legends

简单描述了表格中的一些参数。

实际上在 `BenchmarkDotNet` 中，这样的统计数据列大概有90多条，可以[参考这里](https://github.com/dotnet/BenchmarkDotNet/blob/master/src/BenchmarkDotNet/Columns/Column.cs)(https://github.com/dotnet/BenchmarkDotNet/blob/master/src/BenchmarkDotNet/Columns/Column.cs)

下面挑出一些常用统计列，简单解释：

- Method: 测试方法的名称。
- Mean: 所有测试运行的平均时间。
- Error: 测试运行的标准误差，标准误差是测试结果的离散程度的度量，标准误差越小，表示测试结果越稳定。
- StdDev: 所有测试运行的标准偏差，标准偏差是测试结果的离散程度的度量，标准偏差越小，表示测试结果越接近平均值。
- Median: 所有测试运行的中位数。中位数是测试结果的中间值，如果测试结果的个数为奇数，则中位数为中间的那个值；如果测试结果的个数为偶数，则中位数为中间两个值的平均值。
- Ratio: 每个测试运行的平均时间与基准测试运行的平均时间的比值。基准测试是性能最好的测试，它的比值为 1.0。其他测试的比值表示它们相对于基准测试的性能表现，比值越小，表示性能越好。
- RatioSD: 所有测试运行的比值的标准偏差。标准偏差越小，表示比值的离散程度越小，测试结果更稳定。
- Gen 0: 所有测试运行期间生成的第 0 代垃圾回收的次数。垃圾回收是 .NET 运行时自动回收不再使用的内存的机制，Generational Garbage Collection 是 .NET 中的一种垃圾回收算法。
- Gen 1: 所有测试运行期间生成的第 1 代垃圾回收的次数。
- Gen 2: 所有测试运行期间生成的第 2 代垃圾回收的次数。
- Allocated: 所有测试运行期间分配的内存总量。

### Warings

会给出一些警告，或者建议操作，像示例代码中生成100000个 `Tuple` 对象，他就报警方法执行实现太短，建议使用更多操作将其增加到至少100.0000 ms。

### Export
上面其实还有一部分控制台内容是 **Export** 内容 ,如下图所示：

![image.png](https://niuery.com/static/img/6cd7d808396959b3f2985fd3420a34e1.image.png)

默认给你生成了三种格式的报告，CSV格式，Markdownn格式，和Html格式，生成路径是运行根目录下的`BenchmarkDotNet.Artifacts\results\`文件夹下的 `BenchmarkDotNet.Console.BenchmarkTest-report`文件。

![image.png](https://niuery.com/static/img/937b599bbf4e631fca5d09965a572021.image.png)

## 总结
本篇抛砖引玉，只讲述基于控制台做基准测试，强烈建议各位看官阅读Github上的示例，学会使用更多的参数，借助 `BenchmarkDotNet` 做出更准确准确、更可靠的性能测试结果。


>参考
>
>BenchmarkDotNet Github地址：https://github.com/dotnet/BenchmarkDotNet
>
>基于控制台Demo Github地址：https://github.com/dotnet/BenchmarkDotNet/tree/master/samples/BenchmarkDotNet.Samples
>
>基于Xunit单元测试Demo Github地址：https://github.com/dotnet/BenchmarkDotNet/tree/master/tests/BenchmarkDotNet.IntegrationTests
>
>统计数据列参考 Githu地址：https://github.com/dotnet/BenchmarkDotNet/blob/master/src/BenchmarkDotNet/Columns/Column.cs

基准测试工具 --- BenchmarkDotNet

## 引言

上一篇[数据结构与算法 --- 排序算法（一）](https://niuery.com/post/54)中，学习了冒泡排序，插入排序，选择排序这三种时间复杂度为 $O(n^2)$ 的算法。实时上 $O(n^2)$ 时间复杂度是非常高的，所以一般只适合小规模数据排序，那接下来，就在看一看时间复杂度为 $O(nlog)$ 的算法：归并排序和快速排序。
 

## 分治算法思想

归并排序和快速排序的核心思想就是分治算法思想，所以先介绍一下分治算法思想：

**分治算法思想简单来说就是将一个复杂的问题分解成几个较简单的子问题，再递归地解决这些子问题**。通常遵循以下三个步骤:

- 分解：将问题分解成几个较小的子问题，这些子问题必须是相同类型的问题，且解决这些子问题必须可以解决原问题。

- 解决：递归地解决各个子问题，如果子问题足够小可以直接解决则解决，否则继续分解。

- 合并：将子问题的解合并为原问题的解。

## 归并排序
归并排序（Merge Sort）是一种基于分治思想的排序算法。它的基本思路是将待排序的数组分成两个子序列，然后对每个子序列进行递归排序，最后将排好序的两个子序列合并成一个有序序列。
### 算法图解
来看一下归并排序的执行过程如下图：

![image.png](https://niuery.com/static/img/564d9fac8cfc2e08719bdca0ffffa6fb.image.png)

接下来考虑如何使用C#代码实现一个归并排序算法？

一般归并排序就是通过递归实现的，那么在[数据结构与算法 --- 递归（一）](https://niuery.com/post/51)中总结了递归代码的编写技巧：写递推公式，寻找终止条件，最后将递推公式翻译为代码。

那么看一下归并排序的递归代码的递推公式为：


$$
merge\_sort(p,r)=merge(merge(p,q),merge(q+1,r)),  \quad (p<q<r)
$$
其终止条件为:$p\ge r$。

公式中 $ merge\_sort(p,r) $ 表示对下标从 $p$ 到 $r$ 的数组数据进行归并排序，然后将这个问题拆分成了两个子问题： $merge(p,q)$ 和 $merge(q+1,r)$ ，其中下标 $q$ 表示 $p$ 到 $r$ 的中间位置，也就是$\frac{p+r}{2}$，当这两个子数组排好序之后，再将这两个有序子数组合并（$merge()$），就完成了该数组的排序。

这里还需要着重讲解一下两个有序子数组的合并，实际上一般在这里合并方法使用的是双指针法，双指针法是合并两个有序数组最高效的算法，其时间复杂度为 $O(m+n)$，其中 m 和 n 分别是两个数组的长度。
具体实现步骤如下：

1. 定义两个指针 i 和 j，分别指向两个有序数组的起始位置。
2. 定义一个空数组 temp，用于存储合并后的有序数组。
3. 比较两个指针所指的元素大小，将较小的元素加入 temp 数组中，并将对应的指针向后移动一位。
4. 重复步骤 3，直到其中一个指针超出了数组的范围。
5. 将另一个数组中剩余的元素加入 temp 数组中。
6. 最后将temp中的元素拷贝回arr中,完成排序。

综上，用C#代码实现一个归并算法如下：

```csharp
public static void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        //将待排序的数组分成两个子序列进行递归排序
        MergeSort(arr, left, mid);
        
        MergeSort(arr, mid + 1, right);
        //合并
        Merge(arr, left, mid, right);
    }
}

public static void Merge(int[] arr, int left, int mid, int right)
{
    //双指针法合并数据到temp数组
    int i = left, j = mid + 1, k = 0;
    
    int[] temp = new int[right - left + 1];
    
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            temp[k] = arr[i];
            i++;
        }
        else
        {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    //当一边遍历完成后,将另一边剩余元素直接放入temp。
    while (i <= mid)
    {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= right)
    {
        temp[k] = arr[j];
        j++;
        k++;
    }
    for (int p = 0; p < k; p++)
    {
        arr[left + p] = temp[p];
    }
}

```

### 算法分析
**稳定性：**

归并排序是否稳定关键要看 `Merge()` 方法这部分逻辑。

在合并过程中，如果前半部分（图解左侧）和后半部分（图解右侧）之间有相同元素，先把前半部分中相同的值放入临时数组temp，再把后半部分中的相同的值放入临时数组temp，那么就能保证值相同的元素在合并前后的先后顺序不变，因此，归并排序是稳定排序算法。
    

   
**时间复杂度：**

归并排序的时间复杂度可以通过递归树和递推式来分析，具体分为以下几个步骤：

1. 分解：将待排序的数组逐步分解成更小的子数组，直到每个子数组只有一个元素。

2. 合并：将相邻的子数组两两合并，形成更大的有序子数组。

3. 递归：对合并后的有序子数组重复上述步骤，直到最终得到完全有序的数组。

现在我们来分析归并排序的时间复杂度：

1. 分解步骤：在每一次分解过程中，数组被均分为两部分，所以分解的时间复杂度是 $O(logn)$，其中n是待排序数组的长度。

2. 合并步骤：合并操作需要比较每个子数组中的元素，并将它们按照顺序放入新的临时数组中。在最坏情况下，每个子数组的长度为$\frac{n}{2}$，所以合并的时间复杂度是 $O(n)$。而在每一层的递归中，总共有 $n$ 个元素需要进行合并操作，所以合并的时间复杂度也是 $O(n)$。

3. 递归步骤：归并排序通过递归调用对子数组进行排序，每次将数组的长度减半。因此，总共进行 $logn$ 次递归操作。

综上所述，归并排序的时间复杂度可以表示为：


$$
T(n) = O(logn)   \times    O(n) = O(nlogn)
$$

所以，归并排序的时间复杂度是O(nlogn)。无论输入数组的初始状态如何，归并排序的时间复杂度都保持不变。


**内存消耗：**
很明显，归并排序使用了额外的内存空间，所以它不是原地排序算法。

我们不能像分析时间复杂度那样分析空间复杂度，因为空间复杂度是一个峰值，而时间复杂度是一个累加值，递归代码的空间消耗并不能像时间消耗那样累加，空间复杂度表示在程序运行过程中的最大消耗，而不是累加的内存消耗。

尽管每次合并操作都需要申请额外的临时数组temp，但在函数完成之后，临时数组temp所占的内存就被释放了。

在任意时刻，只会有一个函数在执行，也就只会有一个临时数组temp在使用，占用的临时空间内存最大也不会超过 n 个数据的大小，对应的空间复杂度也就是$O(n)$。

除此之外，在归并排序的过程中，递归调用栈的空间复杂度取决于递归深度。对于一个长度为n的数组进行归并排序，递归深度为log₂n。每一层递归都需要保存一些临时变量，如左右指针、中间指针等，这些变量的空间复杂度为 $O(1)$。因此，递归调用栈的空间复杂度为 $O(log₂n)$。

综上所述，归并排序的空间复杂度为$O(logn + n)$。 可以省略低阶部分，那就是$O(n)$。


>参考
>
> [1] 数据结构与算法之美 / 王争 著. --北京：人民邮电出版社，2021.6