C++及图像算法基础知识（二）

PS：为了面试准备的，总结的有点粗糙。

 

1.使用了未初始化的局部变量

错误：

 

 

正确：

 

 

2.指针与指向指针的指针

Pointer to an integer value

int* i

 

Pointer to a pointer to an integer value

int** i

 

3.i++ 与++i的区别

use ++i if you don't have a specific reason to use i++

 

对于自定义类型，重载运算符：

 

Foo& Foo::operator++()   // called for ++i
{
    this->data += 1;
    return *this;
}

Foo Foo::operator++(int ignored_dummy_value)   // called for i++
{
    Foo tmp(*this);   // variable "tmp" cannot be optimized away by the compiler
    ++(*this);
    return tmp;
}

 

i++多了一个拷贝的动作， If the copy constructor is expensive, then this can have a significant performance impact.

 

 

4.C和汇编的区别

C语言可读性好，代码便于维护，便于开发；汇编语言编写的程序不容易看懂，可维护性不好，但是执行效率高。

1）语言效率

汇编语言实质上是机器语言(0,1序列)的助记符

汇编语言与机器语言是一一对应的。但是C语言呢？当然没这么好事了。C语言的语法是固定的，C语言编写的程序要编译成CPU能读懂的机器语言指令，没办法一一对应，所以就需要有编译规则了。

我试验过，用C编写一个简单的程序，比方说只包含一个for循环，编译出的代码和用汇编写的最优代码几乎是一样。但代码量一大，由于受制于规则（不受制也不行呀，否则编不出来），编出来的代码与用汇编语言写出来的代码相比就走了不少“弯路”了。虽然说，现在的很多C编译器在编译的时候都会有优化，但是，不可能做得到效率上等同于与机器语言一一对应的汇编语言的效率。毕竟，汇编语言可以理解为直接就是面对CPU的，只不过是机器语言用助记符代替而矣。  

2）资源利用

汇编是直接面对CPU的语言，只要是在指令集支持的范围内，汇编语言可以直接而灵活地管理包括特殊功能寄存器、通用寄存器、存储单元的每一个字节，甚至是每一个bit。C语言对内存的使用及管理功能也是很强大的，但毕竟还是受制于语法。举个最简单的例子，C语言当中没有对应三字节或是五字节的变量类型，要么int型，要么long型，所以每次申请必须是固定的字节数，势必造成内存使用上的浪费。而大部份汇编语言根本没有这样的语法，在伪指令的帮助下（其实也只是提高可读性），汇编语言程序可以使用任意字节数的变量，当然处理起来比C语言麻烦得多，最终还是一个字节一个字节地拼接处理，而用C语言写程序就轻松了，不用管这些，最终编译器会搞定嘛。而轻松的代价就是造成了浪费。而内存使用效率不高同时也会影响到整个程序的整体效率。 

 

5. 静态内存与动态内存

静态内存使用的是栈空间内存，不用程序员自己来分配。因为静态变量占用的存储空间对于编译器而言是可预计的，静态内存只需要编程的时候直接声明就可以了。数组

动态内存分配又称为堆内存分配，是指计算机程序在运行期中分配使用内存。链表

 

区别：

1）时间不同。静态分配发生在程序编译和链接的时候。动态分配则发生在程序调入和执行的时候。

2）空间不同。堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。

3）静态内存是在程序一开始运行就会分配内存，直到程序结束了，内存才被释放。

动态内存是在程序调用在程序中定义的函数时才被分配，在程序结束后，操作系统会自动回收。但是有必要手动释放。

 

由malloc函数分配的内存就是从堆上分配内存。从堆上分配的内存一定要自己释放。用free释放，不然就有可能发生“内存泄露”。

malloc函数的原型为：void *malloc (unsigned int size) 其作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整型数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。

 

栈上的内存有一个特点即是不用我们手工去释放申请的内存。栈内存由一个栈指针来开辟和回收。变量直接声明即是静态分配栈内存；依靠alloca来动态分配栈内存。

 

内存管理：

https://chenqx.github.io/2014/09/25/Cpp-Memory-Management/

 

分配内存时有一句老话：First time you do it, then something change it.(不受你控制)

 

int test = 0; //全局静态存储区
int* ptrTest = &test; // 这个指针自己也是在全局静态存储区上，指向的内存地址也是。

int main()
{
    int a = 2;//栈上
    int* ptr = &a;//ptr是在栈上，然后它指向的内存地址也是栈上的

    int* ptrHeap = new int(2);
    // new是在堆上申请的内存，返回的是这个申请的内存的地址
    // 然后ptrHeap是指向这个地址的，但是ptrHeap它自己是占的栈上的地址。
    delete ptrHeap;

return 0;
}

 

6.多态的理解及作用

多态是面向对象的重要特性,简单点说:“一个接口，多种实现”，就是同一种事物表现出的多种形态。

 

（编程其实就是一个将具体世界进行抽象化的过程，多态就是抽象化的一种体现，把一系列具体事物的共同点抽象出来, 再通过这个抽象的事物, 与不同的具体事物进行对话。） 

 

对不同类的对象发出相同的消息将会有不同的行为。

多态允许将子类的对象当作父类的对象使用，某父类型的引用指向其子类型的对象,调用的方法是该子类型的方法。这样可以写出通用的代码，做出通用的编程，以适应需求的不断变化，便于后期维护。

 

编译时多态: 就是 function overloading

运行时多态: 就是 virtual function overriding

 

OO的三个特性：

封装可以隐藏实现细节，使得代码模块化；继承可以扩展已存在的代码模块（类）；它们的目的都是为了——代码重用。而多态除了代码的复用性外，还可以解决项目中紧偶合的问题,提高程序的可扩展性.。耦合度讲的是模块模块之间，代码代码之间的关联度，通过对系统的分析把他分解成一个一个子模块，子模块提供稳定的接口，达到降低系统耦合度的的目的，模块模块之间尽量使用模块接口访问，而不是随意引用其他模块的成员变量。

 

7.栈、堆、静态存储区最大可分配大小

栈stack大小与编译器有关。默认情况下，visual studio 2010 的栈大小为1M。但在平时应用程序中，由于函数会使用栈结果，所以只能用略小于1M大小的栈。对于64位和32位程序，结果都是一样的，因为VS2010已经设定好了默认的栈大小了。

静态存储区(全局变量）

对于全局变量来说，与编译器有关（不保证正确）

默认情况下，VS2010可容纳的全局变量数组大小是2G。由于程序本身的应用，所以只能使用小于2G大小。

对于堆Heap来说，与程序是32位还是64位，以及编译器都有关。

在VS2010的默认情况下，32位程序可以申请的堆大小最大是2G。实际上只能小于2G。而64位程序，如果没有虚拟内存（硬盘）的支持，则可以使用128G的内存（比如说，你有8G内存，就可以使用8G内存）。而如果你把虚拟内存开启，则可以理论上得到16TB的内存使用大小。

细节：由于C++自己的考虑，new操作在64位下也只能最多获得4G内存，而用C函数malloc则可以得到理论上的内存大小

 

8.计算机的存储 速度

 

9.编译过程

词法分析（Lexical analysis或Scanning）

词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。

 

语法分析（Syntax analysis或Parsing）

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.

 

语义分析（Syntax analysis） 

语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个C程序片断:

int arr[2],b;

b = arr * 10; 

源程序的结构是正确的. 

语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.

 

 

10.静态链接/动态链接

静态链接：指程序编译时直接把静态库（Static Linked Library，’.lib’）中调用的函数代码链接进目标程序，因此程序运行时不再需要它的库文件。 

 

动态链接：指把调用函数所在的动态库（Dynamic Linked Library，’.dll’）和调用函数在文件中的位置等信息链接进目标程序，程序运行时再从DLL中寻找相应函数代码，因此需要相应DLL文件的支持。 

 

区别：动态库是运行时才加载到内存中，程序运行时可以随意加载或移除；静态库是编译时就加载到内存中，不能手动移除。 

 

11.int char数组和string之间的互换

 

12.内存分配

https://www.cnblogs.com/fuleying/p/4454869.html

 

13.L1、L2范数/正则化的区别

L1正则化是指权值向量w中各个元素的绝对值之和；L2正则化是指权值向量w中各个元素的平方和然后再求平方根

• • L1正则化可以产生稀疏权值矩阵，即产生一个稀疏模型，可以用于特征选择
  • L2正则化可以防止模型过拟合（overfitting）；一定程度上，L1也可以防止过拟合

 

稀疏矩阵指的是很多元素为0，只有少数元素是非零值的矩阵，即得到的线性回归模型的大部分系数都是0. 通常机器学习中特征数量很多，在预测或分类时，那么多特征显然难以选择，但是如果代入这些特征得到的模型是一个稀疏模型，表示只有少数特征对这个模型有贡献，绝大部分特征是没有贡献的，或者贡献微小，此时我们就可以只关注系数是非零值的特征。这就是稀疏模型与特征选择的关系。

 

为什么L1可以特征选择？考虑二维

 

 

J0与这些角接触的机率会远大于与LL其它部位接触的机率

 

圆，与方形相比，被磨去了棱角。因此J0与L相交时使得w1或w2等于零的机率小了许多，这就是为什么L2正则化不具有稀疏性的原因。

 

为什么L2可以防止过拟合？

设想一下对于一个线性回归方程，若参数很大，那么只要数据偏移一点点，就会对结果造成很大的影响；但如果参数足够小，数据偏移得多一点也不会对结果造成什么影响，专业一点的说法是『抗扰动能力强』。

λ就是正则化参数。从上式可以看到，与未添加L2正则化的迭代公式相比，每一次迭代，θj都要先乘以一个小于1的因子，从而使得θj不断减小，因此总得来看，θ是不断减小的。

最开始也提到L1正则化一定程度上也可以防止过拟合。当L1的正则化系数很小时，得到的最优解会很小，可以达到和L2正则化类似的效果。

 

 

14.模型选择

选择泛化误差小的，但是泛化误差又不能直接得到——>模型评估方法

P-R曲线 AOC AUC F1-score等

 

15.FPGA的高频考点还是要复习

怎样用FPGA实现除法器

 

建立时间与保持时间

Setup time  Tsu 在时钟沿到来之前数据稳定不变的时间，如果建立的时间不满足要求那么数据将不能在这个时钟上升沿被稳定的打入触发器

Hold time  Th  时钟沿到来之后数据稳定不变的时间，如果保持时间不满足要求那么数据同样也不能被稳定的打入触发器

输出响应时间（Tco）

触发器输出的响应时间，也就是触发器的输出在clk时钟上升沿到来之后多长的时间内发生变化，也即触发器的输出延时。

 

 

15.什么是流水线设计

流水线设计就是将组合逻辑系统地分割，并在各个部分（分级）之间插入寄存器，并暂存中间数据的方法。目的是将一个大操作分解成若干的小操作，每一步小操作的时间较小，所以能提高频率，各小操作能并行执行，所以能提高数据吞吐率（提高处理速度）。

使用场景：

1.功能模块之间的流水线，用乒乓 buffer 来交互数据，代价是增加了 memory 的数量

2.I/O 瓶颈，比如某个运算需要输入 8 个数据，而 memroy 只能同时提供 2 个数据，如果通过适当划分运算步骤，使用流水线反而会减少面积。

3.片内 sram 的读操作，因为 sram 的读操作本身就是两极流水线

4.组合逻辑太长，比如(a+b)*c，那么在加法和乘法之间插入寄存器是比较稳妥的做法

优点：

缩短了在一个时钟周期内给的那个信号必须通过的通路长度，增加了数据吞吐量，从而可以提高时钟

频率，但也导致了数据的延时

缺点：

功耗增加，面积增加，硬件复杂度增加，特别对于复杂逻辑如 cpu 的流水线而言，流水越深，发生

需要 hold 流水线或 reset 流水线的情况时，时间损失越大。

 

总结一下，流水线就是插入寄存器，以面积换取速度。

 

取指、译码和执行等操作可以重叠执行，在执行上一条指令的同时就可取出下一条指令，并进行译码，这大大的提高了微处理器的速度

 

16、优先队列

优先队列是一种用来维护一组元素构成的结合S的数据结构，其中每个元素都有一个关键字key，元素之间的比较都是通过key来比较的。优先队列包括最大优先队列和最小优先队列。

插入：上浮

 

删除：下沉

 

17、判断一棵树是不是平衡二叉树

 

18.梯度弥散和梯度爆炸怎么解决

https://blog.****.net/u013403054/article/details/78424095

 

19.delete 和 delete[]区别

C++告诉我们在回收用 new 分配的单个对象的内存空间的时候用 delete，回收用 new[] 分配的一组对象的内存空间的时候用 delete[]。 

关于 new[] 和 delete[]，其中又分为两种情况：(1) 为基本数据类型分配和回收空间；(2) 为自定义类型分配和回收空间。

delete p1 在回收空间的过程中，只有 p1[0] 这个对象调用了析构函数，其它对象如 p1[1]、p1[2] 等都没有调用自身的析构函数，这就是问题的症结所在。如果用 delete[]，则在回收空间之前所有对象都会首先调用自己的析构函数。 

    基本类型的对象没有析构函数，所以回收基本类型组成的数组空间用 delete 和 delete[] 都是应该可以的；但是对于类对象数组，只能用 delete[]。对于 new 的单个对象，只能用 delete 不能用 delete[] 回收空间。 

    所以一个简单的使用原则就是：new 和 delete、new[] 和 delete[] 对应使用。

 

20.回归和分类的区别

分类和回归的区别在于输出变量的类型。

定量输出称为回归，或者说是连续变量预测；

定性输出称为分类，或者说是离散变量预测。

举个例子：

预测明天的气温是多少度，这是一个回归任务；

预测明天是阴、晴还是雨，就是一个分类任务。

 

21.线性分类器和非线性分类器

线性分类器：模型是参数的线性函数，分类平面是（超）平面；

非线性分类器：模型分界面可以是曲面或者超平面的组合。

典型的线性分类器有感知机，LDA，logistic回归，SVM（线性核）；

典型的非线性分类器有朴素贝叶斯（有文章说这个本质是线性的，http://dataunion.org/12344.html），kNN，决策树，SVM（非线性核）