C#实现依赖反转

依赖反转(Dependency Inversion)是一种设计原则,它强调高层模块不应该依赖低层模块,而是应该依赖抽象接口。同时,抽象不应该依赖具体实现,而是具体实现应该依赖抽象。

这个原则可以通过使用接口和依赖注入(Dependency Injection)来实现。接口定义了模块的行为,而不是实现细节,这样高层模块就可以依赖接口,而不是依赖具体的实现。依赖注入是一种将依赖关系从代码中移除的技术,它允许组件在运行时通过构造函数或属性来接收依赖项,而不是在组件内部创建它们。

通过应用依赖反转原则,可以提高代码的可维护性和可测试性,因为它使得代码更容易进行修改和扩展,而不需要修改其他部分的代码。

以下是一个简单的 C# 代码示例,它演示了如何使用依赖反转原则来实现一个简单的打印机程序。

首先,我们定义一个 IPrinter 接口,它表示打印机的行为:

public interface IPrinter
{
    void Print(string text);
}

接下来,我们定义一个 Printer 类,它实现了 IPrinter 接口:

public class Printer : IPrinter
{
    public void Print(string text)
    {
        Console.WriteLine(text);
    }
}

现在,我们定义一个 Document 类,它依赖于 IPrinter 接口:

public class Document
{
    private readonly IPrinter _printer;
 
    public Document(IPrinter printer)
    {
        _printer = printer;
    }
 
    public void PrintDocument(string text)
    {
        _printer.Print(text);
    }
}

在上面的代码中,Document 类的构造函数使用依赖注入方式接收一个 IPrinter 实例,并将其保存在私有字段中。然后,PrintDocument 方法使用这个实例来打印文档。

最后,我们可以在 Main 方法中创建一个 Printer 实例和一个 Document 实例,并将 Printer 实例传递给 Document 的构造函数:


static void Main(string[] args)
{
    IPrinter printer = new Printer();
    Document document = new Document(printer);
 
    document.PrintDocument("Hello, world!");
}

在上面的代码中,我们使用依赖反转原则,将 Document 类从具体的 Printer 类解耦,使得我们可以在运行时动态地替换打印机实现,从而使代码更加灵活和可扩展。


————————————————
版权声明:本文为CSDN博主「老白游戏开发」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/pengfeicfan/article/details/130604215

彻底搞懂递归的时间复杂度

笔者编码10载,面过很多程序员简历上写着熟悉数据结构和算法,但是对于时间复杂度稍微深入点的问题,都回答的不怎么样,其实还是没懂

搞懂算法时间复杂度是一个优先程序员的分水岭

先来看letcode一道题,
泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2:

输入:n = 25
输出:1389537

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-th-tribonacci-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道经典面试题,属于斐波那契数的升级版,很多人很快的写出算法

/**

  • @param {number} n
  • @return {number}
    */
    const tribonacci = (n) => {
    if (n === 0) {
    return 0;
    } else if (n === 1) {
    return 1;
    } else if (n === 2) {
    return 1;
    }
    return tribonacci(n – 1) + tribonacci(n – 2) + tribonacci(n – 3);
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    当然这道试题这样写会超时,原因就不细说了,这个时候面试官会问你这么写的算法时间复杂度是多少
    有的同学可能一看到递归就想到了logn,其实并不是这样,问他是怎么算的,他好像并不知道

再看第二题
来看一下这道面试题:求x的n次方

大家想一下这么简单的一道题目 代码应该如何写。

最直观的方式应该就是,一个for循环求出结果,代码如下

int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
}
1
2
3
4
5
6
7
时间复杂度为O(n)

此时面试官会说,有没有效率更好的算法呢。

如果同学们此时没有思路,建议不要说:我不会,我不知道。可以和面试官探讨一下,问:可不可以给点提示。

面试官一般会提示:考虑一下递归算法

有的同学就写出了如下这样的一个递归的算法,使用递归解决了这个问题

int function2(int x, int n) {
if (n == 0) {
return 1; // return 1 同样是因为0次方是等于1的
}
return function2(x, n – 1) * x;
}
1
2
3
4
5
6
面试官问:那么这份代码的时间复杂度是多少?

有的同学可能一看到递归就想到了logn,其实并不是这样

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

那我们再来看代码,我们递归了几次呢。

每次n-1,递归了n次 时间复杂度是O(n),每次进行了一个乘法操作,乘法操作的时间复杂度一个常数项O(1)

所以这份代码的时间复杂度是 n * 1 = O(n)

这个时间复杂度可能就没有达到面试官的预期。

于是同学又写出了这样的一个递归的算法的代码如下 ,来求 x的n次方

int function3(int x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 1) {
return function3(x, n/2) * function3(x, n/2)*x;
}
return function3(x, n/2) * function3(x, n/2);
}
1
2
3
4
5
6
7
8
9
面试官看到后微微一笑,问这份代码的时间复杂度又是多少呢?

我们来分析一下

首先看递归了多少次呢,可以把递归的次数 抽象出一颗满二叉树。

我们刚刚写的这个算法,可以用一颗满二叉树来表示(为了方便表示 我选择n为偶数),如图:

当前这颗二叉树就是求x的n次方,n为16的情况

n为16的时候 我们进行了多少次乘法运算呢

这棵树上每一个节点就代表着一次递归并进行了一次相乘操作

所以 进行了多少次递归的话,就是看这棵树上有多少个节点。

熟悉二叉树的同学应该知道如何求满二叉树节点数量

这颗满二叉树的节点数量就是2^3 + 2^2 + 2^1 + 2^0 = 15

有同学就会发现 这其实是等比数列的求和公式, 如果不理解的同学可以直接记下来这个结论。

这个结论在二叉树相关的面试题里也经常出现。

这么如果是求x的n次方,这个递归树有多少个节点呢,如下图所示

时间复杂度忽略掉常数项-1之后,我们发现这个递归算法的时间复杂度依然是O(n)。

此时面试官就会问, 貌似这个递归的算法依然还是O(n)啊, 很明显没有达到面试官的预期

那么在思考一下 O(logn)的递归算法应该怎么写

这里在提示一下 上面刚刚给出的那份递归算法的代码,是不是有哪里比较冗余呢。

来看这份优化后的递归算法代码

int function4(int x, int n) {
if (n == 0) {
return 1;
}
int t = function4(x, n/2);// 这里相对于function3,是把这个递归操作抽取出来
if (n % 2 == 1) {
return ttx;
}
return t*t;
}
1
2
3
4
5
6
7
8
9
10
那我们看一下 时间复杂度是多少

依然还是看他递归了多少次

我们可以看到 这里仅仅有一个递归调用,且每次都是 n/2

所以这里我们一共调用了 log以2为底n的对数次

每次递归了做都是一次乘法操作,这也是一个常数项的操作,

所以说这个递归算法的时间复杂度才是真正的O(logn)。

如果同学们最后写出了这样的代码并且时间复杂度分析的非常清晰,相信面试官是比较满意的。

最后希望通过这么一个简单的面试题,让大家真正了解了递归算法的时间复杂度该如何分析。

主定理
介绍一个叫主定理的东西,这个定理为什么重要,就是因为这个主定理的话,其实它是用来解决所有递归的函数,怎么来计算它的时间复杂度。主定理本身的话,数学上来证明相对比较复杂(关于主定理可以参考维基百科:https://zh.wikipedia.org/wiki…)

也就是说,任何一个分治或者递归的函数,都可以算出它的时间复杂度,怎么算就是通过这个主定理。本身比较复杂的话,那怎样化简为实际可用的办法,其实关键就是这四种,一般记住就可以了

一般在各种递归的情形的话,有上边这四种情形,是在面试和平时工作中会用上

二分查找(Binary search):一般发生在一个数列本身有序的时候,要在有序的数列中找到目标数,所以它每次都一分为二,只查一边,这样的话,最后它的时间复杂度是O(logn)

二叉树遍历(Binary tree traversal):如果是二叉树遍历的话,它的时间复杂度为O(n)。因为通过主定理可以知道,它每次要一分为二,但是每次一分为二之后,每一边它是相同的时间复杂度。最后它的递推公式就变成了图中T(n)=2T(n/2)+O(1)这样。最后根据这个主定理就可以推出它的运行时间为O(n)。当然这里也有一个简化的思考方式,就是二叉树的遍历的话,会每一个节点都访问一次,且仅访问一次,所以它的时间复杂度就是O(n)

二维矩阵(Optimal sorted matrix search):在一个排好序的二维矩阵中进行二分查找,这个时候也是通过主定理可以得出时间复杂度是O(n),记住就可以了

归并排序(merge sort):所有排序最优的办法就是nlogn,归并排序的时间复杂度就是O(nlogn)

再附一张主定理的计算方法,目前只找到的比较好的资料

总结:
递归可以使用递归树或者主定理去求解,需要多做题去掌握,下次千万不要碰到递归说是O(logn)了,如果有问题欢迎指正

课后作业

求整数n (n>=0)阶乘的算法如下,其时间复杂度是( )
int fact(int n){
if (n<=l) return 1;
return n*fact(n-1);
}
1
2
3
4
题2写一道算法题
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

/**

  • @param {number[]} nums
  • @return {number}

*/

var reversePairs = function(nums) {

};

Unity优化之Drawcall

一、什么是Drawcalls
在Unity中,每次CPU准备数据并通知GPU的过程就称之为一个DrawCall。这个过程会指定一个Mesh被渲染,绘制材质。

二、Drawcalls有什么影响
为了CPU和GPU可以进行并行工作,需要一个命令缓冲区,由CPU向其中添加命令,然后由GPU从中读取命令,这样就实现了通过CPU准备数据,通知GPU进行渲染。在每次调用DrawCall之前,CPU需要向GPU发送很多内容,主要是包括数据,渲染状态,命令等。所以如果DrawCall数量过多就会导致CPU进行大量计算,进而导致CPU的过载,影响程序运行效率。

三、查看Drawcalls
在unity中查看drawcalls有2个方法,如图1所示查看Game窗口中的State下的Batces,这个数量和drawcalls数量相同。第二种方法是查看Window → Analysis → Profiler 中的Rendering下的Drawcalls,如图2所示。

四、Drawcalls优化

  1. 3D场景优化
    1.1 静态批处理
    静态批处理首先需要到 Project Setting → Player → Other Setting 中将Static Bathing 勾选上,然后把需要静止的物体标记为Static,然后无论大小,相同材质的都会组成Batch。如下图所示,当没有勾选 static 的时候,场景中2个cube的drawcalls为4,勾选了之后drawcalls变成了3。

1.2 动态批处理
动态批处理需要在Project Setting → Player → Other Setting 中将Dynamic Bathing 勾选上,Unity会自动将使用相同材质的物体合并处理。如图所示,场景中虽然有3个cube,但是drawcalls还是只有3。

不过,在使用动态批处理的时候,具有一些局限性。

顶点属性最大限制900的可移动物体,

使用lightmap的物体不行进行批处理

使用多通道的shader也不会进行批处理

缩放比不同的物体不会批处理

1.3 勾选 Enable GPU Instancing
在使用大量重复的物体时,需要将该物体的材质的 Enable GPU Instancing 勾选上,这样Unity会将Mesh相同的物体合并处理,常用于树木,植被,粒子等。如图所以虽然我放置了5个cube,但是drawcalls依然只有3。

正在上传…重新上传取消
1.4 减少实时光照和阴影效果
当开启灯光,在没有开启阴影的时候drawcalls为3,开启了之后drawcalls变成了7。实时阴影会导致drawcalls大幅上升,建议关闭实时阴影,使用lightmap满足你想要的阴影效果。

1.5 合并Mesh和材质球
如果一个模型有2个或者以上的材质球的时候,drawcalls会直线上升,所以应该劲量将mesh和材质球合并成为一个,以减少drawcalls。如图所示我在一个测试cube中放置了3个material,这个时候drawcalls从3变成了10(和不同的material有关,每个material最低为1)。

1.6 渲染顺序调整
Unity的渲染是有顺序的,这个顺序我们可以自己调整,相机按照深度进行渲染。在图中我使用了3个cube梯次排序,其中第一个和第三个使用相同的材质球。当第二个cube在中间时,drawcalls为5,第二个cube在前或者后时,drawcalls为4。

出现图中情况的原因是在绘制第一个cube时候使用材质球A,绘制第二个cube的时候使用材质球B,绘制第三个cube的时候使用材质球A,这个时候第二个打断了材质球A的渲染使用,使第一个和第三个材质球分开渲染了。

  1. 2D UI优化
    2.1 图集制作
    在制作UI的时候,文件夹中小的图片可以在Unity中制作成图集再给UI使用,这样可以减少drawcalls,具体操作为首先在Project Setting →Editor → Sprite Packer 中选择Mode 为Enable。然后在Assets中右键 Create → Sprite Altas,再将需要打包图集的图片资源拖到Altas中的Objects for Packing中,再点击Pack Preview,图集就制作好了。

如图所示,在没有使用图集的时候,3张图drawcalls为5,当使用的图集时,drawcalls变成了3,3个图使用同一张图集,drawcalls也就变成了3。

2.2 不同图集重叠会打断合批
不同的图集之间重叠会打断合批,在制作UI的时候应该注意不同的UI放置位置,避免出现这种问题,如图,2个图集的UI在分开放的时候drawcalls为4,重叠隔开之后drawcalls变成了5。

2.3 谨慎使用多canvas
每添加一个canvas会添加一个drawcalls,哪怕你下面的资源使用同一个图集也会添加。如图所示当我添加一个canvas,改变了第三个图的层次之后,drawcalls从3变成了4。

2.4 Mask会打断合批,新增drawcalls
当我给使用了图集的一个UI添加一个Mask组件之后,drawcalls从3变成了5。这里可以使用Rect Mask 2D,效果相同但是drawcalls不会增加,回到了3。当我在有Mask组件的UI下添加一个Image,sprite还是使用图集中的图片时,发现drawcalls从5变成了6,说明mask组件还会打断合批,使Mask内外资源分开渲染。这个时候将Mask改为Rect Mask 2D,drawcalls从6变回4,但是也比最初的3多了1,说明使用Rect Mask 2D 也会打断合批,分开渲染。

2.5 图文混排打断合批
新加入两个Text文本(Text Mesh Pro效果相同),drawcalls从3变到4,因为text和image有不同写渲染方式需要分开渲染,移动Text,当2个Text打断了图的连续深度排序时,图片的合批会被,打断,生成多的drawcalls,在图文排版是应特别注意。下图列举了一些错误排版方式和正确方法以及建议排版。

正确:

错误:

建议:

GPU instance 使用一次渲染调用来绘制多个物体,来节省每次绘制物体时CPU→GPU的通信

使用限制 优点
静态合批 静止的问题,大内存,大包体 StaticBatchingUtility.Combine 适用范围较广
动态合批 * 顶点属性最大限制900,
* 使用lightmap的物体不行进行批处理
* 使用MultiplePass的shader也不会进行批处理 在一些动的物体上面,内存不会显著增长,不会影响打包的包体
GPUInstance 一般用于大批生成的物体 没有动态合批那样对网格数量的限制,也没有静态网格那样需要这么大的内存
SRP Batcher 不同mesh,只要使用相同shader且变体一样即可 缺点:constant Buffer显存固定开开销,不支持 节省Uniform Buffer的写入操作;按shader分 Batch,预先生存Uniform Buffer,Batch 内部无CPU Write
————————————————
版权声明:本文为CSDN博主「老白游戏开发」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/pengfeicfan/article/details/126963192