精华内容
下载资源
问答
  • 说说性能测试的几个概念

    千次阅读 2019-04-27 12:21:03
    性能测试数据收集中很重要的一部分是被测系统的资源使用情况,因为系统性能和资源使用是密切相关的,主要的目的下面几个方面: 了解在当前压力下,系统各项资源的使用情况,也可以用于横向对比。 通过资源使用情况...

    性能测试(Performance Test)

    通过测试工具和测试手段,监测和收集测试过程中的软件系统运行数据,度量系统与预定义目标的差距。而预定义目标就是通过性能需求来表示。

    怎样才能更有效的获得性能需求?以便更好设计、执行性能测试。可以按以下步骤:

    1. 收集,根据项目历史数据,或者根据经验

    2. 分析,比如业务人员很多,底层到中层、再到高层。

    分析历史数据、竞品、业务。业务需要分析业务常见、业务高峰(大的时间和小的时间段)

    性能问题还存在可以细分一下是场景遗漏、还是数据遗漏。场景遗漏常常由于需求传递变味导致。

    处理方法。 做好策略和设计,如果针对现在的问题:可以做一个checklist不断优化你的策略设计能力。

    关注点:how much和how fast

    测试阶段

    有些同事在测试几轮之后,功能稳定了开始介入性能测试,这时才发现性能根本支撑不了预期值。这个时候就再回头进行系统调优,如果事先选的架构能支撑就好,如果不能达到预期值,后面讨论或者请教高手发现原先的架构缺陷,再调整架构代价就非常大。基本导致前期的功能测试成果作废。其实各个阶段都有事情做:

    需求阶段可以整理,评审出性能需求,评审需求可行性时就要考虑好数据量和用户量。

    设计阶段--对预估的需求做设计,举个例子,背景:我们现在使用的是mysql数据库(公司去oracle化),我们要从一个5000W的一个数据表的6个不同查询维度查询数据,比如说城市、行业、地址类型、爱好、性别、时间范围。这样对于mysql的查询常见的优化设计可能是分表、建立索引,但对于这个场景就不好处理了,数据耦合强,没有办法分表,索引,组合索引太多。后面的处理办法是用mongodb、nosql的方法解决。对于编码和测试阶段可以这样去分不同阶段做不同事情:

     

    编码阶段,可以提出需要,让研发通过单元测试(开多线程)的方式进行压力测试。进行一些单元压力测试阶段也有策略的,建议先做一下单一场景单一用户的性能测试。常常会遇到有些同事在没有压单个场景的情况下,就进行负载测试,到处定位瓶颈,最后发现单一用户单一场景都是问题。这就是绕了一圈回到了起点。

    测试阶段,性能测试的频率根据业务场景需要就测、评估需求的时候,发现有性能需求就计划去做,但建议主要功能每隔3个小版本,关注一下业务量,业务量快达到预估值时进行一次,另外要考虑业务高峰期,比如双11、双12、618、春节等,建议之前都做一次。当然不同行业有不同的高峰期。

    对于测试阶段的不同测试类别,不细说,这里就说一下什么是基准测试和配置测试:

    基准测试:是一种可再现性的测试(对于软件产品来来说,同样的数据量标准、硬件标准下性能指标相对确定;对于硬件产品来说,基准测试标准更是固定而明确的),一般首次测试,会把单用户(如果是双节点负载均衡就要双用户)单场景作为基准测试,而对于多轮测试来说,上一轮测试的稳定基准配置,定为新的基准测试标准,因为基准测试的关键是要获得一致的、可再现的结果。那么什么时候要做基准测试呢,当软件增加了新模块或有大的迭代更新,当硬件环境做了优化提升时。

    配置测试:配置测试方法是指通过对被测系统软硬件环境的调整,了解各种不同环境对系统性能影响的程度,从而找到系统各项资源的最优分配原则。配置测试主要是针对硬件而言,其测试过程是测试目标软件在具体硬件配置情况下,出不出现问题,为的是发现硬件配置可能出现的问题,可能需要做的调优。

    基准测试是相对固定的方法,配置测试是验证性测试的目的。

    关注点:When and where

    负载测试(Load Test)

    负载测试是一种性能测试,指数据在超负荷环境中运行,程序是否能够承担。通过逐步增加系统负载,确定在满足性能指标的情况下,系统所能承受的最大负载量。

    关注点:how much

    压力测试(Stress Test)

    压力测试是一种高负载下的负载测试,也就是说被系统处于一个负载的情况,再继续对他进行加压,形成双重负载,直到系统崩溃,并关注崩溃后系统的恢复能力,以前再加压的一个过程,看看系统到底是否已经被彻底破坏掉了。

    有个很形象的说法就是:你能够承担100千克的重量,而且也能走,但是你能否承担100千克的重量行走1个月。

    外部的负载叫压力,内部的压力叫负载。负载注重关注内部的以及系统自身一些情况;而压力更关注系统外部的表象.

    性能测试模型

    性能测试的执行过程是由轻到重,逐渐对系统施压。通常用户最关心的性能指标包括:响应时间、吞吐量、资源利用率和最大用户数。我们可以将这张图分成3个区域,即:轻负载区域、重负载区域和负载失效区域。

    • 轻负载区域
      在这个区域您可以看到随着虚拟用户数量的增加,系统资源利用率和吞吐量也随之增加,而响应时间没有特别明显的变化;

    • 重负载区域
      在这个区域您可以发现随着虚拟用户数量的增加,系统资源利用率随之缓慢增加,吞吐量开始也缓慢增加,随着虚拟用户数量的增长,资源利用率保持相对的稳定(满足系统资源利用率指标),吞吐量也基本保持平稳,后续则略有降低,但幅度不大,响应时间会有相对较大幅度的增长;

    • 负载失效区域
      在这个区域系统资源利用率随之增加并达到饱和,如CPU利用率达到95%甚至100%,并长时间保持该状态,而吞吐量急剧下降和响应时间大幅度增长(即:出现拐点)。

    • 两个交界点
      在轻负载区域和重负载区域交界处的用户数,我们称为"最佳用户数"。而重负载区域和负载失效区域交界处的用户数则称为"最大用户数"。

    当系统的负载等于最佳用户数时,系统的整体效率最高,系统资源利用率适中,用户请求能够得到快速响应;

    当系统负载处于最佳用户数和最大用户数之间时,系统可以继续工作,但是响应时间开始变长,系统资源利用率较高,并持续保持该状态,如果负载一直持续,将最终会导致少量用户无法忍受而放弃;

    而当系统负载大于最大用户数时,将会导致较多用户因无法忍受超长的等待而放弃使用系统,有时甚至会出现系统崩溃,而无法响应用户请求的情况发生。

    并发用户数

    相对并发用户数(用户视角)

    即在线用户数,在一个时间段内,与服务器进行了交互、对服务器产生了压力的用户的数量。这个时间段,可以是一天,也可以是一个小时。

    通常像ab、wrk等并发工具设定的并发数,就是指的这个并发数,比如在JMeter中,如果将某个线程组的线程数设置为100,那是不是对于这个类型的请求,并发量就是100。从宏观的角度,这样理解也是对的,就好比请了100个人,每个人独立地完成一连串的工作,确实是100个在并行。但是对于服务器感受到的压力,可能就不是100了。

    这里所谓的100个并行对于服务端而言并不是严格的全部并行,因为每个虚拟用户执行的节奏是独立。假设这个操作需要3个请求完成,那么很有可能出现这样的情况:某个虚拟用户还在等待第一个请求的响应,但是另一个虚拟用户已经收到了第一个请求的响应并发起了第二个请求。那么对于服务端而言,在某一个时刻,无论是对于请求1还是请求2,并行度都没有到100。这个模型比较类似于图中右边部分所示的模型。理解这个模型对于并行的理解非常重要。

    这里的差异在于宏观上的并行还是严格意义上的并行,比如就某个请求的严格意义上的并行或许可以通过TCP连接的保持数来看。通过“netstat|grep ESTABLISH|wc-l”命令获得保持连接状态的TCP请求数量。也就是下面的绝对并发用户数。

    并发与并行是相关的概念,但是也有很多细节上的差异。并发意味着两个或更多的任务正在取得进展,即使它们不是同时执行的。例如,可以用时间片的方式实现这一点,每个任务在时间片内执行一小部分,并与其它任务的切片混合执行。如并发收集器。并行的出现使任务实现了真正的同时执行。

    绝对并发用户数(服务器视角)

    主要是针对某一个操作进行测试,即多个用户同一时刻发起相同请求。

    图中,每一个颜色的线段代表一种操作。在任意一个时刻,服务器都知道它有10个事务需要处理,这10个事务也是有10个用户产生的。但它不知道的是,整个时间段内的所有事务,是由多少个用户与系统交互而产生的。时刻1,10个当前事务是由10个用户发起的。时刻2,依然是10个正在进行的事务,但可能是完全不同的10个人发起的。在这段时间内,服务器每一个时刻都在处理10个事务,但是参与了这个交互过程(对服务器产生压力)的人可能会达到上百个,也可能只有最开始的10个。那么,对于服务器来说,压力是什么呢?显然只是每时刻这10个同时处理的事务。

    Think Time

    在进行相对并发用户数的测算时,think time的设置会影响测试的结果。设想这样的一个场景,一个真实的用户在某个电商网站上购物,一个简化的流程可能如下: 1)进入首页 2)搜索一个商品 3)查看商品详情 4)加入购物车 5)提交订单 6)完成支付 基于上面的讨论我们可以构造一系列JMeter请求,放在一个线程组里面。 如果我们要测试针对这样的用户,我们的系统可以支持多少人同时来购物。假设我们已经考虑了用户登录账号和购买商品的参数化问题,是否可以直接将线程组的数值设置到一个较大的数值,然后并发执行呢?

    这样可以执行起来,但是有一个很大的问题。在于真实用户和脚本的不同。脚本如果是基于前面方法录制的,两个请求的执行时间之前是没有任何其他停顿的,其间隔只是依赖于上一个服务的响应时间和测试机发起请求所需的时间。但是显然真实的用户不是机器,他们在做上面每一个步骤的时候都有一个思考的时间,这也是Think Time这个词的意义来源。

    当然,这个思考时间也是泛指,包括了用户操作的时间,比如进入首页后,用户需要在搜索框中输入想购买商品的关键词,打开输入法并输入相关的词可能也需要少则几秒钟的时间,搜索结果出来之后用户需要浏览和选择,找到感兴趣的商品并点击查看详情,后面的步骤也是类似。 试想一下,对比请求连续执行和每个步骤间加入模拟真实用户的Think Time之后,对于同一个系统,能支持的同时在线购物人数必定会有绝大的差异,而有Think Time的做法显然更接近真实情况。

    准备工作

    不同的机器、操作系统、web服务器以及相关参数等的不同,也会影响性能测试的结果。有必要在测试前对参数进行一下配置。
    比如做一次性能测试并对高负载系统,网络参数进行调优。这里列一下操作系统的几个重要参数。

    fs.file-max = 999999  
    net.ipv4.tcp_tw_reuse = 1
    net.ipv4.tcp_keepalive_time = 600
    net.ipv4.tcp_fin_timeout = 30
    net.ipv4.tcp_max_tw_buckets = 5000
    net.ipv4.ip_local_port_range = 1024    61000
    net.ipv4.tcp_rmem = 4096 32768 262142
    net.ipv4.tcp_wmem = 4096 32768 262142
    net.core.netdev_max_backlog = 8096
    net.core.rmem_default = 262144
    net.core.wmem_default = 262144
    net.core.rmem_max = 2097152
    net.core.wmem_max = 2097152
    net.ipv4.tcp_syncookies = 1
    net.ipv4.tcp_max_syn.backlog=1024
    
    • file-max:这个参数表示进程(比如一个worker进程)可以同时打开的最大句柄数,这个参数直接限制最大并发连接数,需根据实际情况配置。
    • tcp_tw_reuse:这个参数设置为1,表示允许将TIME-WAIT状态的socket重新用于新的TCP连接,这对于服务器来说很有意义,因为服务器上总会有大量TIME-WAIT状态的连接。 - tcp_keepalive_time:这个参数表示当keepalive启用时,TCP发送keepalive消息的频度。默认是2小时,若将其设置得小一些,可以更快地清理无效的连接。
    • tcp_fin_timeout:这个参数表示当服务器主动关闭连接时,socket保持在FIN-WAIT-2状态的最大时间。
    • tcp_max_tw_buckets:这个参数表示操作系统允许TIME_WAIT套接字数量的最大值,如果超过这个数字,TIME_WAIT套接字将立刻被清除并打印警告信息。该参数默认为180000,过多的TIME_WAIT套接字会使Web服务器变慢。
    • tcp_max_syn_backlog:这个参数表示TCP三次握手建立阶段接收SYN请求队列的最大长度,默认为1024,将其设置得大一些可以使出现Nginx繁忙来不及accept新连接的情况时,Linux不至于丢失客户端发起的连接请求。
    • ip_local_port_range:这个参数定义了在UDP和TCP连接中本地(不包括连接的远端)端口的取值范围。
    • net.ipv4.tcp_rmem:这个参数定义了TCP接收缓存(用于TCP接收滑动窗口)的最小值、默认值、最大值。
    • net.ipv4.tcp_wmem:这个参数定义了TCP发送缓存(用于TCP发送滑动窗口)的最小值、默认值、最大值。
    • netdev_max_backlog:当网卡接收数据包的速度大于内核处理的速度时,会有一个队列保存这些数据包。这个参数表示该队列的最大值。
    • rmem_default:这个参数表示内核套接字接收缓存区默认的大小。
    • wmem_default:这个参数表示内核套接字发送缓存区默认的大小。
    • rmem_max:这个参数表示内核套接字接收缓存区的最大大小。
    • wmem_max:这个参数表示内核套接字发送缓存区的最大大小。
    • tcp_syncookies:该参数与性能无关,用于解决TCP的SYN攻击。

    测试工具

    性能测试工具的几个核心的模块

    • 压力生成器(Virtual User Generator)
    • 结果采集器(Result Collector)
    • 负载控制器(Controller)
    • 系统资源监控器(Monitor)
    • 结果分析器(Analysis)

     

    由此可以看出,像wrk、apache bench这类的工具,其实不算是完整的性能测试工具,因为它们并没有系统资源监控器,这样的话,其实简单测试出来的结果并不是很准确,只能说是简单粗暴凑合着用。

    被测系统资源监控

    性能测试数据收集中很重要的一部分是被测系统的资源使用情况,因为系统性能和资源使用是密切相关的,主要的目的有下面几个方面: 了解在当前压力下,系统各项资源的使用情况,也可以用于横向对比。 通过资源使用情况的分析可以看出当前是否测出了系统最大的性能。 是否有某项资源的使用已经到达上限,成为瓶颈。 是否有其他非被测系统的模块占用了资源。 通常在性能测试中,测试人员都会去收集CPU、内存、网络等服务器资源使用情况,但是如果只是笼统地给出一个百分比是不够的,需要进一步细分来提供更多有参考价值的数据。

    因此如果只是简单地用wrk这类测试,记得关注被测试系统的cpu、io(网络/文件)、内存等使用情况。对于互联网的应用,特别要关注网络连接数。

    系统资源瓶颈

    • 稳定系统资源状态

    • 系统资源瓶颈

    峰值流量估算

    可根据历史日均压力、日最高压力等信息,估算出未来几年的日均以及日最高压力。再通过一些通用估算方法、如二八原则(80%的工作在20%时间内完成,相当于2小时完成一天8小时的工作量),将日压力转换成峰值压力。

    假设系统日均pv 8000w,一天按照4w秒算,8000w/4w=2000,平均大概2000QPS,按28原则算,峰值的qps则有2000*4=8000 QPS


    参考文章:https://www.jianshu.com/p/e7629acde434

    展开全文
  • 模型优化-梯度下降算法

    千次阅读 2019-05-31 21:39:11
    梯度下降(Gradient Descent)算法是机器学习中使用非常广泛的优化算法。...当加速度为零时,此时速度可能是最大,也可能是最小,这取决于函数曲线。 【步骤】: 随机取一自变量的值 x0x_0x0​; 对应该自变量...

    梯度下降(Gradient Descent)算法是机器学习中使用非常广泛的优化算法。当前流行的机器学习库或者深度学习库都会包括梯度下降算法的不同变种实现。

    【思想】:要找到某函数的最小值,最好的方法是沿着该函数的梯度方向探寻,例如物理学上的加速度与速度的关系。当加速度为零时,此时速度可能是最大,也有可能是最小,这取决于函数曲线。

    全局最小与局部极小

    【步骤】:

    1. 随机取一个自变量的值 x 0 x_0 x0
    2. 对应该自变量算出对应点的因变量值: f ( x 0 ) f(x_0) f(x0)
    3. 计算 f ( x 0 ) f(x_0) f(x0) 处目标函数 f(x) 的导数;
    4. f ( x 0 ) f(x_0) f(x0) 开始,沿着该处目标函数导数的方向,按一个指定的步长 α,向前“走一步”,走到的位置对应自变量取值为 x 1 x_1 x1。换言之, ∣ x 0 − x 1 ∣ / α = f ( x ) |x_0 - x_1| / α = f(x) x0x1/α=f(x) f ( x 0 ) f(x_0) f(x0) 处的斜率;
    5. 继续重复步骤 2 - 4,直至满足结束条件,退出迭代。

    梯度下降法作为机器学习中较常使用的优化算法,有三种不同的形式:批量梯度下降(Batch Gradient Descent)、随机梯度下降(Stochastic Gradient Descent)以及小批量梯度下降(Mini-Batch Gradient Descent)。其中小批量梯度下降法也常用在深度学习中,对模型进行训练。

    为了便于理解,我们以只有一个特征的线性回归模型作为案例,准备工作如下:

    %matplotlib inline
    import numpy as np
    from matplotlib import pyplot as plt
    
    
    # y = 5x + 2
    dataset = np.array([
        [1, 7],
        [2, 13],
        [3, 17],
        [4, 22],
        [5, 27],
        [6, 33],
        [7, 38],
        [8, 42],
        [9, 46],
        [10, 52]
    ])
    x = dataset[:, 0]
    y = dataset[:, 1]
    

    该线性回归的函数可设置为:
    f ( x i ; θ ) = w 1 x i + b f(x_i;\theta) = w_1 x_i + b f(xi;θ)=w1xi+b
    其中,w 为系数向量,b 为偏置,i = 1, 2, …, m 表示样本数,θ 表示所有要求的参数(w 和 b)。对应的目标函数即:
    J ( θ ) = 1 2 m ∑ i = 1 m ( f ( x i ; w ) − y i ) 2 J(\theta) = \frac{1}{2m}\sum_{i=1}^m(f(x_i;w) - y_i)^2 J(θ)=2m1i=1m(f(xi;w)yi)2

    通常我们会把 b 添加到 w 中,构成一个新的系数向量 w’,同时也相应扩充 x 使其变为 x’。
    w ′ T = [ w , b ] x ′ = [ x , 1 ] f ( x 1 ′ ; w ′ ) = w ′ x ′ w'^T = [w, b] \quad x' = [x, 1] \\ f(x_1';w') = w'x' wT=[w,b]x=[x,1]f(x1;w)=wx
    对于上述示例,只有一个特征,所以 w ′ T = [ w 1 , b ] w'^T = [w_1, b] wT=[w1,b]。此外,需要注意的是,$x_i$ 表示第 i 个样本, x i x^i xi 表示样本第 i 个特征。

    在开始具体讲述梯度下降算法之前,先介绍向量化概念。

    向量化

    向量化是去除代码中 for 循环的艺术,尤其当数据集非常大时,运行向量化是一个可以节省大量运行时间的关键技巧。我们仍然用上面所讲的例子来说明什么是向量化。

    在线性回归中,我们需要获得模型的输出值,即计算 f ( x ) = w T x + b f(x) = w^Tx + b f(x)=wTx+b,其中 w 和 x 都是列向量。假设此刻有一个拥有非常多特征的数据集,你想用非向量化方法去计算 f(x),则代码如下:

    f = 0
    for i in range(dataset_length):
        f += w[i] * x[i]
    f += b
    

    非向量化需要从数据集中获取每一条数据,并按照 f(x) 的计算公式逐一计算,然后将其累加。而向量化则通过矩阵乘法并行化处理,在此我们使用 numpy 的 dot() 函数。

    f = np.dot(w, x) + b
    

    为了证明向量化的计算开销比非向量化要小很多,可以运用下面的小例子来查看两种方式的计算时间。

    import numpy as np # 导入numpy库
    a = np.array([1,2,3,4]) # 创建一个数据a
    print(a)
    # [1 2 3 4]
    
    import time # 导入时间库
    a = np.random.rand(1000000)
    b = np.random.rand(1000000) # 通过round随机得到两个一百万维度的数组
    tic = time.time() # 现在测量一下当前时间
    
    # 向量化的版本
    c = np.dot(a,b)
    toc = time.time()
    print("Vectorized version:" + str(1000*(toc-tic)) +"ms") # 打印一下向量化的版本的时间
    
    # 继续增加非向量化的版本
    c = 0
    tic = time.time()
    for i in range(1000000):
        c += a[i]*b[i]
    toc = time.time()
    print(c)
    print("For loop:" + str(1000*(toc-tic)) + "ms") # 打印for循环的版本的时间
    

    最后的输出结果为:

    [1 2 3 4]
    Vectorized version:70.01662254333496ms
    249924.36248504242
    For loop:1096.3506698608398ms
    

    不同电脑的性能有所差异,最终获得的结果也不尽相同,但唯一不变的是向量化的计算时间要远小于非向量化的计算时间。因此,在后续的代码部分我们都将使用向量化的方式进行梯度计算。关于向量化的更多内容,可以去观看吴恩达老师的深度学习课程第一堂课第一周 传送门

    批量梯度下降

    批量梯度下降法是最原始的形式,在每一次迭代时使用所有样本来进行梯度的更新。

    【步骤】:

    1. 对目标函数求偏导。
      ∂ J ( w ′ ) ∂ w ′ = 1 m ∑ i = 1 m ( f ( x i ′ ; θ ) − y i ) x ′ j \frac{\partial J(w')}{\partial w'} = \frac{1}{m}\sum_{i=1}^m(f(x_i';\theta) - y_i)x'^j wJ(w)=m1i=1m(f(xi;θ)yi)xj
      其中,i = 1, 2, …, m 表示样本数,j = 0, 1 表示特征数。
    2. 每次迭代对参数进行更新:
      w j : = w j − α ∂ J ( w ′ ) ∂ w ′ = 1 m ∑ i = 1 m ( f ( x i ′ ; θ ) − y i ) x ′ j w_j := w_j - \alpha\frac{\partial J(w')}{\partial w'} = \frac{1}{m}\sum_{i=1}^m(f(x_i';\theta) - y_i)x'^j wj:=wjαwJ(w)=m1i=1m(f(xi;θ)yi)xj

    【代码实现】:

    def BatchGradientDescent(x, y, step=0.001, iter_count=500):
        length, features = x.shape
        
        # 整合系数向量 w' 和新样本集 x'
        data = np.column_stack((x, np.ones((length, 1))))
        w = np.zeros((features + 1, 1))
        
        # 开始迭代
        for i in range(iter_count):
            new_w = w.copy()
            for feature in range(features + 1):
                new_w[feature] = np.sum((np.dot(data, w) - y) * data[:, feature]) / length
            w -= step * new_w        
        return w
    
    print(BatchGradientDescent(x, y, iter_count=500))
    # 输出:
    array([[5.2272],
           [0.9504]])
    

    【优点】:

    • 一次迭代是对所有样本进行计算,此时利用矩阵进行操作,实现了并行。
    • 由全数据集确定的方向能够更好地代表样本总体,从而更准确地朝向极值所在的方向。当目标函数为凸函数时,BGD一定能够得到全局最优。

    【缺点】:

    • 当数据集 m 很大时,每迭代一步都需要对所有样本进行计算,训练过程会很慢。
    • 内存容量可能支撑不了如此巨大的数据集。

    随机梯度下降

    随机梯度下降法不同于批量梯度下降,每次迭代使用一个样本来对参数进行更新,使得训练速度加快。

    【代码实现】:

    def StochasticGradientDescent(x, y, step=0.001, iter_count=500):
        length, features = x.shape
        
        # 整合系数向量 w' 和新样本集 x'
        data = np.column_stack((x, np.ones((length, 1))))
        w = np.zeros((features + 1, 1))
    
        # 开始迭代
        for i in range(iter_count):
            # 随机选择一个样本
            random_ind = np.random.randint(length)
            new_w = w.copy()
            for feature in range(features + 1):                        
                new_w[feature] = (np.dot(data[random_ind:random_ind + 1], w) - y[random_ind]) * data[random_ind, feature] / length
            w -= step * new_w        
        return w
        
    
    print(StochasticGradientDescent(x, y, iter_count=1000))
    # 输出:
    array([[5.09770338],
           [0.77370206]])
    

    除了随机选择数据集中的样本之外,我们也可以按照数据集中的样本顺序,依次选择样本。不过样本的特定顺序可能会给算法收敛带来一定的影响,因此推荐随机选取样本。

    def StochasticGradientDescent(x, y, step=0.001, iter_count=500):
        length, features = x.shape
        
        # 整合系数向量 w' 和新样本集 x'
        data = np.column_stack((x, np.ones((length, 1))))
        w = np.zeros((features + 1, 1))
        random_ind = 0
        
        # 开始迭代
        for i in range(iter_count):
            random_ind = (random_ind + 1) % length
            new_w = w.copy()
            for feature in range(features + 1):                        
                new_w[feature] = (np.dot(data[random_ind:random_ind + 1], w) - y[random_ind]) * data[random_ind, feature] / length
            w -= step * new_w        
        return w
    

    【优点】:由于不是全部训练数据上的损失函数,而是在每轮迭代中,随机优化某一条训练数据上的损失函数,这样每一轮参数的更新速度大大加快。

    假设我们现在有 30w 个样本,对于批量梯度下降而言,每次迭代需要计算 30w 个样本才能对参数进行一次更新。而对于随机梯度下降而言,参数每次更新只需要一个样本。因此,若使用这 30w 个样本进行参数更新,则参数会被更新 30w 次。在这期间,随机梯度下降就能保证收敛到一个合适的最小值上。

    【缺点】:

    • 准确度下降:随机梯度下降仅考虑单个样本的损失函数,容易受噪声数据的影响,因此准确度无法与批量梯度下降相比。
    • 可能会收敛到局部最优:由于单个样本不能代表全体样本的趋势,尤其随机选取的样本恰好是噪声,则很有可能偏离最优值。
    • 不易于并行实现:因为每次迭代过程中只计算一个样本的损失函数,没能利用向量化所带来的计算优势。

    山谷震荡与鞍部停滞

    不论是机器学习还是深度学习的优化问题,存在众多局部极小值陷阱。这些陷阱对于批量梯度下降、小批量梯度下降以及随机梯度下降都是普遍存在的。但对于随机梯度下降而言,可怕的不是落在局部极小值陷阱,而是山谷和鞍部这两类地形。

    【山谷震荡】:山谷顾名思义就是狭长的山间小道,左右两边是峭壁,见下图。

    梯度下降示例

    在梯度下降算法中,下降最快的方向始终是垂直等高线并指向谷底的方向。在山谷这一类地形中,很容易从山谷的一端撞向山谷的另一端,并且随机梯度下降粗糙的梯度估计使得它在两山壁之间来回反弹震荡的概率增加,不能沿山道方向迅速下降,导致收敛不稳定和收敛速度慢。

    特征归一化方法可以有效地减少山谷地形,从而削减山谷震荡现象发生的可能。

    【鞍部停滞】:鞍部的形状像一个马鞍,一端上升,另一端下降,而中心区域是一片近乎水平的平地,可以想象成在一座峰峦叠错连绵不绝的山脉中突然出现了一片平原。

    鞍部陷阱

    随机梯度下降来到鞍部,由于坡度不明显,且单个样本的梯度方向不一定指向谷底,因此非常容易陷在鞍部,缓慢而无方向地乱走。若鞍部范围较广,随机梯度下降很有可能就困在此处,无法走出鞍部范围。

    【解决方案】:保持下降的惯性、加大对环境的感知,具体做法请参考模型优化的其他方法。

    小批量梯度下降

    小批量梯度下降是对批量梯度下降以及随机梯度下降的一个折中方案,其思想是每次迭代使用 batch_size 数量的样本来对参数进行更新。

    【代码实现】:

    def MiniBatchGradientDescent(x, y, step=0.001, iter_count=500, batch_size=4):
        length, features = x.shape
        
        # 整合系数向量 w' 和新样本集 x'
        data = np.column_stack((x, np.ones((length, 1))))
        # 消除样本顺序带来的影响
        np.random.shuffle(data)
        w = np.zeros((features + 1, 1))
        start, end = 0, batch_size
        
        # 开始迭代
        for i in range(iter_count):        
            new_w = w.copy()
            for feature in range(features + 1):
                new_w[feature] = np.sum((np.dot(data[start:end], w) - y[start:end]) * data[start:end, feature]) / length
            w -= step * new_w
            start = (start + batch_size) % length
            end = (end + batch_size) % length
        return w
    
    
    print(MiniBatchGradientDescent(x, y))
    # 输出:
    array([[5.25089298],
           [1.09047361]])
    

    有的时候,数据的特定顺序会给算法收敛带来影响,因此一般会在每次遍历训练数据之前,先对所有的数据进行随机排序。

    【优点】:

    • 向量化能够使得计算一个 batch 数量样本所需的时间与计算单个样本所需的时间相差无几。
    • 每次使用一个 batch 可以大大减小随机梯度下降收敛所需要的迭代次数,同时可以使收敛到结果更加接近梯度下降的效果。

    对比批量梯度下降和随机梯度下降,二者都不需要考虑样本的数量,批量梯度下降直接选用全部样本,而随机梯度下降则随机选取一个样本。但对于小批量梯度下降而言,batch_size 该如何设置,是一个问题。

    结合小批量梯度下降算法的优点,我们来谈论下 batch_size 的选择。

    【增大 batch_size】:

    • 可以充分发挥向量化的作用,不仅可以提高内存利用率,同时提升计算性能。
    • batch_size 越大,则遍历全部样本(epoch)所需 的迭代次数也越少,对于相同数据量的处理速度进一步加快。
    • batch_size 越大,则选取的样本数也越多,越能代表整个数据集,那么根据梯度确定的下降方向也越准确。需要注意的是,当 batch_size 增大到一定程度后,下降方向基本不会再发生变化。

    但需要注意的是,我们也不能盲目增大 batch_size,一旦 batch_size 过大,仍然会面临批量梯度下降的问题——内存容量可能撑不住。此外,跑完一次 epoch 所需的迭代次数减少,相应的参数更新次数也变少,对准确度也会造成一定的影响。

    一般来说,batch_size 取 2 的幂次时能充分利用矩阵运算操作,所以可以在 2 的幂次中挑选最优的取值,例如 32、64、128、256 等。

    三类梯度下降算法的比较

    通过上述的分别介绍,批量梯度下降、随机梯度下降以及小批量梯度下降的计算公式都是相同的,唯一的区别就是在每轮迭代中参与的样本数量。

    • 批量梯度下降:全部样本;
    • 随机梯度下降:单个样本;
    • 小批量梯度下降:一个 batch 样本。

    在性能以及准确性方面,小批量梯度下降综合了批量梯度下降和随机梯度下降的优点,从而缓解了两者的缺陷。批量梯度下降计算开销大,随机梯度计算快但准确率不够高。下批量梯度下降通过设置 batch,在计算速度方面不逊色于随机梯度下降,并且迭代次数比随机梯度要少,总的来说反而比随机梯度更快收敛。此外,小批量梯度下降相比随机梯度下降准确率更高,因为它选取一个 batch 的样本,可以在一定程度上减少噪声的影响。

    三类梯度下降算法的收敛过程图

    上图选自博客 批量梯度下降(BGD)、随机梯度下降(SGD)以及小批量梯度下降(MBGD)的理解,若构成侵权,则立即删除。

    这三类算法的相关代码都可以在该传送门中获得。

    讲完了这三类梯度下降算法,我们再来讨论下在梯度下降算法中出现的超参数 α、迭代终止条件以及算法所遇到的难点。

    超参数 α

    超参数 α 又叫做步长,用于确定找到最小值点而尝试在目标函数上前进的步伐到底走多大。如果该参数设置的大小不合适,则会导致最终无法找到最小值点。

    比如下面左图就是因为步幅太大,几个迭代后反而取值越来越大。修改成右图那样的小步伐就可以顺利找到最低点。

    large stepssmall steps

    不过大步伐也不是没有优点。步伐越大,每一次前进得越多。步伐太小,虽然不容易“跨过”极值点,但需要的迭代次数也多,相应需要的运算时间也就越多。

    为了平衡大小步伐的优缺点,也可以在一开始的时候先大步走,当所到达点斜率逐渐下降——函数梯度下降的趋势越来越缓和——以后,逐步调整,缩小步伐。比如下图这样:

    优化后的步伐选择

    算法难点

    即使步伐合适,也不一定能够找到最小值点。如果目标函数有多个极小值点(多个向下的“弯儿”),那么如果开始位置不妥,很可能导致最终是走到了一个局部极小值就无法前进了。

    梯度下降算法的难点

    【解决方案】:如果目标函数不能确定只有一个极小值,而获得的模型结果又不令人满意时,就该考虑是否是在学习的过程中,优化算法进入了局部而非全局最小值。这种情况下,可以尝试几个不同的起始点。甚至尝试一下大步长,说不定反而能够跨出局部最小值点所在的凸域。

    迭代结束的条件

    梯度下降法(梯度上升法应该也适用)迭代结束的条件,常用的有两种:

    • 定义一个合理的阈值,当两次迭代之间的差值小于该阈值时,迭代结束。
    • 设置一个大概的迭代步数,比如 1000 或 500,梯度下降法最终的迭代肯定会收敛,只要达到相应迭代次数,多了也没关系。因为迭代次数多了后,在到达极值点时,函数对变量的导数已近乎为 0,即使过了极值点,导数就变为正数了,之前的导数为负数。这个时候,变量 x 的值减去步长与导数的乘积反倒变小了。所以即使步数多了,结果也基本上就在极值点处左右徘徊,几乎等于极值点,因此没有问题。

    参考

    展开全文
  • 一、我们可能从来没有找到过...很多人都一种看法,就是“局部最优是神经网络优化的主要难点”。这来源于一维优化问题的直观想象。在单变量的情形下,优化问题最直观的困难就是很多局部极值,如 人们直观...

     

    一、 我们可能从来没有找到过“局部最优”,更别说全局最优了。

    作者:五楼whearer
    链接:https://www.zhihu.com/question/68109802/answer/262143638

    深度神经网络“容易收敛到局部最优”,很可能是一种想象,实际情况是,我们可能从来没有找到过“局部最优”,更别说全局最优了。

    很多人都有一种看法,就是“局部最优是神经网络优化的主要难点”。这来源于一维优化问题的直观想象。在单变量的情形下,优化问题最直观的困难就是有很多局部极值,如

    人们直观的想象,高维的时候这样的局部极值会更多,指数级的增加,于是优化到全局最优就更难了。然而单变量到多变量一个重要差异是,单变量的时候,Hessian矩阵只有一个特征值,于是无论这个特征值的符号正负,一个临界点都是局部极值。但是在多变量的时候,Hessian有多个不同的特征值,这时候各个特征值就可能会有更复杂的分布,如有正有负的不定型和有多个退化特征值(零特征值)的半定型

     

    在后两种情况下,是很难找到局部极值的,更别说全局最优了。

     

    前面很多回答说了,现在看来神经网络的训练的困难主要是鞍点的问题。在实际中,我们很可能也从来没有真的遇到过局部极值。Bengio组这篇文章Eigenvalues of the Hessian in Deep Learning里面的实验研究给出以下的结论:

    • Training stops at a point that has a small gradient. The norm of the gradient is not zero, therefore it does not, technically speaking, converge to a critical point.
    • There are still negative eigenvalues even when they are small in magnitude.

     

    另一方面,一个好消息是,即使有局部极值,具有较差的loss的局部极值的吸引域也是很小Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

    For the landscape of loss function for deep networks, the volume of basin of attraction of good minima dominates over that of poor minima, which guarantees optimization methods with random initialization to converge to good minima.

    所以,很可能我们实际上是在“什么也没找到”的情况下就停止了训练,然后拿到测试集上试试,“咦,效果还不错”。

     

    补充说明,这些都是实验研究结果理论方面,在各种假设下,深度神经网络的Landscape 的鞍点数目指数增加,而具有较差loss的局部极值非常少。

    SGD收敛性的很多结论都是经验性的。在loss function landscape是退化的情况下loss 停滞在某个数值上训练不动的原因,很大程度上不是因为停在某个点不动了,是停在某个区域不动了。over-parameterized的神经网络有大片的平坦区域,这里一阶二阶乃至更高阶都是退化的,甚至有实验说这样的区域时dominant的(虽然我觉得那个结论有点大)。这时候可以说反复迭代也没啥改进,但是这反过来说算法无需太多迭代就能找到这样一个平坦区域,这里loss 和其中的local minima (可能也是退化的)相差不大,是不是真的找到local minima也没那么重要了。

     

    相关的回答:

    神经网络的训练可以采用二阶优化方法吗(如Newton, Quasi Newton)?

     

    二、真的结束于最优点吗?


    链接:https://www.zhihu.com/question/68109802/answer/263503269
     

    我们知道,在局部最优点附近,各个维度的导数都接近0,而我们训练模型最常用的梯度下降法又是基于导数与步长的乘积去更新模型参数的,因此一旦陷入了局部最优点,就像掉进了一口井,你是无法直着跳出去的,你只有连续不间断的依托四周的井壁努力向上爬才有可能爬出去。更何况梯度下降法的每一步对梯度正确的估计都在试图让你坠入井底,因此势必要对梯度“估计错很多次”才可能侥幸逃出去。那么从数学上看,什么才是局部最优点呢?

    这个问题看似很白痴,很多人会说“局部最优点不就是在loss曲面上某个一阶导数为0的点嘛”。这就不准确啦,比如下面这个马鞍形状的中间的那个点:

    (图片来自《deep learning》)

    显然这个点也是(一阶)导数为0,但是肯定不是最优点。事实上,这个点就是我们常说的鞍点

    显然,只用一阶导数是难以区分最优点和鞍点的。

    我们想一下,最优点和鞍点的区别不就在于其在各个维度是否都是最低点嘛~只要某个一阶导数为0的点在某个维度上是最高点而不是最低点,那它就是鞍点。而区分最高点和最低点当然就是用二阶导数(斜率从负变正的过程当然就是“下凸”,即斜率的导数大于0,即二阶导数大于0。反之则为“上凹”,二阶导数小于0)。也就是说,若某个一阶导数为0的点在至少一个方向上的二阶导数小于0,那它就是鞍点啦

    那么二阶导数大于0和小于0的概率各是多少呢?由于我们并没有先验知识,因此按照最大熵原理,我们认为二阶导数大于和小于0的概率均为0.5!

    那么对于一个有n个参数的机器学习/深度学习模型,“loss曲面”即位于n+1维空间(loss值为纵轴,n个参数为n个横轴)。在这个空间里,如果我们通过梯度下降法一路下滑终于滑到了一个各方向导数均为0的点,那么它为局部最优点的概率即[公式][公式] ,为鞍点的概率为 [公式] ,显然,当模型参数稍微一多,即n稍微一大,就会发现这个点为鞍点的概率会远大于局部最优点!

    好吧我再啰嗦的举个栗子,已经反应过来的同学可以跳过这个栗子:

    假设我们的模型有100个参数(实际深度学习模型中一般会远大于100),那么某一阶导数为0的点为局部最优点的概率为约为 [公式] ,而为鞍点的概率则为 [公式] 。就算我们的模型在训练时使用了特别厉害的“超级梯度下降法”,它可以每走一步都恰好踩在一个一阶导数为0的点上,那么从数学期望上来看,我们需要走10^31步才行。而实际的projects中,哪怕数据集规模为千万级,我们分了100万个batches,然后要迭代100次,那也仅仅是走了 [公式] 步,你真的觉得运气可以辣么好的走到局部最优点上去吗?所以实际中,当我们的深度学习模型收敛时,几乎没有必要认为它收敛到了一个局部最优点,这完全等同于杞人忧天。

    也就是说,如果最后模型确实在梯度下降法的指引下收敛到了一个导数为0的点,那这个点几乎可以肯定就是一个鞍点。

    如果我们的模型真的收敛到鞍点上了,会很可怕吗?

    这就又回到了文章开头的那副马鞍状的图。

    显然,站在马鞍中央的时候,虽然很难翻过两边的山坡,但是往前或者往后随便走一步就能摔下马鞍!而在文章《batch size》中小夕讲过,我们默认使用的mini-batch梯度下降法本身就是有噪声的梯度估计,哪怕我们位于梯度为0的点,也经常在某个mini-batch下的估计把它估计偏了,导致往前或者往后挪了一步摔下马鞍,也就是mini-batch的梯度下降法使得模型很容易逃离特征空间中的鞍点。

    那么问题来了,既然局部最优点很难踩到,鞍点也很容易逃离出去,那么

    为什么我们的模型看起来是收敛了呢?

    初学者可能会说 “诶诶,会不会是学习率太大了,导致在“鞍点”附近震荡?” 首先,鞍点不像最优点那样容易震荡,而且哪怕你不断的减小学习率继续让模型收敛,大部分时候你这时计算output层或者后几层的梯度向量的长度时往往会发现它依然离0很遥远!(这句话是有实验支撑的,不过那篇论文我暂时没记起来,找到时贴出来)说明大部分时候收敛到的并不是鞍点。

    那会不会踩到的鞍点太多,虽然前面的鞍点都轻松逃逸了,但是最后恰好收敛到一个跳不下去的鞍点身上了?

    这倒是有可能,不排除有一些“马鞍面”特别平坦的鞍点区域,当模型陷入这种鞍点上时,由于计算出的梯度非常小,导致要连续迭代非常多次才可能慢慢移开这个鞍点,事实上大部分工程情况下,没等它移开的时候我们就已经默认为模型收敛、训练结束了,实际上人家模型还在努力逃离鞍点中呢。

    不过话说回来,虽然高维空间中的鞍点数量远远大于最优点,而且鞍点数量随着特征空间维度增高而指数级增长,但是鞍点的数量在整个空间中又是微不足道的:按前面的假设,假设在某个维度上随机一跳有10%的概率踩到导数为0的点,那么我们在101维的空间中的一步恰好踩到这个点上的概率为10^-100,也就是说在101维空间里随机乱跳的时候,有10^-100的可能性踩到鞍点身上。因此,即使有难以逃离的鞍点,即使我们的优化算法在努力向附近的鞍点靠拢,那么被我们正好踩到那些难以逃离的特殊鞍点的概率也是非常小的。

    所以更令人信服的是,在高维空间里(深度学习问题上)真正可怕的不是局部最优也不是鞍点问题,而是一些特殊地形。比如大面积的平坦区域:

    (图片来自《deep learning》)

    在平坦区域,虽然导数不为0但是却不大。虽然是在不断下降但是路程却非常长。对于优化算法来说,它需要走很多很多步才有可能走过这一片平坦区域。甚至在这段地形的二阶导数过于特殊的情况下,一阶优化算法走无穷多步也走不出去(设想一下,如果终点在一米外,但是你第一次走0.5米,后续每一步都是前一步的一半长度,那么你永远也走不到面前的一米终点处)。

    所以相比于栽到最优点和鞍点上,优化算法更有可能载到这种类似平坦区的地形中(如果这个平坦区又是“高原地带”,即loss值很高的地带,那么恭喜你悲剧了)。更糟糕的是,由于高维地形难以可视化,还有很多更复杂的未知地形会导致假收敛,一旦陷入到这些危险地形中,几乎是无解的。

    所以说,在深度学习中,与其担忧陷入局部最优点怎么跳出来,更不如去考虑数据集要怎么做才能让网络更好学习,以及网络该怎么设计才能更好的捕获pattern,网络该怎么训练才能学到我们想让它学习的知识。

     

     

    三、 和泛化能力的关系


    链接:https://www.zhihu.com/question/68109802/answer/264008642

     

    很多回答已经从梯度的角度深入分析了收敛性,在这里我补充一下这个问题和泛化能力的关系,解释一下为什么没有收敛也不妨碍应用。

    tl;dr:首先在实际的训练中,由于SGD以及dropout等regularization方法的使用,
    最后模型基本不可能收敛于某一个点,它只是处在了一个比较平坦的区域。其次,神经网络的神奇之处在于,在这个平坦的区域内随便选一个点(即网络参数)都会具有很好的泛化能力,且这个平坦区域越大,泛化能力越好,从而可以在测试集上取得比较好的结果。这也是神经网络应用广泛的原因。

    1. 最后不会收敛到某一点。sgd和dropout等都相当于是在模型中注入了具有随机性的噪声,所以基本没有可能存在一个点,可以在这些噪声的干扰下得到零梯度。所以最终稳定的模型应该是处在一个区域内,这些噪声的干扰不会让模型脱离这个区域。

    2. 没有收敛并不是坏事。尽管模型最后并没有收敛到某一个点,我们仍将最后的稳定位置称为一个minima,在这里minima指的并不是点,而是一个区域。在这个区域里面,loss surface是基本平坦的,且低于周围的位置,看起来像是一个盆地。在[1]里面,作者指出神经网络的loss surface上会有很多这种minima,使用sgd得到的minima的函数值通常都比较小。这和我们的经验是相符合的:配合各种训练方法,随机初始化的神经网络训练到最后的training loss都会比较小。特别地,[1]里面提到全局最优的参数往往意味着严重过拟合(可以从数据存在噪声的角度理解这个结论)。在[2]以及它引用的一些文献中,我们可以看到,这些小“盆地”的面积和网络泛化能力强相关。通常,面积大的盆地(flat minima)泛化能力好(可以从loss对权重噪声的稳定性上理解)。

     

    展开全文
  • C++面试常用知识总结——基础篇

    万次阅读 多人点赞 2019-07-15 18:13:04
    文章目录1、算法1.1、排序1.1.1、快排1.1.2、归并1.1.3、稳定性高效率高的排序1.2、广度优先算法和深度优先算法1.3、BFPRT算法1.4、二叉树1.4.1、遍历方式2、数据库2.1、画ER图2.2、如何备份2.3、加快数据库查询有几...

    文章目录

    1、算法

    1.1、排序

    思想和写法,要会敲代码,最好会手撕代码

    1.1.1、快排

    一定要会手撕代码、思想要清楚。
    实质是分治法,选择一个基准来分,这个分的过程是partition,它是快排的灵魂。基于以上特点,用递归的方式来描述。

    #include <iostream>
    using namespace std;
    
    int partition(int arr[], int left, int right) {
        int key = arr[right];
        int k = left;
        for(int i = left; i < right; ++i) {
            if(arr[i] < key) {
                swap(arr[i], arr[k++]);
            }
        }
        swap(arr[right], arr[k]);
        return k;
    }
    
    void quicksort(int arr[], int left, int right) {
        if(left < right) {
            int i = partition(arr, left, right);
            quicksort(arr, left, i-1);
            quicksort(arr, i+1, right);
        }
        return;
    }
    
    int main() {
        int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
        for(int i = 0; i < 10; ++i)
            cout << arr[i] << " ";
        cout << endl;
        quicksort(arr, 0, 9);
        for(int i = 0; i < 10; ++i)
            cout << arr[i] << " ";
        return 0;
    }
    

    1.1.2、归并

    一定要会手撕代码、思想要清楚。
    先递归划分子问题,然后合并结果

    #include <iostream>
    #include <vector>
    using namespace std;
    
    void merge(vector<int>& A, vector<int> L, vector<int> R) {
        int l = L.size();
        int r = R.size();
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < l && j < r) {
            if(L[i] < R[j]) {
                A[k++] = L[i++];
            } else {
                A[k++] = R[j++];
            }
        }
        while(i < l) A[k++] = L[i++];
        while(j < r) A[k++] = R[j++];
    }
    
    void mergesort(vector<int>& arr) {
        int n = arr.size();
        if(n < 2) return;
        int mid = n/2;
        int i;
        vector<int> L(mid);
        vector<int> R(n - mid);
        for(i = 0; i < mid; ++i) {
            L[i] = arr[i];
        }
        for(;i < n; ++i) {
            R[i-mid] = arr[i];
        }
        mergesort(L);
        mergesort(R);
        merge(arr, L, R);
    }
    
    int main() {
        int arr[10] = {2, 5, 4, 3, 1, 6, 9, 7, 8, 10};
        vector<int> Arr(arr, arr + 10);
        for(int i = 0; i < 10; ++i)
            cout << Arr[i] << " ";
        cout << endl;
        mergesort(Arr);
        for(int i = 0; i < 10; ++i)
            cout << Arr[i] << " ";
        return 0;
    }
    

    1.1.3、稳定性、效率

    从平均时间来看,快速排序是效率最高的,但快速排序在最坏情况下的时间性能不如堆排序和归并排序

    稳定性算法:基数排序,插入排序,冒泡排序,归并排序
    不稳定性算法:希尔排序,快速排序,选择排序,堆排序,桶排序

    时间复杂度:评估执行程序所需的时间,可以估算出程序对处理器的使用程度
    空间复杂度:评估执行程序所需的存储空间,可以估算出程序对计算机内存的使用程度
    在这里插入图片描述

    1.2、BFPRT算法

    由5位外国人(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan)提出,并以他们的名首字母命名,称为 中位数的中位数算法,又称 线性查找算法。

    • 将n个元素每5个一组,分成n/5(上界)组。
    • 取出每一组的中位数,任意排序方法,比如插入排序。
    • 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。
    • 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。
    • 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k小的元素。
    • 终止条件:n=1时,返回的即是i小元素。

    结合不同考题侧面的去考(经典:选出第k大(第k小)的元素,)

    1.3、二叉树

    1.3.1、广度优先算法BFS和深度优先算法DFS

    BFS:使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。类似层次遍历
    DFS:一直往深处走,直到找到解或者走不下去为止(使用栈保存未被检测的结点,结点按照深度优先的次序被访问并依次被压入栈中,并以相反的次序出栈进行新的检测),类似先序遍历。

    总结:最短路径用广度优先搜索BFS,全部解用深度优先搜索DFS。

    结合不同考题侧面的去考

    1.3.2、遍历方式

    • 前序遍历:先访问根节点,再遍历左子树,然后再遍历右子树。总的来说是根—左—右
    • 中序遍历:先中序访问左子树,然后访问根,最后访问右子树。总的来说是左—根—右
    • 后序遍历:先后序访问左子树,然后访问右子树,最后访问根。总的来说是左—右—根
    • 层次遍历(宽度优先遍历):利用队列,依次将根,左子树,右子树存入队列,按照队列的先进先出规则来实现层次遍历。
    • 深度优先遍历:利用栈,先将根入栈,再将根出栈,并将根的右子树,左子树存入栈,按照栈的先进后出规则来实现深度优先遍历。

    2、数据库

    2.1、画E-R图

    在这里插入图片描述

    2.2、备份

    2.2.1、备份类型

    • 完全备份:指的是备份整个数据集(即整个数据库)
    • 部分备份:指的是备份部分数据集(例如: 只备份一个表)
    • 增量备份:指的是备份自上一次备份以来(增量或完全)以来变化的数据。特点: 节约空间、还原麻烦
    • 差异备份:指的是备份自上一次完全备份以来变化的数据。特点: 浪费空间、还原比增量备份简单

    2.2.2、备份方式

    • 热备份:指的是当数据库进行备份时, 数据库的读写操作均不是受影响
    • 温备份:指的是当数据库进行备份时, 数据库的读操作可以执行, 但是不能执行写操作
    • 冷备份:指的是当数据库进行备份时, 数据库不能进行读写操作, 即数据库要下线

    2.2.3、Mysql如何备份

    • 直接拷贝数据库
    • mysqldump命令
    • mysqlhotcopy命令
    • 使用文件系统快照(LVM等)进行
    • Xtrabackup开源的热备份软件

    2.3、加快数据库查询有几种方式

    • 选取最适用的字段属性:申请过大字段属性增加了不必要的空间
    • 使用连接(JOIN)来代替子查询(Sub-Queries):不需要在内存中创建临时表
    • 使用联合(UNION)来代替手动创建的临时表
    • 使用事务
    • 锁定表:可以维护数据的完整性
    • 使用外键:锁定表不能保证数据的关联性。这个时候我们就可以使用外键
    • 使用索引:根据业务建立在JOIN,WHERE判断和ORDERBY排序的字段上
    • 优化的查询语句,例如LIKE关键字(这种通配符是以牺牲系统性能为代价的)

    2.4、建立索引

    2.4.1、建立索引如何加快查询

    因为索引是一种优化查询的数据结构,比如MySQL中的索引是B+树实现的,而B+树就是一种数据结构,可以优化查询速度,可以利用索引快速查找数据,所以能优化查询!

    2.4.2、表结构中字段是否添加索引判断依据是什么?

    字段是否是查询条件或者是排序条件。适合于查询多而添删改少的表。

    2.4.3、是否将所有的字段都添加索引,来加快查询?

    不可以的

    • 索引是有大量数据的时候才建立的,没有大量数据反而会浪费时间,因为索引是使用二叉树建立.
    • 当一个系统查询比较频繁,而新建,修改等操作比较少时,可以创建索引,这样查询的速度会比以前快很多,同时也带来弊端,就是新建或修改等操作时,比没有索引或没有建立覆盖索引时的要慢。
    • 索引并不是越多越好,太多索引会占用很多的索引表空间,甚至比存储一条记录更多。
      对于需要频繁新增记录的表,最好不要创建索引,没有索引的表,执行insert、append都很快,有了索引以后,会多一个维护索引的操作,一些大表可能导致insert 速度非常慢。

    2.5、内、外链接,左、右链接

    数据库分为:内连接、外连接、交叉连接

    2.5.1、内连接

    有两种,显式的和隐式的,返回连接表中符合连接条件和查询条件的数据行
    在这里插入图片描述

    • 显式
      在这里插入图片描述
    • 隐式
      在这里插入图片描述

    2.5.2、外连接(OUTER JOIN)

    • 左外连接(LEFT OUTER JOIN或LEFT JOIN)
    • 右外连接(RIGHT OUTER JOIN或RIGHT JOIN)
    • 全外连接(FULL OUTER JOIN或FULL JOIN)

    2.5.3、交叉连接(CROSS JOIN)

    没有WHERE 子句,它返回连接表中所有数据行的笛卡尔积

    2.6、事务(transaction)

    2.6.1、特点、特性

    ①原子性:事务作为一个整体被执行,要么全部执行,要么全部不执行。
    ②一致性:保证数据库的状态从一个一致状态转变为另一个一致状态。
    ③隔离性:多个事务并发执行时,一个事务的执行并不影响其他事务的执行。
    ④持久性:一个事务一旦提交,对数据库的修改应该永久保存。

    2.6.2、并发访问问题(由隔离性引起)

    ①脏读:B事务读取到了A事务尚未提交的数据。
    ②不可重复读:一个事务中,两次读取的数据的内容不一致。
    ③幻读/虚读:一个事务中,两次读取的数据的数量不一致。

    2.6.3、隔离级别

    读未提交、读已提交、可重复读和序列化
    ①读取尚未提交的数据:哪个问题都不能解决。
    ②读取已经提交的数据:可以解决脏读。(oracle默认)
    ③重读读取:可以解决脏读,不可重复读。(mysql默认)
    ④串行化:都可以解决。—相当于锁表,一般没人用,效率太低。

    3、网络

    3.1、http、https的区别

    • https协议需要到ca申请证书,一般免费证书较少,因而需要一定费用。
    • http是超文本传输协议,信息是明文传输,https则是具有安全性的ssl加密传输协议。
    • http和https使用的是完全不同的连接方式,用的端口也不一样,前者是80,后者是443。
    • http的连接很简单,是无状态的;HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,比http协议安全。

    3.1.1、Https的优点

    • 使用Https协议可认证用户和服务器,确保数据发送到正确的客户机和服务器。
    • Https协议是由SSL+Http协议构建的可进行加密传输、身份认证的网络协议,要比http协议安全,可防止数据在传输过程中不被窃取、修改,确保数据的完整性。
    • Https是现行架构下最安全的解决方案,虽然不是绝对安全,但它大幅增加了中间人攻击的成本。

    3.1.2、Https的缺点(对比优点)

    • Https协议握手阶段比较费时,会使页面的加载时间延长近
    • Https连接缓存不如Http高效,会增加数据开销,甚至已有的安全措施也会因此而受到影响
    • SSL证书通常需要绑定IP,不能在同一IP上绑定多个域名,IPv4资源不可能支撑这个消耗
    • Https协议的加密范围也比较有限。最关键的,SSL证书的信用链体系并不安全,特别是在某些国家可以控制CA根证书的情况下,中间人攻击一样可行

    3.2、tcp/ip的三次握手

    3.2.1、讲述过程

    在这里插入图片描述

    • 第一次握手:Client将标志位SYN置为1(表示要发起一个连接),随机产生一个值seq=J,并将该数据包发送给Server,Client进入SYN_SENT状态,等待Server确认。
    • 第二次握手:Server收到数据包后由标志位SYN=1知道Client请求建立连接,Server将标志位SYN和ACK都置为1,ack=J+1,随机产生一个值seq=K,并将该数据包发送给Client以确认连接请求,Server进入SYN_RCVD状态。
    • 第三次握手:Client收到确认后,检查ack是否为J+1,ACK是否为1,如果正确则将标志位ACK置为1,ack=K+1,并将该数据包发送给Server,Server检查ack是否为K+1,ACK是否为1,如果正确则连接建立成功,Client和Server进入ESTABLISHED状态,完成三次握手,随后Client与Server之间可以开始传输数据了。

    3.2.2、为什么是三次握手不是两次不是四次

    三次握手的最主要目的是确认双方都有收发数据的能力。三次握手完成两个重要的功能,既要双方做好发送数据的准备工作(双方都知道彼此已准备好),也要允许双方就初始序列号进行协商,这个序列号在握手过程中被发送和确认。

    • 第一次: A发给B。证明A有发消息的能力。
    • 第二次: B收到并发消息给A。证明B有收消息,并且有发消息的能力。
    • 第三次: A收到B消息。证明A有收消息的能力。

    二次握手达不到目的,四次多余。

    3.3、tcp/ip的四次挥手

    • 第一次挥手:首先,客户端发送一个FIN,用来关闭客户端到服务器的数据传送,然后等待服务器的确认。其中终止标志位FIN=1,序列号seq=u。
    • 第二次挥手:服务器收到这个FIN,它发送一个ACK,确认ack为收到的序号加一。
    • 第三次挥手:关闭服务器到客户端的连接,发送一个FIN给客户端。
    • 第四次挥手:客户端收到FIN后,并发回一个ACK报文确认,并将确认序号seq设置为收到序号加一。首先进行关闭的一方将执行主动关闭,而另一方执行被动关闭。

    3.3.1、为什么是四次挥手

    双方关闭连接要经过双方都同意。所以,首先是客服端给服务器发送FIN,要求关闭连接,服务器收到后会发送一个ACK进行确认。服务器然后再发送一个FIN,客户端发送ACK确认,并进入TIME_WAIT状态。等待2MSL后自动关闭。

    3.3.2、为什么需要2MSL时间?

    首先,MSL即Maximum Segment Lifetime,就是最大报文生存时间,是任何报文在网络上的存在的最长时间,超过这个时间报文将被丢弃。《TCP/IP详解》中是这样描述的:MSL是任何报文段被丢弃前在网络内的最长时间。RFC 793中规定MSL为2分钟,实际应用中常用的是30秒、1分钟、2分钟等。

    TCP的TIME_WAIT需要等待2MSL,当TCP的一端发起主动关闭,三次挥手完成后发送第四次挥手的ACK包后就进入这个状态,等待2MSL时间主要目的是:防止最后一个ACK包对方没有收到,那么对方在超时后将重发第三次握手的FIN包,主动关闭端接到重发的FIN包后可以再发一个ACK应答包。在TIME_WAIT状态时两端的端口不能使用,要等到2MSL时间结束才可以继续使用。当连接处于2MSL等待阶段时任何迟到的报文段都将被丢弃。

    3.4、OSI七层

    从低到高分别是:物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
    在这里插入图片描述
    OSI七层模型是一种框架性的设计方法,设计的主要目的是为了解决异种网络互联时遇到的兼容问题,主要功能就是帮助不同类型的主机实现数据传输。最大优点是将服务,协议,接口三者明确的区分开来,通过七个层次化的结构模型使得不同的主机不同的网络之间实现可靠的通讯。服务说明下一层为上一层提供什么功能,接口说明上一层如何实现下一层提供的服务,协议涉及本层如何实现自己的服务。

    • 优点:
      1.发生故障易排除。
      2.各层各自定义标准接口,使得相同等级的对应层之间的不同网络设备实现互操作。
      3.技术更新可在小范围内进行,不必对整个网络更新。

    3.4.1、物理层

    电缆连线连接器,网卡等。不包括具体的物理媒体。

    物理层的任务就是为它的上一层提供一个物理连接,以及它们的机械、电气、功能和过程特性。如规定使用电缆和接头的类型、传送信号的电压等。在这一层,数据还没有被组织,仅作为原始的位流或电气电压处理,单位是比特。

    3.4.2、数据链路层

    交换机。

    控制物理层和网络层之间的通讯,把网络层的数据分割成物理层可以传输的帧。

    3.4.3、网络层

    路由器。

    将网络地址翻译成对应的物理地址,并决定如何将数据从发送方路由到接收方。通过综合考虑发送优先权、网络拥塞程度、服务质量以及可选路由的花费来决定从一个网络中节点A 到另一个网络中节点B 的最佳路径。

    3.4.4、传输层

    最重要的一层。OSI下3层的主要任务是数据通信,上3层的任务是数据处理。而传输层(Transport Layer)是OSI模型的第4层。因此该层是通信子网和资源子网的接口和桥梁,起到承上启下的作用。协议 和 端口号 是在传输层定义的。

    该层的主要任务是:定义了一些传输数据的协议和端口号(如HTTP的端口80等),TCP(传输控制协议,传输效率低,可靠性强,可以用于传输可靠性要求高,数据量大的数据),UDP(用户数据报协议,与TCP特性恰恰相反,用于传输可靠性要求不高,数据量小的数据,如QQ聊天数据就是通过这种方式传输的)。 主要是从下层接收的数据进行分段和传输,到达目的地址后再进行重组。常常把这一层数据叫做报文段

    eg:电脑如何识别某一个应用程序?
    通过端口号:每一个应用程序都有很多的服务,每一个服务对应着一个端口号

    3.4.5、会话层

    负责网络中两个节点之间建立和保持通信。

    会话层的功能包括:建立通信链接,保持会话过程通信链接的畅通,同步两个节点之间的对话,决定通信是否被中断以及通信中断时决定从何处重新发送。

    数据的传输是在会话层完成的,而不是传输层,传输层只是定义了数据传输的协议。

    3.4.6、表示层

    应用程序和网络之间的翻译官,在表示层,数据将按照网络能理解的方案进行格式化;这种格式化也因所使用网络的类型不同而不同。表示层管理数据的解密与加密,如系统口令的处理。在网络中传输需要加密数据的时候,表示层进行加密解密。对图片的编码解码也是表示层的工作。

    其主要功能是“处理用户信息的表示问题,如编码、数据格式转换和加密解密”等

    3.4.7、应用层

    负责对软件提供接口以使程序能使用网络服务。术语“应用层”并不是指运行在网络上的某个特别应用程序 ,应用层提供的服务包括文件传输、文件管理以及电子邮件的信息处理。

    它是计算机用户,以及各种应用程序和网络之间的接口,其功能是直接向用户提供服务,完成用户希望在网络上完成的各种工作。是最靠近用户的OSI层。这一层为用户的应用程序(例如电子邮件、文件传输和终端仿真)提供网络服务。

    4、操作系统

    4.1、select、poll和epoll的区别

    • 消息传递方式
      select:内核需要将消息传递到用户空间,需要内核的拷贝动作;
      poll:同上;
      epoll:通过内核和用户空间共享一块内存来实现,性能较高;

    • 文件句柄剧增后带来的IO效率问题
      select:因为每次调用都会对连接进行线性遍历,所以随着FD剧增后会造成遍历速度的“线性下降”的性能问题;
      poll:同上;
      epoll:由于epoll是根据每个FD上的callable函数来实现的,只有活跃的socket才会主动调用callback,所以在活跃socket较少的情况下,使用epoll不会对性能产生线性下降的问题,如果所有socket都很活跃的情况下,可能会有性能问题;

    • 支持一个进程所能打开的最大连接数
      select:单个进程所能打开的最大连接数,是由FD_SETSIZE宏定义的,其大小是32个整数大小(在32位的机器上,大小是3232,64位机器上FD_SETSIZE=3264),我们可以对其进行修改,然后重新编译内核,但是性能无法保证,需要做进一步测试;
      poll:本质上与select没什么区别,但是他没有最大连接数限制,他是基于链表来存储的;
      epoll:虽然连接数有上线,但是很大,1G内存的机器上可以打开10W左右的连接;

    综上,在选择select,poll,epoll时要根据具体的使用场合以及这三种方式的自身特点:
    1、表面上看epoll的性能最好,但是在连接数少并且连接都十分活跃的情况下,select和poll的性能可能比epoll好,毕竟epoll的通知机制需要很多函数回调。
    2、select低效是因为每次它都需要轮询。但低效也是相对的,视情况而定,也可通过良好的设计改善。

    4.2、负载均衡

    软件负载均衡、硬件负载均衡、DNS负载均衡。
    DNS负载均衡是地理级别的,硬件负载均衡对应的是集群级别的,软件负载均衡对应的是机器级别的。

    4.2.1、软件负载均衡

    常见的软件有 LVS、 Nginx 、HAProxy 。

    软件负载负载均衡又分四层和七层负载均衡,四层负载均衡就是在网络层利用IP地址端口进行请求的转发,基本上就是起个转发分配作用。而七层负载均衡就是可以根据访问用户的HTTP请求头、URL信息将请求转发到特定的主机。 LVS为四层负载均衡。Nginx、HAProxy可四可七。Nginx是万级别的,通常只用它来做七层负载,LVS来做四层负载。LVS是十万级别的,所以如果顶不住常见的也有这样的搭配:将LVS和NGINX组合起来。

    • 优点:在于便宜而且简单灵活,就买个主机,装下软件,配置一下就能用了,配置也很简单对于一般小型企业,或者并发量不高的企业来说就够用了。而且在高峰期时容易扩容。
    • 缺点:在于(和硬件负载均衡比)性能一般,流量很大的企业就用软件负载均衡顶不住,没防火墙或者防DDos攻击等安全性功能。

    4.2.2、硬件负载均衡

    就是用一个硬件一个基础网络设备,类似我们的交换机啊这样的硬件,来实现负载均衡。 常见的硬件有F5、A10。

    优点:

    • 功能强大,支持全局负载均衡提供全面的复杂均衡算法。
    • 性能强悍,支持百万以上的并发。
    • 提供安全功能,例如防火墙,防DDos攻击等。

    缺点:

    • 贵!这算是它最大的缺点了。为了安全通常还得一主一备。
    • 扩展能力差,当访问量突增的时候超过限度不能动态扩容。

    4.2.3、DNS负载均衡

    这个负载均衡时通过DNS来的,因为DNS解析同一个域名可以返回不同的ip。所以例如哈尔滨的人访问百度就返回距离他近的那个机房的IP,海南的人访问百度就返回距离他近的那个机房的IP。所以主要是用来实现地理级别的负载均衡。

    优点:

    • 交给DNS服务器处理咱们都不用干活
    • 因为是就近访问可以减少响应的时间,提升访问速度

    缺点:

    • DNS有缓存而且缓存时间较长,所以当机房迁移等需要修改DNS配置的时候,用户可能还会访问之前的IP,导致访问失败。
    • 扩展能力差,因为运营商管理控制的,由不得我们定制或者扩展。
    • 比较笨,不能区分服务器之间的差异,也不能反映服务器的当前运行状态

    4.3、内存管理

    4.3.1、页式、段式管理

    • 分页式存储管理
      分页存储管理是将一个进程的地址(逻辑地址空间)空间划分成若干个大小相等的区域,称为页,相应地,将内存空间划分成与页相同大小(为了保证页内偏移一致)的若干个物理块,称为块或页框(页架)。在为进程分配内存时,将进程中的若干页分别装入多个不相邻接的块中。

    • 分段式存储管理
      在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段是一组完整的逻辑信息,如有主程序段、子程序段、数据段及堆栈段等,每个段都有自己的名字,都是从零开始编址的一段连续的地址空间,各段长度是不等的。

    两者的区别:

    • 页是信息的物理单位,分页是为了实现非连续的分配,以便解决内存的碎片问题,或者说分页是为了由于系统管理的需要。
    • 页的大小固定是由系统确定的,将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度是不固定的,决定与用户的程序长度,通常由编译程序进行编译时根据信息的性质来划分。
    • 分页式存储管理的作业地址空间是一维的,分段式的存储管理的作业管理地址空间是二维的。

    4.3.2、页面置换算法

    在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

    • 页面置换算法有哪些?
      (1)最佳置换算法(Optimal):即选择那些永不使用的,或者是在最长时间内不再被访问的页面置换出去。(它是一种理想化的算法,性能最好,但在实际上难于实现)。
      (2)先进先出置换算法FIFO:该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
      (3)最近最久未使用置换算法LRU(Least Recently Used):该算法是选择最近最久未使用的页面予以淘汰,系统在每个页面设置一个访问字段,用以记录这个页面自上次被访问以来所经历的时间T,当要淘汰一个页面时,选择T最大的页面。
      (4)Clock置换算法:也叫最近未用算法NRU(Not RecentlyUsed)。该算法为每个页面设置一位访问位,将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时,其访问位置“1”。在选择一页淘汰时,就检查其访问位,如果是“0”,就选择该页换出;若为“1”,则重新置为“0”,暂不换出该页,在循环队列中检查下一个页面,直到访问位为“0”的页面为止。由于该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用过的页面换出去,所以把该算法称为最近未用算法。
      (5)最少使用置换算法LFU:该算法选择最近时期使用最少的页面作为淘汰页。

    4.4、进程、线程

    进程:具有独立功能的程序关于某个数据集合上的一次运行活动。
    线程:进程的一个实体。
    比喻:一列火车是一个进程,火车的每一节车厢是线程。

    4.4.1、进程、线程的联系与区别

    (1)粒度性分析:线程的粒度小于进程。
    (2)调度性分析:进程是资源拥有的基本单位,线程是独立调度与独立运行的基本单位,出了寄存器,程序计数器等必要的资源外基本不拥有其他资源。
    (3)系统开销分析:由于线程基本不拥有系统资源,所以在进行切换时,线程切换的开销远远小于进程。

    • 联系
      ①一个线程只能属于一个进程,一个进程可以有多个线程;
      ②系统资源分配给进程,同一进程的所有线程共享该进程的所有资源;
      ③真正在处理机上运行的是线程;
      ④不同进程的线程间利用消息通信的方式实现同步。
    • 区别
      ①调度:线程是系统调度和分配的基本单位,进程是作为拥有系统资源的基本单位;
      ②并发性:进程之间可以并发执行,同一进程的多个线程时间亦可以并发执行;
      ③拥有资源:进程是拥有资源的独立单位,线程不拥有资源,但可以访问隶属于进程的资源;
      ④系统开销:创建和撤销进程的开销更大;进程拥有独立的地址空间,一个进程的崩溃不会影响其他进程;线程拥有自己的堆栈和局部变量,没有独立的地址空间,因此进程里的一个线程崩溃会导致其他线程均崩溃。

    4.4.2、进程、线程的通信方式

    • 进程间
      ①管道( pipe ):
      管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
      ②有名管道 (namedpipe) :
      有名管道也是半双工的通信方式,但是它允许无亲缘关系进程间的通信。
      ③信号量(semophore ) :
      信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其他进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。
      ④消息队列( messagequeue ) :
      消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
      ⑤信号 (sinal ) :
      信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生。
      ⑥共享内存(shared memory ) :
      共享内存就是映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的 IPC 方式,它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制,如信号两,配合使用,来实现进程间的同步和通信。
      ⑦套接字(socket ) :
      套接口也是一种进程间通信机制,与其他通信机制不同的是,它可用于不同设备及其间的进程通信。
    • 线程间
      ①锁机制:包括互斥锁、条件变量、读写锁
      互斥锁提供了以排他方式防止数据结构被并发修改的方法。
      读写锁允许多个线程同时读共享数据,而对写操作是互斥的。
      条件变量可以以原子的方式阻塞进程,直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
      ②信号量机制(Semaphore):包括无名线程信号量和命名线程信号量
      ③信号机制(Signal):类似进程间的信号处理,线程间的通信目的主要是用于线程同步,所以线程没有像进程通信中的用于数据交换的通信机制。

    4.4.3、死锁

    • 死锁产生的原因
      (1)竞争资源;
      (2)进程推进顺序不当。
    • 死锁产生的必要条件
      (1)互斥条件:一个资源一次只能被一个进程所使用,即是排它性使用。
      (2)不剥夺条件:一个资源仅能被占有它的进程所释放,而不能被别的进程强占。
      (3)请求与保持条件:进程已经保持了至少一个资源,但又提出了新的资源要求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对已经获得的其它资源保持不放。
      (4)环路等待条件:当每类资源只有一个时,在发生死锁时,必然存在一个进程-资源的环形链。
    • 预防死锁
      破坏四个必要条件之一。
    • 死锁的避免
      银行家算法,该方法允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换,便可将资源分配给进程;否则不分配资源,进程必须阻塞等待。从而避免发生死锁。
    • 死锁定理
      S为死锁状态的充分条件是:尚且仅当S状态的资源分配图是不可完全简化的,该充分条件称为死锁定理。
    • 死锁的解除
      (1)方法1:强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链,并收回分配给终止进程的全部资源供剩下的进程使用。
      (2)方法2:使用一个有效的挂起和解除机构来挂起一些死锁的进程,其实质是从被挂起的进程那里抢占资源以解除死锁。

    4.4.4、进程的五种基本状态

    在这里插入图片描述

    • 创建状态
      进程在创建时需要申请一个空白PCB,向其中填写控制和管理进程的信息,完成资源分配。如果创建工作无法完成,比如资源无法满足,就无法被调度运行,把此时进程所处状态称为创建状态
    • 就绪状态
      进程已经准备好,已分配到所需资源,只要分配到CPU就能够立即运行
    • 执行状态
      进程处于就绪状态被调度后,进程进入执行状态
    • 阻塞状态
      正在执行的进程由于某些事件(I/O请求,申请缓存区失败)而暂时无法运行,进程受到阻塞。在满足请求时进入就绪状态等待系统调用
    • 终止状态
      进程结束,或出现错误,或被系统终止,进入终止状态。无法再执行

    4.4.5、进程同步与互斥的区别

    • 互斥
      是指某一资源同时只允许一个访问者对其进行访问,具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序,即访问是无序的。
    • 同步
      是指在互斥的基础上(大多数情况),通过其它机制实现访问者对资源的有序访问。在大多数情况下,同步已经实现了互斥,特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

    简单地说:同步体现的是一种协作性,互斥体现的是一种排他性。

    5、C++基础知识

    5.1、C++的三大特性

    5.1.1、面向对象特征:封装、继承、多态

    面向对象的理解:是一种“万物皆对象”的编程思想。面向对象的编程是以对象为中心,以消息为驱动,所以程序=对象+消息。
    多态:函数多态,一个接口,多种方法。(C++以虚函数)
    纯虚函数:是虚函数再加上=0(如:virtual void eat()=0;)
    虚函数总是在派生类中被改写,这种改写被称为“override”(覆盖)

    5.1.2、析构函数可以为 virtual 型,构造函数则不能,为什么?

    虚函数采用一种虚调用的办法。虚调用是一种可以在只有部分信息的情况下工作的机制,特别允许我们调用一个只知道接口而不知道其准确对象类型的函数。但是如果要创建一个对象,你势必要知道对象的准确类型,因此构造函数不能为 virtual。

    5.1.3、如果虚函数是非常有效的,我们是否可以把每个函数都声明为虚函数?

    不行,这是因为虚函数是有代价的。由于每个虚函数的对象都必须维护一个虚函数表,因此在使用虚函数的时候会产生一个系统开销。如果仅是一个很小的类,且不派生其他类,那么根本没必要使用虚函数。

    5.2、重载、重写

    重载:编写一个与自己已有函数同名但是参数表不同的函数
    重写(覆盖):重写的函数必须有一致的参数表和返回值

    5.3、程序编译过程

    • 编辑:编辑程序
    • 预处理:删除宏定义、头文件、注释等,添加行号和文件标识,保留所有的#pragma编译器指令,因为编译器须要使用它们
    • 编译:生成汇编代码
    • 汇编:汇编器是将汇编代码转变成机器可以执行的命令
    • 链接:生成可执行文件
    • 运行:执行可执行程序

    5.4、加载程序会经过几个区(堆和栈的区别)

    • 栈区:由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
    • 堆区:一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。
    • 全局区(静态区):全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后有系统释放
    • 文字常量区:常量字符串就是放在这里的。程序结束后由系统释放
    • 程序代码区:存放函数体的二进制代码。

    有些说法,把全局区,常量区合在一起。
    也有些说法,把全局区分成:自由存储区(malloc/free)和全局(静态)存储区。

    5.5、链表和数组有什么不同

    • 数组元素在栈区,链表元素在堆区
    • 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
    • 数组从栈中分配空间, 对于程序员方便快速,但自由度小。链表从堆中分配空间,自由度大,但管理比较麻烦。
      数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);
      数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

    5.6、深拷贝、浅拷贝的区别

    最根本的区别在于是否真正获取了一个对象的复制实体,而不是引用。

    • 浅拷贝:只是拷贝了基本类型的数据,而引用类型数据,复制后也是会发生引用,我们把这种拷贝叫做“(浅复制)浅拷贝”,换句话说,浅复制仅仅是指向被复制的内存地址,如果原地址中对象被改变了,那么浅复制出来的对象也会相应改变。
    • 深拷贝:在计算机中开辟了一块新的内存地址用于存放复制的对象。

    5.7、pragma预处理指令

    #pragma once(比较常用)只要在头文件的最开始加入这条指令就能够保证头文件被编译一次,约等于#ifndef,#define,#endif

    5.8、结构体和共同体的区别

    • 结构体 struct:把不同类型的数据组合成一个整体,自定义类型
    • 共同体 union:使几个不同类型的变量共同占用一段内存
    展开全文
  • 可能是全网最好的MySQL重要知识/面试题总结

    万次阅读 多人点赞 2019-06-29 20:20:34
    事务隔离级别哪些?MySQL的默认隔离级别是?索引相关为什么索引能提高查询速度什么是最左前缀原则?注意避免冗余索引Mysql如何为表字段添加索引?存储引擎一些常用命令MyISAM和InnoDB区别乐观锁与悲观锁的区别悲观锁...
  • 看完保送阿里的RocketMQ知识(超详细)

    万次阅读 多人点赞 2019-12-02 00:01:15
    本文GitHub https://github.com/JavaFamily 已收录,一线大厂面试脑图、个人联系方式,欢迎Star和指教 前言 消息队列在互联网技术存储方面使用如此广泛,几乎所有的后端技术面试官都要在消息队列的使用和原理...
  • 中国房价不可能下降的19理由

    千次阅读 热门讨论 2014-01-26 10:00:27
    在《腾讯房产》频道看到的,所谓专家解释说的房价不可能下降有N无以辩驳理由。虽然少数内容缺乏数据依据,但总体来看,分析得合情合理,也是截止目前,分析得最全面的,尽管不是最透彻的。
  • 数据中台怎么选型?终于人讲明白了

    万次阅读 多人点赞 2022-01-07 14:07:21
    数据中台怎么选型?终于人讲明白了
  • TC主要的缺点是没有scale的能力,如果单机无法满足要求,只能通过主从复制的方式扩展,另外人提到TC的性能会随着数据量的增加而下降,当数据量 上亿条以后,性能会比较明显的下降。 这是Tim Yang做的一...
  • 2020年中国云原生用户调研的十二要点

    千次阅读 多人点赞 2020-11-21 11:10:24
    国内第一份云原生用户调研报告在上月的云原生大会上进行了发布,在一月后的今天,一周六的早上,认真读了一遍,整理了一些要点,不敢独享,发出来与大家共享,个人观点,如雷同,纯属巧合,欢迎人格攻击以外...
  • 转自:展鸿职业考试网... 未来十年里哪几个行业最潜力呢?人力资源管理师为您解答。   今年以来,国家相继制定出台了纺织、轻工、汽车、钢铁、装备制造、船
  • 公司要做数据分析,首先要考虑数据的准备,也就是数据平台的建设,最近接触了几个朋友都处于这一环节,而且其中一个在方案选型过程中,也是充满了纠结,而我也并没有在开始阶段给出合理全面的建议。 所以根据自己的...
  • 支撑处理器的技术——永无止境地追求速度的世界》 ... 地球是由超过总人口好倍的处理器在支撑,其长期处于计算机、移动设备甚至社会基础设施的核心地位。本书讲解处理器构造极其高性能化技
  • 关于航模的几点总结积累

    千次阅读 多人点赞 2018-09-10 22:18:41
    关于航模的几点积累: 一、关于机型: 1.固定翼飞行器分类 按外观:像真机,非像真机 按主翼位置:上单翼,中单翼,下单翼 按动力来源:电动,油动 按控制系统:遥控,线控,自由飞行 按螺旋桨...
  • 作为认知智能的一重要核心技术,自然语言处理在过去一年中了进一步的发展,无论从技术和产品都显著的成果,例如大规模预训练语言模型的明显优势和广泛应用,智能对话和服务助理,结合领域需求的 NLP 技术和...
  • 阿里妹导读:淘宝点亮了全中国,Aliexpress点亮了全球,在近百国家的购物类app排名第一。但AE国际只有1-2物流,峰值压力一度导致多国家的银行系统、物流系统瘫痪,可以想象,作为Aliexpress的SRE压力多大。...
  • 关于Android学习的三终极问题

    千次阅读 多人点赞 2019-05-06 17:05:33
    问题我直到今天也没有答案,这天和朋友闲聊说到这事情。他们得说是智商差距,得说是学习的时候心不在焉——看着在学习,其实已神游大千世界。.....,不过,我自己从来没有下过类似的结论。我武断的...
  • 文末50+行业报告白皮书,9大行业分析指标体系,60+名企规划PPT等福利 2004年笔者进入公司后就从事数据仓库的工作,伴随着中国移动经营分析系统的发展而成长,主导过多次数据仓库的重构建设,见证了数据仓库从...
  • 我们的鸿蒙 OS 是全球第一基于微内核全场景分布式 OS,基于微内核不仅仅我们一家,谷歌的 Fuchsia 也是微内核,苹果也在向这方向发展,但是目前主要是宏内核,我们还是面向全场景分布式 OS,分布式架构支撑,...
  • 觉得不错的话,记得点个Star。 下面这些问题都是一线大厂的真实面试问题,不论是对你面试还是说拓宽知识面都很帮助。之前发过一篇8 张图读懂大型网站技术架构 可以作为不太了解大型网站系统技术架构朋...
  • 软件设计师通关宝典(这一就够了!)

    千次阅读 多人点赞 2020-10-24 13:22:03
    (02)种数据技术:Data Extraction→数据抽取技术 OLAP→数据联机分析技术 OLTP→数据联机处理技术 ETL→数据清洗技术 (03)种加密技术以及密钥传送 对称加密技术:优点(速度快),缺点(加密强度不高,...
  • 支撑计算机高速化的半导体技术

    千次阅读 2012-11-20 08:31:05
    支撑的中心台柱就是半导体技术的进步。本节来看看为什么半导体技术的进步会带来计算机的进步。 摩尔(Moore)定律——更多的晶体管,更高的并行度   Intel的创始人之一Gordon Moore在1965年的Electronics杂志...
  • 青云绝对不是简简单单实现各家都的功能,而是在几个功能上做到极致,从而体现它的“酷”,否则,这种创业企业是无法跟其他巨头竞争的。 在这几个功能上,青云可以秒杀国内所有的IaaS提供商,这绝对不是夸大 。...
  • rs485总线是啥线?rs485总线是芯线

    千次阅读 2020-12-23 14:35:24
    RS-485是串行数据接口规范,由电子工业协会拟定并发布的,1983年在RS-422根底上拟定了RS-485规范,添加了多点、双向通讯才调,即容许多发送器联接到同一条总线上,一同添加了发送器的驱动才谐和抵触保护特性,拓宽...
  • 1、看数据看维度在对某一项业务或者业务的某个模块进行分析,可以从大小两角度去切入分析。首先站在广阔的视角去看待一些数据。比如对某个产品(消费品),就要分析在大环境下是一什么样的数据,如市场排名,...
  • 一共81,开源大数据处理工具汇总

    千次阅读 2017-03-29 21:03:41
    我们将针对大数据开源工具不同的用处来进行分类,并且附上了官网和部分下载链接,希望能给做大数据的朋友做参考。下面是第一部分。 查询引擎 一、Phoenix 贡献者::Salesforce 简介:这是一Java...
  • 在开源中国上关注ceph翻译,没有看到ceph论文的相关翻译, 索性在阅读过程中把它翻译了出来,花费了几个周末时间,翻译过程中收获颇多,现把译文分享出来,如对您有益则倍感荣幸,肯定很多不足之处。如纰漏之 处...
  • 摘要: 再过半月就2013年的春运就要来临,每年外地打工的人们都会因为订票而烦恼。...特别是网上订票,对12306提供给的网上订票系统会各种看法,从去年的年春节,铁道部推出12306网站,实行网络实名购票,每一
  • 智能音箱的2020:下降、消失、寡头

    千次阅读 多人点赞 2020-12-31 15:17:19
    Alexa不是“人”,是她家的亚马逊智能音箱,然而最终Alexa这被她信赖的人工智能,并没有帮他完成报警。 社会在对“疫情之惨痛”发出唏嘘之,对人工智能特别是智能音箱的质疑也随着而来,“不作为”的Alexa再次...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,885
精华内容 11,154
关键字:

下降时支撑点有几个