前语
大家好这里是阳九,一个文科转码的野路子码农,热衷于研究和手写前端东西(现在是全栈了).
今天来聊聊一个困扰广大新手程序员(我)的问题:为什么要学算法？
“刷算法很痛苦,工作中又用不到” __某京东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数量极大 超越一个亿
考虑到性能问题,咱们发现
- 运用行列和传递数组到基层两种方法进行遍历 时间复杂度均为On
- 行列最大需求存储的元素数量不会超越一层的节点数目(即16^n个,n为层数)
- 数组保存的元素也为一层的节点数目(即16^n个,n为层数)
那么 当层数达到6层时 16^6 = 1677万
如果把这么多IPV6存到数组,轻而易举的超越了1G,而咱们的Node服务必定不会为这个核算留出这么多内存
运用文件进行缓存
之后我运用了文件进行缓存,传输数据 具体做法有两种
- 运用行列算法,用txt文件模仿递归行列,不断的从文件头读取IPV6,生成的成果推入IPV6
- 运用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语言重写了,便利敞开多线程)
结束
本次的工作告诉我,比起刷算法题,在事务中想到算法并结合布景合理运用才是真实的难点,需求强大的算法根底。(首要是想不到)
反观各种东西,结构,真实干到底层无非就两个东西, 编译和算法
而且算法能培养人的思想,写代码么,首要便是一个聪明。
算法题写多了,会觉得平时大部分事务都没什么难度,很快就写了(无法便是麻烦)
所以把,哎 算法仍是得写。 难顶哦
