常见面时问题 一．算法 1.冒泡排序 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。 2.快速排序 (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 [2] (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
3.二分查找
二．数据结构 1.数组Array[] 内存上连续分配，元素类型相同，通过下标访问，读取快，增删慢，长度不变。 2.动态数组ArrayList[] 跟数组的不同：长度可变，元素类型可不同，会有装箱操作 3.列表List<> 本质上是数组，长度不够时，申请此时长度的两倍的内存进行复制操作。 跟数组不同：泛型，类型安全，不定长，避免装箱拆箱 4.链表LinkedList 泛型，内存不连续，每个元素有前后节点，节点值可以重复，不能下标访问，找元素只能遍历，查找慢，增删快 5.队列Quene 先进先出的链表 6.栈Stack 先进后出的链表 7.字典Dictionary 泛型，增删改查都快，类型不安全，有序 三．优化 1.CPU优化（性能优化） （1）缓存对象，不要频繁查找 （2）对象池 （3）测试代码，空的start update也会消耗内存 （4）避免CPU峰值，如同时实例化非常多的对象，提前加载实例化，协程每帧创建等手段。 （5）避免触发GC。使用profiler工具定位造成大量垃圾内存的函数进行优化。String的相关操作，变量的相关操作 （6）其他小地方： ①减少对粒子系统Play()的调用； ②处理Rigidbody时，使用FixedUpdate，设置Fixed timestep，减少物理计算次数； ③如果可以，尽量不用MeshCollider，如果不能避免的话，尽量用减少Mesh的面片数，或用较少面片的物体来代替； ④使用内建数组如使用Vector3.zero而不是new Vector(0,0,0)； ⑤每次访问Transform.position/rotation都有相应的消耗。能cache就cache其返回结果； ⑥如果可能，尽量用Queue/Stack来代替List； ⑦同一脚本中频繁使用的变量建议声明其为全局变量，脚本之间频繁调用的变量或方法建议声明为全局静态变量或方法； 2. GPU优化（渲染优化） （1）基础知识： ①一个draw call包含网格数据以及网格如何被渲染。在某些场景，共享设置的一些对象可能会被合并为一个draw call。合并不同对象的数据到同一个draw call被称作batching ②CPU会发出指令，使GPU改变一些渲染状态。这个指令被称为SetPass call。SetPass call通知GPU，如何去渲染下一个网格。只有在渲染下一个网格时，其渲染状态相对于渲染上一个网格发生了变化时，才会调用SetPass call。 ③渲染优化的主要目的就是减少渲染的工作量，控制渲染的工作量是保证效率的根本，而每帧渲染的顶点数量是衡量渲染工作量最直观的标准之一：每帧可渲染的顶点数量主要取决于设备的CPU和GPU。 不过通常来说PC游戏每帧渲染的顶点个数不宜超过2M，移动游戏每帧渲染的顶点数量不宜超过0.1M。 （2）具体内容： ①如果是CPU限制，如SetPassCalls 或者Batches过多，可通过以下手段解决： ·减少渲染对象：降低摄像机渲染距离，使用遮挡剔除 ·减少渲染次数：使用光照贴图，关闭不需要的阴影，谨慎使用反射探针 ·合并渲染对象：使用静态合批，谨慎使用动态合批，使用GPUInstanceing，使用纹理图集 ②如果是GPU限制，即Verts 、Tris过多，可通过以下手段解决： ·Shader优化 ·纹理压缩：根据需要降低图片大小，改变压缩方式 ·Mipmap/LOD:根据距离改变渲染精度 四．渲染 1.渲染管线 三个阶段：应用阶段-几何阶段-光栅化阶段 应用阶段：CPU准备数据，即渲染图元，数据包括点线面等。 几何阶段：包括顶点着色器，曲面细分着色器，几何着色器，裁剪，屏幕映射五个阶段。 光栅化阶段：包括三角形设置，三角形遍历，片元着色器，逐片元操作四个阶段。 顶点着色器：Vertex Shader 完全可编程，通常实现顶点的空间变换，顶点着色等功能。 ① 顶点坐标从模型空间转换到齐次裁剪空间 ② 逐顶点光照，计算顶点颜色 曲面细分着色器：Tessellation Shader 可选着色器，用于细分图元 几何着色器：Gemetry Shader 可选着色器，可被用于逐图元的着色操作，或者用于产生更多图元。 裁剪：Cliping 裁剪掉不在摄像机视野内的顶点，并剔除某些三角图元片面。 屏幕映射：Screen Mapping 不可操作，每个图元转坐标换到屏幕坐标 三角形设置：固定函数操作，计算每个三角形网格需要的信息。上一个阶段输出的是三角形网格的顶点，现在这个是要计算三角形的面的信息。 三角形遍历：固定函数操作，检查每个像素是否被三角形覆盖，覆盖的话就生成一个片元fragment。使用三角网格三个顶点信息对整个覆盖区域的像素插值。并不影响每个像素的，只是记录影响此像素的信息。 片元着色器：有很多重要操作，如：修改颜色、深度缓冲、进行混合等，不可编程，但有很高的可配置性。根据上一步的信息，计算出一个或者多个颜色值。 逐片元操作：决定每个片元的可见性，如深度测试、模板测试；如果通过所有测试就混合片元颜色值和存储在颜色缓冲区的颜色。高度可配置，每一步都可以设置。 五．设计模式 https://www.cnblogs.com/zhaoqingqing/p/4288454.html 1.单例 2.监听者/广播 2.工厂 六．Shader 七．程序设计原则
