仓库源文站点原文


tags: [程序设计, 笔记, C++, '#NEED-UPDATE'] title: 哔哩哔哩 冒-_-泡 技术视频的笔记 last_modified_at: 2023-3-4 slug: bilibili-mao-pao-video-notes redirect_from:

- /posts/哔哩哔哩冒--泡_技术视频的笔记

慢慢填

视频传送门

正文

【算法】用位运算加速sqrt

首先,我们要了解sqrt的原理:简而言之,就是先将$sqrt(a)=x$转换为求$x^2-a=0$的解。

具体来说,计算机会任取一个$x_0$,并求$x^2-a=0$在$x_0$上的切线(也就是导函数),通过该导函数与 x轴 的交点来逐渐逼近原函数的交点。多次重复以上过程,从而得到误差允许的解。(具体公式如下图)

逼近正解的函数图像表示

其中,$x_{0+1}$点(也就是D点,或者说$x_1$点)的坐标可以化简为$(x_0+a/x_0)/2$(如果第一个值$x_0$为负数,也很容易看出$x_1$必定为正数)

那么,如何优化呢?若最开始取的$x_0$足够接近正解,我们就可以跳过大量运算。为此,我们要先了解一下 IEEE 754 浮点数规范

可以看到,浮点数是由指数与底数两部分分开存储。因此,我们只需要将指数先除 2,再将底数部分略微调整(此处通过多次实验,可以得出最优底数调整值),即可得到非常近似的结果。

具体代码参看原视频12:55处,摘录如下:

float mySqrt(float x){
    float a = x;
    unsigned int* p = (unsigned int*)&x; // 用于进行位的运算
    *p = (*p + 0x3f76cf62) >> 1; // 魔数推导详见视频,通过大量随机测试得到结果
    x = (x + a / x) / 2; // 前文所述的逼近正解,这句可以复制多次以更大减小误差
    return x;
}

【算法】后宫三千如何友好相处?- N皇后排布问题

建模:以一个一维数组表示每行皇后的位置

搜索树:搜索+剪枝,找到合法状态

启发式搜索

前提:约束满足问题(CSP):在若干变量的情况下,要求找到一组满足约束的解

原因:传统搜索深度与 n 成指数关系,效率低,且目的是统计所有状态

性质:随机化算法,每次得到的解可能不同

联系:模拟退火;局部剪枝;弧相容技术

建模

状态空间:n 行所有可能性

状态变迁:某行皇后位置的迁移

若两个状态能通过一次迁移得到,则认为它们是连接的

状态价值评估:冲突数量,冲突越少则目前状态价值越高

解法(爬山法)

多次随机选择起点,通过不断迁移找到更好的解(局部贪心搜索),找到正解或局部最优解后本次搜索结束

若找到的是局部最优解(本身有冲突,且无论如何迁移都会冲突),则随机起点重新搜索

效率:由于是单向搜索(只像价值较高状态搜索),效率较高

优化

状态空间:n 行不同列的排列

状态变迁:某两个皇后所在行的交换

状态价值评估:冲突数量(仅需考虑斜线)

效果:状态空间:$n^n$ -> $n!$

【算法】一道简单的面试题,顺利答出的却寥寥

strcmp

效率测试

随机输入时,标准库中的strcmp远比手动实现的慢。为什么?

其中一个原因,可能是strcmp存在硬件优化,由于进行大范围的读取而导致效率降低;但手工实现的是逐个字符比较的,在第一处不同就会直接返回,不会出现大规模复制问题。

时间复杂度

那随机字符串比较的平均时间复杂度是?或者说,找到第一处不相等的字符需要几次比较?

原始期望值算法

不懂,请自行跳转原视频08:09查看

解方程

$E=(c-1)/c+(1/c)*(1+E)$

其中c代表每个字符可取的值的数量,E代表最终比较数的期望值,本方程的思想就是设字符串无限长,将第一个字符相等第一个字符不相等的总值相加,解得$E=c/(c-1)$;当c较大(比如 255)时,平均时间复杂度就约为O(1)

字符串匹配

朴素字符串匹配

最坏时间复杂度O(MN),平均时间复杂度O(N)(输入随机)(参考:《算法导论》),也是 Java 的实现算法

为什么不用 KMP?

需要预处理,在极端情况下可能更慢,而朴素算法相对较通用;同时,作为基础库要保证代码维护性

【算法】经典算法的工程滑铁卢 - BKDR hash分析

简介

根据视频的描述,该 hash 算法是在 Java 中对字符串求 hashCode的算法的一种实现。具体来说,它将字符串视作类似 31 进制求值(若溢出则直接回环),近似公式如下(与真正代码很不同):

$str.hashCode() == (\sum_{i=0}^{str.length}str[i]*31^i) \% 2^N$

注意,这里的 B 不一定要选 31,但最好不要选 2 的倍数。由于执行时会对$2^N$取模,因此若字符串很长,前半段就无法参与运算。

问题:冲突率过高

对 100 万以内所有数字取 hash,可以发现,以字符串形式存储数字不会产生 hash 冲突,但以大端序整数存储数字冲突率极高(约每 40 个数字会有相同的 hash)

0xbd40xaf3为例,(b-a)^31 = 1^31 = 31^1 = (0xf3-0xd4)^1,也就是说后两位的哈希值经过累计抵消了最高位的的哈希差。然而,在 ASCII 码中几乎不可能出现此情景,因此以字符串形式存储不会有这种冲突。

那么,如何解决?显而易见,只要低位的差远远小于模数,就不会发生这种冲突(可以理解为不会进位)。因此,将模数由 31 调整为 60001 一类的数,就可以解决此问题。

问题:哈希值连续

目前的算法中,如果最后一次参与加法的位是连续的,那么计算出来的 hash 值也是连续的,会造成一定效率问题。对此,需要乘法打散:即将最后得到的 hash 值再次乘以一个相对较大的数(如 60001),以防止所有 hash 值完全连续

问题:前缀 0

如果最早参加乘法的数位数值上均为 0,那无论有多少个 0,hash 值都是相同的。对此,可以将运算时的初值由 0 改为 1(也就相当于上方简介中的公式),这样前导零会被视为普通的数值参与运算。

那为什么要保留这个不好的实现?

<del>历史遗留</del> 在随机生成数据的场景下已经有较好的表现了,但并不完善。生产环境下建议自己重新实现。