关于算法动态规划的实现优化

栏目: 编程工具 · 发布时间: 5年前

内容简介:作用:不用说了提高效率和性能应用:目前也是买了算法导论这本书,看得头晕,各种数学知识需要返回去重新认识,哎,终于知道了以前学的东西总有用的。。。,自己买的哭着也要读完,不扯了,直接说下现在已经应用的两个地方第一点我也是看了这篇博客才下定决心迈向算法大坑的,具体不多说直接附上地址

首先说下算法对于前端的作用和应用

作用:不用说了提高效率和性能

应用:目前也是买了算法导论这本书,看得头晕,各种数学知识需要返回去重新认识,哎,终于知道了以前学的东西总有用的。。。,自己买的哭着也要读完,不扯了,直接说下现在已经应用的两个地方

  1. trie树结构,对于后端扁平化数据转树形结构适用于前端的应用,终于把递归改成动规了
  2. 动态规划在前端瀑布流中的应用

第一点我也是看了这篇博客才下定决心迈向算法大坑的,具体不多说直接附上地址

连接描述

第二点的动态规划参考以下博客,其中说的非常清晰,我主要是列举下对于此篇介绍中已实现的js,做 空间复杂度优化的代码,不足之处请指出

链接描述

首先我是按照数据的倒退图里面以物品数组作为外层数组,背包容量作为内层数组的形式写的js(按照图的推导顺序)

1 用来生成随机大小的物品重量和价值数组

function getNum() {
    return parseInt(Math.random()*100+1);
}
function getArr(size) {
    var arr = [];
    for (var i = 0;i<size;i++) {
        arr.push(getNum());
    }
    return arr;
}
var weight = getArr(10000);
var value = getArr(10000);
var V = 10000;

2 实现

function aaa(wight,value,all) {
    var startTime = new Date().getTime();
    var returnList = [];
    for (var i = 0;i<wight.length;i++) {
        returnList[i] = [];
        for (var j = 0;j<all;j++) {
            var nowW = j+1;//此时背包重量
            var nowW_ = wight[i];//此时物品重量
            var nowV = value[i];//此时的价值
            var lastW = nowW - nowW_;//此时背包重量减去此时要添加的物品后的重量
            
            var fV = lastW>=0?nowV:0;
            fV = fV+(i>0&&returnList[i-1][lastW-1]?returnList[i-1][lastW-1]:0);
            var nV = i>0&&returnList[i-1][j]?returnList[i-1][j]:0;
            returnList[i][j] = Math.max(fV,nV);
        }
    }
    var endTime = new Date().getTime();
    return returnList[wight.length-1][all-1]+"耗时:"+(endTime-startTime)+"ms";
}
console.log(aaa(weight,value,V));

这种方式需要构建庞大的二维缓存数组(用来把每次的最优解存下,类似于斐波那契函数动规的缓存),这一步完全可以优化成只构建上一步的最优解供给下一次使用

function bbb(wight,value,all) {
    var startTime = new Date().getTime();
    var returnList = [];
    var returnList_prev = [];
    var flag = true;
    for (var i = 0;i<wight.length;i++) {
        for (var j = 0;j<all;j++) {
            var nowW = j+1;//此时背包重量
            var nowW_ = wight[i];//此时物品重量
            var nowV = value[i];//此时的价值
            var lastW = nowW - nowW_;//此时背包重量减去此时要添加的物品后的重量
            //考虑过两个数组相互赋值,但是数组是引用类型,两个会干扰,如果深拷贝那就更影响速度,所以想到这种两个数组相互使用相互覆盖的方式来避免构建庞大的二维数组
            if(flag) {
                var fV = lastW>=0?nowV:0;
                fV = fV+(i>0&&returnList_prev[lastW-1]?returnList_prev[lastW-1]:0);
                var nV = i>0&&returnList_prev[j]?returnList_prev[j]:0;
                returnList[j] = Math.max(fV,nV);
            } else {
                var fV = lastW>=0?nowV:0;
                fV = fV+(i>0&&returnList[lastW-1]?returnList[lastW-1]:0);
                var nV = i>0&&returnList[j]?returnList[j]:0;
                returnList_prev[j] = Math.max(fV,nV);
            }
            
        }
        flag = !flag;
    }
    var endTime = new Date().getTime();
    return returnList[all-1]+"耗时:"+(endTime-startTime)+"ms";
}
console.log(bbb(weight,value,V));

对比了两次的结果时间分别是:

关于算法动态规划的实现优化

可以看到bbb方法明显比aaa快了一倍之多

这里只是想把自己看书后应用的东西分享下,大家有更好的方法也可以指正-。-


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

分布式算法导论

分布式算法导论

特尔 (Gerard Tel) / 电子工业出版社 / 2003-7 / 59.00

《分布式算法导论(第2版)(英文版)》由电子工业出版社出版。一起来看看 《分布式算法导论》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码