blog icon indicating copy to clipboard operation
blog copied to clipboard

Published 20 hours ago • verified publisher icon creeperyang

算法学习（JavaScript实现）

Open creeperyang opened this issue 6 years ago • 6 comments

一、HashTable （哈希函数，哈希表的简单实现）

这一章节内容主要是 HashTable，中文即哈希表，散列表等等。HashTable 是编程中日常使用，不可或缺的一个数据结构，本章节最终会代码实现一个简单哈希表，来解释哈希表相关的重要概念。

对前端同学而言，哈希表是个每天用但说起来可能陌生的概念。说每天用，是因为在 JavaScript 中，对象（{}）的底层实现即哈希表，我们也经常用对象来做缓存等各种用法，利用其查找时间复杂度为 O(1) 的特性。

1. 为什么需要 hash table （元素查找的时间复杂度）

对若干个元素（key-value对），如果我们想通过 key 来找到对应的 value，通常情况下，我们需要遍历所有元素，一一比较 key，来找到对应的 value。这个时间复杂度是 O(n) 。

然后我们假设这些元素是有序的，那么通过二分查找，时间复杂度可以降到 O(log n) 。

那么有没有更好的方法呢？这就是 hash table 出现的原因，它可以达到 O(1) 的时间复杂度。

2. 什么是 hash table？

哈希表是一种用于存储键值对（key-value pairs）的数据结构，它可以实现key到value的映射，一般情况下查找的时间复杂度是O(1) 。

image

  • 哈希表的核心是哈希函数（hash function），它可以接收 key 作为参数（一般是字符串），然后返回一个数字（通常作为 index 去找到对应的 bucket，bucket 里存储了一个或多个 value）。
  • 哈希函数应该尽可能均匀的把不同的 key 映射到不同的 bucket（即产出不同的 index）。最差情况下，如果所有的 key 都得到相同的 index，那么哈希表就退化成一个链表了（取决于 bucket 的实现）。
  • bucket 指什么？理想情况下，如果每个 key 都得到一个唯一的 index，那么这时候一个bucket对应一个元素，我们通过哈希函数可以一步取到 value；但通常这是不可能的，即 key -- > index 的映射肯定会有冲突的，所以一个 bucket 可能会有多个元素。

3. 哈希表的简单实现

/**
 * 哈希函数，接收字符串返回数字
 * https: //github.com/darkskyapp/string-hash
 * 
 * @param str 字符串
 * @returns number，32位整数，0～4294967295
 */
function hash(str) {
    var hash = 5381,
        i = str.length;

    while (i) {
        hash = (hash * 33) ^ str.charCodeAt(--i);
    }

    /* JavaScript does bitwise operations (like XOR, above) on 32-bit signed
     * integers. Since we want the results to be always positive, convert the
     * signed int to an unsigned by doing an unsigned bitshift. */
    return hash >>> 0;
}

class HashTable {
    static hash(key) {
        return hash(key)
    }
    constructor() {
        this.buckets = [];
    }
    set(key, value) {
        const index = HashTable.hash(key);
        let bucket = this.buckets[index];
        // 直接使用数组来处理哈希函数冲突的问题 
        if (!bucket) {
            this.buckets[index] = bucket = [];
        }
        if (!bucket.some(el => el.key === key)) {
            bucket.push({ key, value });
        }
    }
    get(key) {
        const index = HashTable.hash(key);
        const bucket = this.buckets[index];
        if (!bucket) return;

        let result;
        bucket.some(el => {
            if (el.key === key) {
                result = el.value;
                return true;
            }
            return false;
        });
        return result;
    }
}

以上是一个简单的哈希表实现，还有很多细节没有考虑，比如：

  • 填装因子（填装因子 = 哈希表的元素数量 / 哈希表的位置总数）。根据经验，一旦填装因子大于 0.7，我们就需要调整哈希表的长度。

  • buckets 数组这里没有规定长度，如果考虑 buckets 的长度，那么我们就要对哈希函数返回的值进行取余操作。

参考：

creeperyang avatar Mar 06 '19 08:03 creeperyang

二、KNN （k-nearest neighbors，K最近邻算法）

从一个很简单的例子来理解KNN。

假设我们有一堆橙子和一堆柚子，通常情况下，柚子比橙子更大，更红；现在有一个水果，我们怎么判断它是橙子还是柚子？肯定是比较它的大小和颜色，与橙子/柚子哪个更接近。怎么判断接近？我们可以把之前的橙子/柚子画到二维点图上，X轴为颜色，Y轴为大小，然后来看看离这个水果最近的3个点，结果这3个点里，有2个是橙子，那么我们大概率可以确定，这个水果就是橙子。

这里运用到的就是 KNN 算法：给定一个（训练）数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

KNN 算法是一种基本分类和回归方法，是机器学习中最简单的算法之一。

由于给定的数据集都带有label（即是橙子还是柚子），并且新输入的实例也会明确确定label，所以KNN属于监督学习。

下面讲一些KNN算法的注意点：

K 的选取

  • K 不能过小，过小就容易被噪声干扰。极端情况，K 取 1，只要新实例最近的一个是噪点，那么新实例的分类就会出错。
  • K 不能过大。过大时，表示邻域过大，这个范围内有很多非同类的数据也在起作用（训练实例和输入实例距离大，不相似），容易分类错误。极端情况，K 取全部数据，那么新实例永远归入数量占多的类别。
  • 所以 K 不能过大过小，一般取一个较小的数值，并采取交叉验证法来选取最优的K值。

距离计算

  • 一般采用欧氏距离（Euclidean Distance）。欧氏距离可以量测任意方向的线段，计算方法是 d=\sqrt{\left(x_1-x_2\right)^2 + \left(y_1-y_2\right)^2 + \left(z_1-z_2\right)^2 + ...}
  • 不采用曼哈顿距离（Manhattan Distance）。曼哈顿距离就像曼哈顿的街道一样，只有水平和垂直的线段，无法计算多维度，计算方法是 |x_1 - x_2| + |y_1 - y_2|
  • 实际中经常使用余弦相似度（计算角度而非距离）。

特征归一化

假设我们通过两个维度（身高和脚长）来判断性别，很显然，计算距离时，结果会偏向于身高。

所以很容易理解，我们需要对特征归一化。即取每个维度的最大值减去最小值，然后该维度计算时首先除以这个值来进行归一化。

creeperyang avatar Mar 06 '19 10:03 creeperyang

三、动态规划

背包问题

首先我们从背包问题开始。

一个背包可以装4kg的物品，现有物品音响（3000元|4kg）笔记本电脑（2000元|3kg）、吉他（1500元|1kg），那么我们怎么拿可以使物品价值最高？

1、 最简单的方法：罗列所有组合，选取符合条件的最高的那个。

物品是1个的时候，我们可以拿或不拿，即2种选择；物品3个的时候，我们有8种选择；物品n种时，我们有 2^n 种选择——时间复杂度 O(2^n)!

2、动态规划

image

动态规划的核心在于合并两个子问题的解来得到更大问题的解。

那么它的难度就在于怎么把大问题分解成子问题。

在这里的例子里，装入背包的物品价值取决于物品类型和背包容量两个因素，以这两个因素为维度，利用网格来得到问题的解（本质上是当容量更小、物品更少时更容易得到解）。

  • 当只有一个物品时，随容量增加，很轻松可以得到容量对应的最大价值（这里作为第一行开始）。
  • 当增加物品时（即下一行），那么每个格子的值将由上一行对应格子的值和当前物品价值来决定：
    • 增加物品，价值只可能增长，所以最小值是上一行对应格子的值；
    • 如果当前格子的容量可以放下当前物品，那么可能的最大值是当前物品的价值 + 上一行对应剩余容量格子的值。

creeperyang avatar Mar 08 '19 11:03 creeperyang

动态规划优秀文章：动态规划套路详解

1. 核心观点

动态规划并不难，通常是通过流程 递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法 一步步铺垫而来，动态规划的核心是化递归（自顶向下）为循环迭代（自底向上）。

如上面流程所示，在动态规划中，得到暴力解（即如何穷举所有可能性，也即得到“状态转移方程”）是最困难的一步。为什么说困难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不容易穷举完整。

2. 凑零钱Demo演示

假设有 k 种不同币值硬币，总金额为 n 时最少需要几枚硬币可以凑出这个金额？无法凑出则给 -1。 比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。

假设 n 总是可以被凑出来的，那么这个问题其实非常简单，我们只需要先从最大币值的硬币开始凑就可以了。然而这个假设并不总是成立，所以事实上我们需要穷举所有可能性——典型的可以采用动态规划方法来解决的问题。

下面我们按流程来解题：

1）暴力解（即状态转移方程）：
f(0) = 0;
f(n) = 1 + min{f(n - Ci)}  ( i 属于 [1, k], Ci 即对应的硬币币值)

其中，n 即总金额， i 为 1~k，即不同币值硬币个数，Ci 为对应硬币币值。

如上，可以理解为原问题的解可以通过子问题的最优解来得到，即 f(11) 是可以分解为：

  • 硬币 1 元 和 f(10) 的最小硬币数
  • 硬币 2 元 和 f(9) 的最小硬币数
  • 硬币 5 元 和 f(6) 的最小硬币数

3种情形的最优解即为最终解，而 f(10) / f(9) / f(6) 可以继续递归分解。

好了，给这个暴力解一个程序表达：

// 暴力递归
function assembleCoin(coins, amount) {
    if (amount === 0) {
        return 0;
    }

    let ans = Number.MAX_SAFE_INTEGER;
    for(let c of coins.values()) {
        // 剩余金额
        let value = amount - c;
        // 币值大于总金额，说明是无效的
        if (value < 0) continue;
        // 计算剩余金额可能的最少组合次数
        const sub = assembleCoin(coins, value);
        // 次数小于0，说明无效
        if (sub < 0) continue;

        // 该次组合有效，更新最少次数
        ans = Math.min(ans, 1 + sub);
    }

    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}
2）带备忘录的递归

暴力解有太多的重复子问题（比如多个 f(5) 的求解）,如果重复子问题的求解结果被缓存了，那同一个子问题就只用计算一次了：

// 带备忘录的递归
function assembleCoinWithMemo(coins, amount) {
    const memo = {};
    return coinHelper(memo, coins, amount);
}

function coinHelper(memo, coins, amount) {
    if (amount === 0) {
        return 0;
    }

    if (memo[amount] !== undefined) {
        return memo[amount];
    }

    let ans = Number.MAX_SAFE_INTEGER;
    for (let c of coins.values()) {
        // 剩余金额
        let value = amount - c;
        // 币值大于总金额，说明是无效的
        if (value < 0) continue;
        // 计算剩余金额可能的最少组合次数
        const sub = coinHelper(memo, coins, value);
        // 次数-1，说明无效
        if (sub === -1) continue;

        // 该次组合有效，取最少次数
        ans = Math.min(ans, 1 + sub);
    }
    memo[amount] = ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
    return memo[amount];
}
3）动态规划：递归 --> 循环

动态规划其实和上面的备忘录法已经相当接近了，把备忘录换成 DP 表，从而自底向上求解替代自顶向下，就是动态规划：

// 动态规划
function assembleCoinDP(coins, amount) {
    // dp 表最多包含 amount + 1 种情况（包括0）
    const dp = Array(amount + 1).fill(amount + 1);
    // 最简单（自底向上的底）的情况：
    dp[0] = 0;
    // 从 1 开始填充 dp 表的过程即自底向上逐渐求解的过程
    for(let i = 1; i < dp.length; i++) {
        // 内层 for 循环求所有子问题 + 1（种硬币） 的最小值
        // 比如 i = 1，我们即求解：1元+dp[0]，2元+dp[-1]，5元+dp[-4] 等3种情况，
        // 其中后两种被 continue 直接过滤了，所以 dp[1] 很容易得到为 1；
        // 随着 i 增大，我们最终总可以得到所有的 d[i]，且必然 d[x]（x < i）是已经计算
        // 有结果的（保持 amount + 1的最大值即代表amount 为该值时无可用的硬币排布，返回 -1）
        for (let c of coins.values()) {
            if (i - c < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - c]);
        }
    }
    return dp[amount] === amount + 1 ? -1 : dp[amount];
}
时间复杂度

最后顺便给一组实际测试时不同方式的用时：

// 1,2,5     -----------   13
4
normal: 2.667ms
4
memo: 0.166ms
4
dp: 0.171ms

// 1,2,5     -----------   27
6
normal: 35.627ms
6
memo: 0.185ms
6
dp: 0.183ms

// 1,2,5     -----------   39
9
normal: 18192.081ms
9
memo: 0.191ms
9
dp: 0.206ms

可以看到，相比带备忘录的递归和动态规划，暴力递归的用时太可怕了：

  • 暴力递归时间复杂度：O(k*n^k)
  • 备忘录：O(kn)
  • 动态规划：O(kn)

如上，希望通过例子可以对动态规划更容易理解一些。

creeperyang avatar Oct 08 '19 11:10 creeperyang

四、KMP（Knuth-Morris-Pratt ） 算法

KMP 是著名的字符串匹配算法，效率高但比较难理解（一看就懂的请勿代入 😂 ）。

字符串匹配问题是指从一段已有的文本串（记为 txt，长度记为 N）中匹配模式串（记为 pat，长度记为 M），我们首先从暴力匹配算法开始，讲一讲为什么会有 KMP（KMP是为解决什么问题）。

暴力匹配

function directSearch(pat, txt) {
    if (!pat || !txt) return -1;

    const txtLen = txt.length;
    const patLen = pat.length;

    for (let i = 0; i < txtLen - patLen + 1; i++) {
        let j;
        for (j = 0; j < patLen; j++) {
            if (pat[j] !== txt[i + j]) {
                break;
            }
        }
        // j 等于 patLen，代表比较过程全部走完，即全部匹配
        if (j === patLen) {
            return i;
        }
    }
    return -1;
}

如上，暴力匹配即从文本串第一位开始，每次都遍历整个模式串来一一比较，简单直接，时间复杂度为 O(MN)。

但暴力匹配有个问题：它不够智能，每次都需要从头开始重新一一比较，之前比较过程中匹配的部分没法利用，做了很多无用功。那么有没有方法可以利用之前比较的结果？有，这就是KMP。

从 PMT （部分匹配表 Partial Match Table）开始来理解 KMP

这里为什么不从 KMP 的概念开始学习 KMP（正如我们以前学习一般算法那样）？因为从概念开始，最后讲到 PMT 真的不容易理解，所以干脆反其道而行之，先来理解 KMP 的核心概念：部分匹配表PMT。

1) 字符串的前缀、后缀到 PMT

理解PMT的前置要求就是理解字符串的前缀、后缀。假设字符串A、B、S，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。后缀同理。

PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

举例描述，对 aba 而言，前缀是 {a, ab}，后缀是 {ba, a}，那么交集就是 {a}，PMT中对应值就是 1。

假设模式串 pat 是 abababca，那么对应的 PMT 表就是：

char: a b a b a b c a
index: 0 1 2 3 4 5 6 7
value: 0 0 1 (a) 2 (ab) 3 (aba) 4 (abab) 0 1 (a)

2) PMT可以帮助到暴力匹配什么

现在我们已经有了 PMT 了，那它可以用来优化暴力匹配吗？当然可以，这里也就是 KMP 理解的难点。

暴力匹配被认为效率低的地方在于一旦不匹配，就只能从头开始比较，之前的比较结果无法利用。但当我们有了 PMT ，我们就再也不用从头比较了！

我们尝试来在暴力匹配中加入 PMT ：

txt: ababababca -- i 是遍历 txt 的下标 pat: abababca -- j 是遍历 pat 的下标

  1. 暴力匹配第一轮在碰到 c 的时候，即 i = j = 6 时，发现了不匹配；
  2. 如果没有 PMT，那么我们之能重置i = 1, j = 0开始重新比较（这里就是为什么低效，i 要回头，然后比较整个 pat）；
  3. 但是借助 PMT，我们可以不用让 i 回头，我们保持 i = 6, 设置 j = 5，继续比较。

如上就是借助 PMT 之后的比较过程（即KMP），它可以保证 i 不回退，可以尽量不重新比较整个模式串（j 设置为合理的值而不像暴力匹配那样直接重置为 0）。

但为什么可以比暴力匹配更聪明？即为什么 i 不回退， j 是 5？

  1. 初始化 i = j = 0 开始匹配，直到 i = j = 6 不匹配。

  2. 我们的目的是希望文本串（txt）只循环一遍，即 i 不回退，这就是为什么 i 保持 6 不变。我们需要解释的是 i 不变可以保证匹配正确性吗（即正确的匹配结果肯定不是 i 为 1- 5）？由第4点解释。

  3. 当 i = j = 6 （第7位）不匹配时，暗含的是之前6位（0-5，ababab）是相同的，即模式串（pat）和文本串（txt） 均包含相同的子串 ababab，又因为 i 不变，那么找到合适的 j 继续比较其实就是找 ababab 的前缀、后缀的交集的最大长度——恰好这个工作已经由我们的 PMT 先做了，我们查到 index 为 5 对应的值是 4，那么 j 就是 4 （下标为4，前4位是 abab，作为ababab的前缀，同时以文本串的角度而言，是后缀）。

    再详细一点来解释一下。因为 i 不变（这是设定，为什么可以这样设定第4点解释），所以我们相当于是把模式串 pat 向后移动，对模式串和文本串共有的 ababab 而言，是不是就是找到 ababab 的前缀、后缀的交集的最大长度？很直接吧。

  4. 好了，这一步来解释一下为什么 i 可以保持不变。如上一步而言，当 i = j = 6 （第7位）不匹配时，前 6 位（ababab）是匹配的。假设我们用暴力匹配的方法，把 i 设置为 1，j 设置为 0 开始重新比较，有没有发现，对 i 从 1 到 5 而言（即 j 从 0 到 4），我们仍然是在比较 ababab 的前缀后缀？！

    • 对 i = 1，我们是在问 ababab 是不是有最大长度 5 的前缀后缀交集，即 PMT 表的值有没有 5，并没有；
    • 对于 i = 2，我们是在问 ababab 的 PMT 表值是不是有 4，真的有；有没有发现这时候字符串的位置和我们第 3 步得到的是一样的？
    • 其实正因为对 1 - 5 的暴力匹配过程本质上就是在查询 PMT 表，所以我们可以直接设定 i 不变，找到对应的 j 即可！

  5. 至此，KMP 的核心思想应该可以理解了，即 PMT 表简化/消除了在部分匹配时暴力匹配的重复工作，暴力匹配在部分匹配的情况下本质是在找某一字符串的前缀、后缀的最长交集。

KMP 的实现

/**
 * 定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。
 * next[x] 定义为： pat[0]~pat[x]这一段字符串，使得k-前缀等于k-后缀的最大的k。
 * 对字符串pat的求解并返回next数组。
 * 
 * @demo 'aa' => [0,1]
 * @demo 'abababc' => [0,0,1,2,3,4,0]
 */
function getPMT(pat) {
    // 所有元素填充为 0，且next[0]=0不用再计算。
    const next = Array(pat.length).fill(0);

    let curr = 1; // 指针（从1开始），用于指定当前需要计算的next数组元素next[curr]
    let len = 0; // 长度，理解为next[curr-1]的值，即前一位（next[curr-1]）的最长相等前后缀长度
    while (curr < pat.length) {
        console.log('start',len, curr, next)
        // 如果字符相等，则说明最长相等前后缀长度加1（即len+1）
        if (pat[curr] === pat[len]) {
            next[curr++] = ++len; // 同时 curr 往右移动一位继续计算过程
        }
        // 如果不等，则根据情况设置 len / curr
        else {
            // 如果len是0，即前一位的最长相等前后缀长度是0，现在又不相等，next[curr] 只能继续0；
            // curr往右移动一位继续
            if (len === 0) {
                curr++;
            }
            // 如果 len > 0，即前一位的最长相等前后缀长度大于 0，那么我们需要怎么缩短 len，然后重新比较 pat[curr] 和 pat[len]。
            // ---
            // 先假设 pat[0,...,len-1] 为字符串 A，pat[curr-len,...,curr-1] 为字符串 B，很显然，我们当前比较的就是
            // [...A,pat[len]] 和 [...B,pat[curr]]，只可惜 pat[curr] 和 pat[len] 不等；
            // 那么 A 和 B 的最长相等前后缀长度是多少呢？是 next[len-1]，注意到这里有A和B相等。
            // 回到上面的问题，怎么缩短 len 是最有效的（尽可能让len最大）？
            // 显然 curr 是不用变的，因为 curr 就是用来指示当前需要计算的 next[curr];
            // 所以缩短len到len1，本质上就是尽可能取A的左半部分（长度len1），尽可能取B的右半部分（长度len1），让两者相等；
            // 巧合的是，A和B相等，那么，这个len1，正好就是 next[len-1]
            else {
                len = next[len - 1];
            }
        }
        console.log('end',len, curr, next)
    }

    return next;
}
function kmpSearch(txt, pat) {
    let i = 0;
    let j = 0;
    const next = getPMT(pat);
    while (i < txt.length && j < pat.length) {
        if (txt[i] === pat[j]) {
            i++;
            j++;
            if (j === pat.length) {
                return i - j;
            }
        } else {
            if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

creeperyang avatar Oct 22 '19 08:10 creeperyang

五、位操作实现加法等特殊需求

怎么不用加号实现加法？

这里考虑两个特殊位操作符：

  • Bitwise AND (&)：二进制数对应位都是1才返回1，否则0。
  • Bitwise XOR (^)：二进制数对应位不等（1个1、1个0）才返回1，否则0。
const a = 5;        // 00000000000000000000000000000101
const b = 3;        // 00000000000000000000000000000011

console.log(a & b); // 00000000000000000000000000000001
// Expected output: 1

console.log(a ^ b); // 00000000000000000000000000000110
// Expected output: 6

那么我们怎么借助这两个位操作实现加法？

function bitAdd(a, b) {
    // 对应位都是1才返回1，所以这是a和b的和的需要进位的部分
    const carry = a & b;
    // 对应位只有不一样才返回1（去除了对应位都是1的部分），所以这是a和b的和的不需要进位的部分
    const noCarrySum = a ^ b;
    // 需要进位，那么进位的部分先进位（<<1），然后递归调用bitAdd
    if (carry) {
        return bitAdd(carry << 1, noCarrySum);
    }
    // 如果不需要进位，直接返回就好
    else {
        return noCarrySum;
    }
}

更进一步，借助bitAdd实现乘法，比如数字✖️7:

const bitMultiply7 = (a) => bitAdd(a << 2, bitAdd(a << 1, a));

creeperyang avatar Mar 11 '23 08:03 creeperyang

已收到,稍候会处理best wish~

18boys avatar Mar 11 '23 08:03 18boys