第七章：速记Day7-灵析社区
英勇黄铜问题 1：gbdt 的目标函数是什么
GBDT 特指梯度提升决策树算法。GBDT 是在函数空间上利用梯度下降进行优化。
GBDT 是多个弱分类器合成强分类器的过程(加权求和)，每次迭代产生一个弱分类器，当前弱分类器是在之前分类器残差基础上训练。GBDT 的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。
Gradient 即每个文档得分的一个下降方向组成的N维向量，N为样本个数。这里仅仅是把”求残差“的逻辑替换为”求梯度“，可以这样想：梯度方向为每一步最优方向，累加的步数多了，总能走到局部最优点，若该点恰好为全局最优点，那和用残差的效果是一样的。
目标：损失函数尽可能快减小，则让损失函数沿着梯度方向下降。--> gbdt 的 gb 的核心了。
问题 2：React 事件绑定的方式有哪些？
- render 方法中使用 bind
- render 方法中使用箭头函数
- constructor 中 bind
- 定义阶段使用箭头函数绑定
问题 3：卷积神经网络可被用哪些方面 ?
- 模式分类
- 物体检测
- 物体识别
- 图像识别
问题 4：请由低到高依次写出事物的隔离级别
读取未提交、读取已提交、可重复读、可串行化
问题 5：添加索引时需要注意哪些原则？
- 在查询中很少使用或者参考的列不要创建索引。
- 只有很少数据值的列 也不应该增加索引。
- 定义为 text、image 和 bit 数据类型的列不应该增加索引。
- 当 修改性能远远大于检索性能 时，不应该创建索引。
- 定义有 外键 的数据列一定要创建索引。
问题 6：B+ Tree 与 B-Tree 的结构很像，但是也有自己的特性，它的有哪些？
- 所有的非叶子结点只存储 关键字信息
- 所有具体数据都存在叶子结点中
- 所有的叶子结点中包含了全部元素的信息
- 所有叶子节点之间都有一个链指针
问题 7：车规划算法了解哪些 ?
根据车辆导航系统的研究历程 , 车辆路径规划算法可分为静态路径规划算法和动态路径算法。静态路径规划是以物理地理信息和交通规则等条件为约束来寻求最短路径，静态路径规划算法已日趋成熟 , 相对比较简单 , 但对于实际的交通状况来说 , 其应用意义不大。
动态路径规划是在静态路径规划的基础上 , 结合实时的交通信息对预先规划好的最优行车路线进行适时的调整直至到达目的地最终得到最优路径。下面介绍几种常见的车辆路径规划算法。
1. Dijkstra 算法
Dijkstra（迪杰斯特拉）算法是最短路算法的经典算法之一，由 E.W.Dijkstra 在 1959 年提出的。该算法适于计算道路权值均为非负的最短路径问题，可以给出图中某一节点到其他所有节点的最短路径，以思路清晰，搜索准确见长。相对的，由于输入为大型稀疏矩阵，又具有耗时长，占用空间大的缺点。其算法复杂度为 O ( n ² ) ，n 为节点个数。
2. Lee 算法
Lee 算法最早用于印刷电路和集成电路的路径追踪，与 Dijkstra 算法相比更适合用于数据随时变化的道路路径规划，而且其运行代价要小于 Dijkstra 算法。只要最佳路径存在，该算法就能够找到最佳优化路径。Lee 算法的复杂度很难表示，而且对于多图层的路径规划则需要很大的空间。
3. Floyd 算法
Floyd 算法是由 Floyd 于 1962 年提出的，是一种计算图中任意两点间的最短距离的算法。可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包，Floyd-Warshall 算法的时间复杂度为 O ( n ³ ) ，空间复杂度为 O ( n ² ) ，n 为节点个数。与对每一节点作一次 Dijkstra 算法的时间复杂度相同，但是实际的运算效果比 Dijkstra 算法要好。
4. 启发式搜索算法—— A* 算法
启发式搜索有很多的算法，如 : 局部择优搜索法、最好优先搜索法、A* 算法等。其中 A* 算法是由 Hart、Nilsson、Raphael 等人首先提出的，算法通过引入估价函数，加快了搜索速度，提高了局部择优算法搜索的精度，从而得到广泛的应用，是当前较为流行的最短路算法。A* 算法所占用的存储空间少于 Dijkstra 算法。其时间复杂度为 O ( bd ) ，b 为节点的平均出度数，d 为从起点到终点的最短路的搜索深度。
5. 双向搜索算法
双向搜索算法由 Dantzig 提出的基本思想，Nicholson 正式提出算法。该算法在从起点开始寻找最短路径的同时也从终点开始向前进行路径搜索，最佳效果是二者在中间点汇合，这样可缩短搜索时间。但是如果终止规则不合适，该算法极有可能使搜索时间增加 1 倍，即两个方向都搜索到最后才终止。
6. 蚁群算法
蚁群算法是由意大利学者 M.Dorigo 等于 1991 年提出的，它是一种随机搜索算法 , 是在对大自然中蚁群集体行为的研究基础上总结归纳出的一种优化算法，具有较强的鲁棒性，而且易于与其他方法相结合，蚁群算法的复杂度要优于 Dijkstra 算法。
此外 , 还有实时启发式搜索算法、基于分层路网的搜索算法、神经网络、遗传算法及模糊理论等，由于实际需求不同对算法的要求和侧重点也会有所不同，所以也出现了许多以上算法的各种改进算法。大多数算法应用于求解车辆路径规划问题时都会存在一定的缺陷，所以目前的研究侧重于利用多种算法融合来构造混合算法。
问题 8：struct 和 class 区别
在 C++ 里 struct 关键字与 class 关键字一般可以通用的。
struct 和 class 的区别:
- struct 更适合看成是一个数据结构的实现体，class 更适合看成是一个对象的实现体。struct 没有继承，没有封装，要说封装只有初步封装。而 class 把数据，接口可以以三种类型封装，private， public，protected;还可以继承和派生。
- class 是引用类型，而 struct 是值类型。
class 有默认的无参构造函数，有析构函数，struct 没有默认的无参构造函数，且只能声明有参的构造函数，没有析构函数:class 可以使用 abstract 和 sealed，有 protected 修饰符。
- struct 不可以用 abstract 和 sealed，没有 protected 修饰符。
它们都可以提供自己的接口函数，构造函数。一个类可以由结构继承而来。struct 只能叫做数据的集合，外部可以任意访问，但是类就完成了封装，维护了数据安全，这就是面向对象的理念。
class 实例由垃圾回收机制来保证内存的回收处理，而 struct 变量使用完后立即自动解除内存分配:从职能观点来看，class 表现为行为，而 struct 常用于存储数据。
问题 9：AUC 是怎么计算的
1. 最直观的，根据 AUC 这个名称，我们知道，计算出 ROC 曲线下面的面积，就是 AUC 的值。事实上，这也是在早期 Machine Learning 文献中常见的AUC计算方法。由于我们的测试样本是有限的。我们得到的 AUC 曲线必然是一个阶梯状的。因此，计算的 AUC 也就是这些阶梯下面的面积之和。
这样，我们先把 score 排序(假设 score 越大，此样本属于正类的概率越大)，然后一边扫描就可以得到我们想要的 AUC。但是，这么 做有个缺点，就是当多个测试样本的 score 相等的时候，我们调整一下阈值，得到的不是曲线一个阶梯往上或者往右的延展，而是斜着向上形成一个梯形。
此时，我们就需要计算这个梯形的面积。由此，我们可以看到，用这种方法计算 AUC 实际上是比较麻烦的。
2. 一个关于AUC的很有趣的性质是，它和 Wilcoxon-Mann-Witney Test 是等价的。而 Wilcoxon-Mann-Witney Test 就是测试任意给一个正类样本和一个负类样本，正类样本的 score 有多大的概率大于负类样本的 score。有了这个定义，我们就得到了另外一中计算 AUC 的办法：得到这个概率。
我们知道，在有限样本中我们常用的得到概率的办法就是通过频率来估计之。这种估计随着样本规模的扩大而逐渐逼近真实值。
这和上面的方法中，样本数越多，计算的 AUC 越准确类似，也和计算积分的时候，小区间划分的越细，计算的越准确是同样的道理。具体来说就是统计一下所有的 M×N(M为正类样本的数目，N为负类样本的数目)个正负样本对中，有多少个组中的正样本的 score 大于负样本的score。
当二元组中正负样本的 score相等的时候，按照 0.5 计算。然后除以 MN。实现这个方法的复杂度为 O(n^2)。n 为样本数（即 n=M+N ）
3. 第三种方法实际上和上述第二种方法是一样的，但是复杂度减小了。它也是首先对 score 从大到小排序，然后令最大 score 对应的 sample 的 rank 为n，第二大 score 对应 sample 的 rank 为n-1，以此类推。然后把所有的正类样本的 rank 相加，再减去 M-1 种两个正样本组合的情况。得到的就是所有的样本中有多少对正类样本的 score 大于负类样本的 score。然后再除以 M×N。即
公式解释：
1.为了求的组合中正样本的 score 值大于负样本，如果所有的正样本 score 值都是大于负样本的，那么第一位与任意的进行组合 score 值都要大，我们取它的 rank 值为 n，但是 n-1 中有 M-1 是正样例和正样例的组合这种是不在统计范围内的（为计算方便我们取n组，相应的不符合的有 M 个），所以要减掉，那么同理排在第二位的 n-1，会有 M-1 个是不满足的，依次类推，故得到后面的公式 M*(M+1)/2，我们可以验证在正样本 score 都大于负样本的假设下，AUC 的值为1
2.根据上面的解释，不难得出，rank 的值代表的是能够产生 score 前大后小的这样的组合数，但是这里包含了（正，正）的情况，所以要减去这样的组（即排在它后面正例的个数），即可得到上面的公式。
另外，特别需要注意的是，再存在 score 相等的情况时，对相等 score 的样本，需要 赋予相同的 rank (无论这个相等的 score 是出现在同类样本还是不同类的样本之间，都需要这样处理)。具体操作就是再把所有这些 score 相等的样本 的rank取平均。然后再使用上述公式。
问题 10：讲一下多进程和多线程
（1）进程：
一个进程，包括了代码、数据和分配给进程的资源（内存），在计算机系统里直观地说一个进程就是一个 PID。操作系统保护进程空间不受外部进程干扰，即一个进程不能访问到另一个进程的内存。有时候进程间需要进行通信，这时可以使用操作系统提供进程间通信机制。
通常情况下，执行一个可执行文件操作系统会为其创建一个进程以供它运行。但如果该执行文件是基于多进程设计的话，操作系统会在最初的进程上创建出多个进程出来，这些进程间执行的代码是一样，但执行结果可能是一样的，也可能是不一样的。
为什么需要多进程？最直观的想法是，如果操作系统支持多核的话，那么一个执行文件可以在不同的核心上跑；即使是非多核的，在一个进程在等待 I/O 操作时另一个进程也可以在 CPU 上跑，提高 CPU利用率、程序的效率。
在 Linux 系统上可以通过 fork () 来在父进程中创建出子进程。一个进程调用 fork () 后，系统会先给新进程分配资源，例如存储数据和代码空间。然后把原来进程的所有值、状态都复制到新的进程里，只有少数的值与原来的进程不同，以区分不同的进程。fork () 函数会返回两次，一次给父进程（返回子进程的 pid 或者 fork 失败信息），一次给子进程（返回0）。
至此，两个进程分道扬镳，各自运行在系统里。
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
#include <stdlib.h>
void print_exit(){
printf("the exit pid:%d\n",getpid() );
}
int main (){
pid_t pid;
atexit( print_exit ); //注册该进程退出时的回调函数
pid=fork(); // new process
int count = 0;
if (pid < 0){
printf("error in fork!");
}
else if (pid == 0){
printf("i am the child process, my process id is %d\n",getpid());
count ++;
printf("child process add count.\n");
}
else {
printf("i am the parent process, my process id is %d\n",getpid());
count++;
printf("parent process add count.\n");
sleep(2);
wait(NULL);
}
printf("At last, count equals to %d\n", count);
return 0;
} 上述代码在 fork() 之后进行了一次判断，以辨别当前进程是父进程还是子进程。
为了说明父进程与子进程有各自的资源空间，设置了对 count 的计数。Terminal输出如下：、
明显两个进程都执行了count++操作，但由于count是分别处在不同的进程里，所以实质上count在各自进程上只执行了一次。
（2）线程：
线程是可执行代码的可分派单元，CPU 可单独执行单元。在基于线程的多任务的环境中，所有进程至少有一个线程（主线程），但是它们可以具有多个任务。这意味着单个程序可以并发执行两个或者多个任务。
也就是说，线程可以把一个进程分为很多片，每一片都可以是一个独立的流程，CPU 可以选择其中的流程来执行。但线程不是进程，不具有 PID，且分配的资源属于它的进程，共享着进程的全局变量，也可以有自己“私有”空间。
但这明显不同于多进程，进程是一个拷贝的流程，而线程只是把一条河流截成很多条小溪。它没有拷贝这些额外的开销，但是仅仅是现存的一条河流，就被多线程技术几乎无开销地转成很多条小流程，它的伟大就在于它少之又少的系统开销。
Linux 中可以使用 pthread 库来创建线程，但由于 pthread 不是 Linux 内核的默认库，所以编译时需要加入pthread 库一同编译。
g++ -o main main.cpp -pthread
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
void* task1(void*);
void* task2(void*);
void usr();
int p1,p2;
int count = 0 ;
int main() {
usr();
return 0;
}
void usr(){
pthread_t pid1, pid2;
pthread_attr_t attr;
void *p1, *p2;
int ret1=0, ret2=0;
pthread_attr_init(&attr); //初始化线程属性结构
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); //设置attr结构
pthread_create(&pid1, &attr, task1, NULL); //创建线程，返回线程号给pid1,线程属性设置为attr的属性
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
pthread_create(&pid2, &attr, task2, NULL);
ret1=pthread_join(pid1, &p1); //等待pid1返回，返回值赋给p1
ret2=pthread_join(pid2, &p2); //等待pid2返回，返回值赋给p2
printf("after pthread1:ret1=%d,p1=%d\n", ret1,(int)p1);
printf("after pthread2:ret2=%d,p2=%d\n", ret2,(int)p2);
printf("At last, count equals to %d\n", count);
}
void* task1(void *arg1){
printf("task1 begin.\n");
count++;
printf("task1 thread add count.\n");
pthread_exit( (void *)1);
}
void* task2(void *arg2){
printf("thread2 begin.\n");
count ++;
printf("task2 thread add count.\n");
pthread_exit((void *)2);
} 上述代码的中主线程在usr()函数中创建了两个线程，线程的属性都是JOINABLE，即可以被其他线程收集返回信息。然后等待两个线程的返回，输出返回信息。
Terminal 的输出显示 thread2 先于 thread1 执行，表明了这不是一个同步的程序，线程的运行是单独进行的，由内核线程调度来进行的。为了区别进程，在代码中也加入了 count++ 操作。最后在主线程中输出 count=2，即 count 被计数了2次，子线程被允许使用同一个进程内的共享变量，区别了进程的概念。
由于线程顺序、时间的不确定性，往往需要对进程内的一个共享变量进行读写限制，比如加锁等。
阅读量：616
点赞量：0
收藏量:0