前语

大家好这里是阳九,一个文科转码的野路子码农,热衷于研究和手写前端东西(现在是全栈了).

今天来聊聊一个困扰广大新手程序员(我)的问题:为什么要学算法?

“刷算法很痛苦,工作中又用不到” __某京东JAVA后端

“算法能够让咱们了解数据结构” __某架构师

然而最近我也是在工作中初次遇到了算法问题, 算法确确实实在本次的事务中帮助了我,记载一下

不枉我写了这么多没啥卵用的题,书到用时方恨少啊

本次的算法十分简略,便是一个BFS广度优先遍历树,(我先想到的是力扣的一道题”二叉树的层序遍历“)

原因

我在做一个IPV6地址处理的功能,有这样一个需求,给出一个不完好的IPV6地址,生成多个完好的IPV6地址

(由于涉及到事务机密,这里不能详细说明,只能简易阐述要做的工作)

let ipv6_part = "268b:7360:0000:0000:****:****:****:****"

其中,”*”的方位是未知的16进制字符, (0-f)

咱们需求根据装备,补全这个不完好的IPV6地址,从而获得多个完好的IPV6地址字符串。

而之前的搭档,运用了递归进行补位, 也便是IPV6逐个+1,终究将其他的*号用0填充

268b:7360:0000:0000:****:****:****:***0
268b:7360:0000:0000:****:****:****:***1
268b:7360:0000:0000:****:****:****:***2
...
268b:7360:0000:0000:****:****:****:***f
268b:7360:0000:0000:****:****:****:**10

那么这样生成的IPV6地址,基本上都是分布在同一个IPV6段里,在运用的时分就会有问题(要么能够用,要么不能用)

咱们需求让生成的IPV6地址足够涣散, 所以需求从第一个”“开始补位,也便是这样,终究再将其他的号用0填充

268b:7360:0000:0000:0***:****:****:****
268b:7360:0000:0000:1***:****:****:****
268b:7360:0000:0000:2***:****:****:****
...
268b:7360:0000:0000:f***:****:****:****
268b:7360:0000:0000:10***:****:****:****

简略递归算法

生成二进制数字 咱们能够经过树来生成二进制数字,沿着树的途径走下去,就能够生成二进制数字,也便是所谓的二叉树

记录一次在业务中正儿八经使用算法的例子

相同的 咱们能够这样处理10进制,

记录一次在业务中正儿八经使用算法的例子

现在咱们需求处理的是一个IPV6地址,也便是16叉树

记录一次在业务中正儿八经使用算法的例子

咱们能够发现,如果是这种模式生成IPV6,便是所谓的”深度优先递归遍历树”DFS, 那么咱们得到的成果就不涣散,而是十分靠拢。

268b:7360:0000:0000:****:****:****:***0
268b:7360:0000:0000:****:****:****:***1
268b:7360:0000:0000:****:****:****:***2
...

咱们需求将深度优先转换为广度优先BFS, 也便是这样

算法代码完成

一般来说咱们有两种办法完成广度优先遍历, 能够参阅力扣的一道题102. 二叉树的层序遍历 – 力扣(Leetcode) 咱们的广度优先遍历16叉树,也便是16叉树的层序遍历

运用行列完成

咱们能够经过行列, 每次解析行列头元素,然后解析出的成果再次推入行列,完成BFS

function breadthFirstSearch(root) {
    let queue = [root]; 
    let result = [];
    while (queue.length > 0) {
      let node = queue.shift();
      result.push(node.value);
      if (node.left) {queue.push(node.left)}
      if (node.right) { queue.push(node.right)}
    }
    return result;
  }

运用for循环完成

咱们也能够将每层的解析成果推入数组,保存起来,传入下一个递归函数中,执行for循环

const result = []
var breadthFirstSearch = function (curNodeList) {
    // 保存本层成果
    let nextNodeList = []
    //  遍历上一层的所有节点
    curNodeList.forEach((node) => {
        result.push(node.val) // 写入成果
        if (node.left) { nextNodeList.push(node.left) }
        if (node.right) { nextNodeList.push(node.right) }
    })
    // 本层成果继续传入基层核算
    nextNodeList.length > 0 && deep(nextNodeList)
};
breadthFirstSearch([root])

记录一次在业务中正儿八经使用算法的例子

实践代码完成中的问题

  • 由于咱们处理的节点都是一个IPV6字符串,也便是128位, (核算机内部优化为16字节)
  • 需求处理的IPV6数量极大 超越一个亿

考虑到性能问题,咱们发现

  1. 运用行列和传递数组到基层两种方法进行遍历 时间复杂度均为On
  2. 行列最大需求存储的元素数量不会超越一层的节点数目(即16^n个,n为层数)
  3. 数组保存的元素也为一层的节点数目(即16^n个,n为层数)

那么 当层数达到6层时 16^6 = 1677万

如果把这么多IPV6存到数组,轻而易举的超越了1G,而咱们的Node服务必定不会为这个核算留出这么多内存

记录一次在业务中正儿八经使用算法的例子

运用文件进行缓存

之后我运用了文件进行缓存,传输数据 具体做法有两种

  1. 运用行列算法,用txt文件模仿递归行列,不断的从文件头读取IPV6,生成的成果推入IPV6
  2. 运用for循环算法,用txt文件模仿传入基层的数组,每次for循环,读取上一个文件的成果文件
// 成果文件
const resultFileStream = fs.createWriteStream(resultFile, { flags: 'a' });
var breadthFirstSearch = function (floor) {
    // 读取上层成果文件 floor为层数
    let regionsFile = `./cache/${floor}.txt`
    const readStream = fs.createReadStream(regionsFile)
    // 创建本层成果regions文件(给下一层运用)
    let nextRegionsFile = `./cache/${floor + 1}.txt`
    const nextRegionsStream = fs.createWriteStream(nextRegionsFile);
    // 逐行读取文件内容
    const rl = readline.createInterface({
        input: readStream,
        crlfDelay: Infinity // 运用默认的换行符号
    })
    // 每个成果生成16个子成果
    rl.on('line', (ipv6) => {
        for (let j = 1; j < 16; j++) {
            let newIpv6 = handle(ipv6)
            nextRegionsStream.write(newIpv6 + "\n");// 写入本层遍历成果
            resultFileStream.write(newIpv6 + "\n");// 写入成果文件
        }
    })
    // 文件处理完毕  进行下一层处理
    rl.on("close", () => {
        breadthFirstSearch(floor + 1)
    })
};

多线程再次优化

终究我运用了for循环的算法, 由于这样能够单独遍历每一层的成果,当本层成果过大时,咱们能够将单层的成果进行拆分,敞开多个线程进行处理(后边直接将核算逻辑用GO语言重写了,便利敞开多线程)

记录一次在业务中正儿八经使用算法的例子

结束

本次的工作告诉我,比起刷算法题,在事务中想到算法并结合布景合理运用才是真实的难点,需求强大的算法根底。(首要是想不到)

反观各种东西,结构,真实干到底层无非就两个东西, 编译和算法

而且算法能培养人的思想,写代码么,首要便是一个聪明。

算法题写多了,会觉得平时大部分事务都没什么难度,很快就写了(无法便是麻烦)

所以把,哎 算法仍是得写。 难顶哦