瀑布流布局:教你如何用动态规划和贪心算法实现

 2021-07-09 2:10    77  

瀑布流布局:教你如何用动态规划和贪心算法实现前端瀑布流布局「实践」

瀑布流布局:教你如何用动态规划和贪心算法实现前端瀑布流布局「实践」

瀑布流布局:教你如何用动态规划和贪心算法实现前端瀑布流布局「实践」

作者瀑布流布局:ssh前端

瀑布流布局:教你如何用动态规划和贪心算法实现前端瀑布流布局「实践」

转发链接瀑布流布局:://mp.weixin.qq.com/s/yT0D1qug4Q3YOrCCYf9nKA

瀑布流布局:教你如何用动态规划和贪心算法实现前端瀑布流布局「实践」

前言瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列瀑布流布局。

我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能的接近,这样的布局会非常的美观。

预览

分析从预览图中可以看出,虽然图片的高度是不定的,但是到了这个布局的最底部,左右两张图片是正好对齐的,这就是一个比较美观的布局了。

那么怎么实现这个需求呢?从头开始拆解,现在我们能拿到一组图片数组 [img1, img2, img3],我们可以通过一些方法得到它对应的高度 [1000, 2000, 3000],那么现在我们的目标就是能够计算出左右两列 left: [1000, 2000] 和 right: [3000] 这样就可以把一个左右等高的布局给渲染出来了。

准备工作首先准备好小姐姐数组 SISTERS:

let SISTERS = [  '://pic3.zhimg.com/v2-89735fee10045d51693f1f74369aaa46_r.jpg',  '://pic1.zhimg.com/v2-ca51a8ce18f507b2502c4d495a217fa0_r.jpg',  '://pic1.zhimg.com/v2-c90799771ed8469608f326698113e34c_r.jpg',  '://pic1.zhimg.com/v2-8d3dd83f3a419964687a028de653f8d8_r.jpg',  ... more 50 items]准备好一个工具方法 loadImages,这个方法的目的就是把所有图片预加载以后获取对应的高度,放到一个数组里返回。并且要对外通知所有图片处理完成的时机,有点类似于 Promise.all 的思路。

这个方法里,我们把图片按照 宽高比 和屏幕宽度的一半进行相乘,得到缩放后适配屏宽的图片高度。

let loadImgHeights = (imgs) => {  return new Promise((resolve, reject) => {    const length = imgs.length    const heights = []    let count = 0    const load = (index) => {      let img = new Image()      const checkIfFinished = () => {        count++        if (count === length) {          resolve(heights)        }      }      img.onload = () => {        const ratio = img.height / img.width        const halfHeight = ratio * halfInnerWidth        // 高度按屏幕一半的比例来计算        heights[index] = halfHeight        checkIfFinished()      }      img.onerror = () => {        heights[index] = 0        checkIfFinished()      }      img.src = imgs[index]    }    imgs.forEach((img, index) => load(index))  })}有了图片高度以后,我们就开始挑选适合这个需求的算法了。

贪心算法在人的脑海中最直观的想法是什么样的?在每装一个图片前都对比一下左右数组的高度和,往高度较小的那个数组里去放入下一项。

这就是贪心算法,我们来简单实现下:

let greedy = (heights) => {  let mid = Math.round(sum(heights) / 2)  let total = 0  let leftHeights = []  let rightHeights = []  let left = []  let right = []  heights.forEach((height, index) => {    if (sum(leftHeights) > sum(rightHeights)) {      right.push(index)      rightHeights.push(height)    } else {      left.push(index)      leftHeights.push(height)    }    total += height  })  return { left, right }}我们得到了 left,right 数组,对应左右两列渲染图片的下标,并且我们也有了每个图片的高度,那么渲染到页面上就很简单了:

<div class="wrap" v-if="imgsLoaded">  <div class="half">    <img      class="img"      v-for="leftIndex in leftImgIndexes"      :src="imgs[leftIndex]"      :style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }"    />  </div>  <div class="half">    <img      class="img"      v-for="rightIndex in rightImgIndexes"      :src="imgs[rightIndex]"      :style="{ width: '100%', height: imgHeights[rightIndex] + 'px' }"    />  </div></div>效果如图:

预览地址:://sl1673495.github.io/dp-waterfall/greedy.html

可以看出,贪心算法只寻求局部最优解(只在考虑当前图片的时候找到一个最优解),所以最后左右两边的高度差还是相对较大的,局部最优解很难成为全局最优解。

再回到文章开头的图片去看看,对于同样的一个图片数组,那个预览图里的高度差非常的小,是怎么做到的呢?

动态规划和局部最优解对应的是全局最优解,而说到全局最优解,我们很难不想到动态规划这种算法。它是求全局最优解的一个利器。

如果你还没有了解过动态规划,建议你看一下海蓝大佬的 一文搞懂动态规划[2],也是这篇文章让我入门了最基础的动态规划。

动态规划中有一个很著名的问题:「01 背包问题」,题目的意思是这样的:

有 n 个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

关于 01 背包问题的题解,网上不错的教程似乎不多,我推荐看慕课网 bobo 老师的玩转算法面试 从真题到思维全面提升算法思维[3] 中的第九章,会很仔细的讲解背包问题,对于算法思维有很大的提升,这门课的其他部分也非常非常的优秀。

我也有在我自己维护的题解仓库中对老师的 01 背包解法做了一个js 版的改写[4]。

那么 01 背包问题和这个瀑布流算法有什么关系呢?这个思路确实比较难找,但是我们仔细想一下,假设我们有 [1, 2, 3] 这 3 个图片高度的数组,我们怎么通过转化成 01 背包问题呢?

由于我们要凑到的是图片总高度的一半,也就是 (1 + 2 + 3) / 2 = 3,那么我们此时就有了一个 容量为3 的背包,而由于我们装进左列中的图片高度需要低于总高度的一半,待装进背包的物体的总重量和高度是相同的 [1, 2, 3]。

那么这个问题也就转化为了,在 容量为3的背包 中,尽可能的总重量为 [1, 2, 3],并且价值也为 [1, 2, 3] 的物品中,尽可能的挑选出总价值最大的物品集合装进背包中。

也就是 总高度为3,在 [1, 2, 3] 这几种高度的图片中,尽可能挑出 总和最大,但是又小于3 的图片集合,装进数组中。

二维数组结构我们构建的二维 dp 数组

纵坐标 y 是:当前可以考虑的图片,比如 dp[0] 是只考虑下标为 0 的图片,dp[1] 是考虑下标为 0 的图片,并且考虑下标为 1 的图片,以此类推,取值范围是0 ~ 图片数组的长度 - 1。

横坐标 x 是:用当前考虑的图片集合,去尽可能凑到总高度为 y 时,所能凑成的最大高度 max,以及当前所使用的图片下标集合 indexes,取值范围是 0 ~ 高度的一半。

小问题拆解就以 [1, 4, 5, 4] 这四张图片高度为例,高度的一半是 7,用肉眼可以看出最接近 7 的子数组是[1, 5],我们来看看动态规划是怎么求出这个结果的。

我们先看纵坐标为 0,也就是只考虑图片 1 的情况:

首先去尝试凑高度 1:我们知道图片 1 的高度正好是 1,所以此时dp[0][0]所填写的值是 { max: 1, indexes: [0] },也就代表用总高度还剩 1,并且只考虑图片 1 的情况下,我们的最优解是选用第一张图片。凑高度2 ~ 7:由于当前只有 1 可以选择,所以最优解只能是选择第一张图片,它们都是 { max: 1, indexes: [0] }。高度 1 2 3 4 5 6 7图片1(h=1) 1 1 1 1 1 1 1这一层在动态规划中叫做基础状态,它是最小的子问题,它不像后面的纵坐标中要考虑多张图片,而是只考虑单张图片,所以一般来说都会在一层循环中单独把它求解出来。

这里我们还要考虑第一张图片的高度大于我们要求的总高度的情况,这种情况下需要把 max 置为 0,选择的图片项也为空。

let mid = Math.round(sum(heights) / 2)let dp = []// 基础状态 只考虑第一个图片的情况dp[0] = []for (let cap = 0; cap <= mid; cap++) {  dp[0][cap] =    heights[0] > cap      ? { max: 0, indexes: [] }      : { max: heights[0], indexes: [0] }}有了第一层的基础状态后,我们就可以开始考虑多张图片的情况了,现在来到了纵坐标为 1,也就是考虑图片 1 和考虑图片 2 时求最优解:

高度 1 2 3 4 5 6 7图片1(h=1) 1 1 1 1 1 1 1图片1(h=2)此时问题就变得有些复杂了,在多张图片的情况下,我们可以有两种选择:

选择当前图片,那么假设当前要凑的总高度为 3,当前图片的高度为 2,剩余的高度就为 1,此时我们可以用剩余的高度去「上一个纵坐标」里寻找「只考虑前面几种图片」的情况下,高度为 1 时的最优解。并且记录 当前图片的高度 + 前几种图片凑剩余高度的最优解 为 max1。不选择当前图片,那么就直接去「只考虑前面几种图片」的上一个纵坐标里,找到当前高度下的最优解即可,记为 max2。比较 max1 和max2,找出更大的那个值,记录为当前状态下的最优解。有了这个前置知识,来继续分解这个问题,在纵坐标为 1 的情况下,我们手上可以选择的图片有图片 1 和图片 2:

凑高度 1:由于图片 2 的高度为 2,相当于是容量超了,所以这种情况下不选择图片 2,而是直接选择图片 1,所以 dp[1][0] 可以直接沿用 dp[0][0]的最优解,也就是 { max: 1, indexes: [0] }。凑高度 2:选择图片 2,图片 2 的高度为 4,能够凑成的高度为 4,已经超出了当前要凑的高度 2,所以不能选择图片 2。不选择图片 2,在只考虑图片 1 时的最优解数组 dp[0] 中找到高度为 2 时的最优解:dp[0][2],直接沿用下来,也就是 { max: 1, indexes: [0] }这种情况下只能不选择图片 2,而沿用只选择图片 1 时的解, { max: 1, indexes: [0] }省略凑高度 3 ~ 4 的情况,因为得出的结果和凑高度 2 是一样的。凑高度 5:高度为 5 的情况下就比较有意思了:选择图片 2,图片 2 的高度为 4,能够凑成的高度为 4,此时剩余高度是 1,再去只考虑图片 1 的最优解数组 dp[0]中找高度为 1 时的最优解dp[0][1],发现结果是 { max: 1, indexes: [0] },这两个高度值 4 和 1 相加后没有超出高度的限制,所以得出最优解:{ max: 5, indexes: [0, 1] }不选择图片 2,在图片 1 的最优解数组中找到高度为 5 时的最优解:dp[0][5],直接沿用下来,也就是 { max: 1, indexes: [0] }很明显选择图片 2 的情况下,能凑成的高度更大,所以 dp[1][2] 的最优解选择 { max: 5, indexes: [0, 1] }仔细理解一下,相信你可以看出动态规划的过程,从最小的子问题 只考虑图片1出发,先求出最优解,然后再用子问题的最优解去推更大的问题 考虑图片1、2、考虑图片1、2、3的最优解。

画一下[1,4,5,4]问题的 dp 状态表吧:

可以看到,和我们刚刚推论的结果一致,在考虑图片 1 和图片 2 的情况下,凑高度为 5,也就是dp[1][5]的位置的最优解就是 5。最右下角就是全局的最优解了。

给出代码:

// 尽可能选出图片中高度最接近图片总高度一半的元素let dpHalf = (heights) => {  let mid = Math.round(sum(heights) / 2)  let dp = []  // 基础状态 只考虑第一个图片的情况  dp[0] = []  for (let cap = 0; cap <= mid; cap++) {    dp[0][cap] =      heights[0] > cap        ? { max: 0, indexes: [] }        : { max: heights[0], indexes: [0] }  }  for (    let useHeightIndex = 1;    useHeightIndex < heights.length;    useHeightIndex++  ) {    if (!dp[useHeightIndex]) {      dp[useHeightIndex] = []    }    for (let cap = 0; cap <= mid; cap++) {      let usePrevHeightDp = dp[useHeightIndex - 1][cap]      let usePrevHeightMax = usePrevHeightDp.max      let currentHeight = heights[useHeightIndex]      // 这里有个小坑 剩余高度一定要转化为整数 否则去dp数组里取到的就是undefined了      let useThisHeightRestCap = Math.round(cap - heights[useHeightIndex])      let useThisHeightPrevDp = dp[useHeightIndex - 1][useThisHeightRestCap]      let useThisHeightMax = useThisHeightPrevDp        ? currentHeight + useThisHeightPrevDp.max        : 0      // 是否把当前图片纳入选择 如果取当前的图片大于不取当前图片的高度      if (useThisHeightMax > usePrevHeightMax) {        dp[useHeightIndex][cap] = {          max: useThisHeightMax,          indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex),        }      } else {        dp[useHeightIndex][cap] = {          max: usePrevHeightMax,          indexes: usePrevHeightDp.indexes,        }      }    }  }  return dp[heights.length - 1][mid]}有了一侧的数组以后,我们只需要在数组中找出另一半,即可渲染到屏幕的两列中:

this.leftImgIndexes = dpHalf(imgHeights).indexesthis.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes)得出效果:

代码地址预览地址[5]

://sl1673495.github.io/dp-waterfall

完整代码地址[6]

://github.com/sl1673495/dp-waterfall/blob/master/index.html

总结算法思想在前端中的应用还是可以见到不少的,本文只是为了演示动态规划在求解最优解问题时的威力,并不代表这种算法适用于生产环境(实际上性能非常差)。

在实际场景中我们可能一定需要最优解,而只是需要左右两侧的高度不要相差的过大就好,那么这种情况下简单的贪心算法完全足够。

在业务工程中,我们需要结合当前的人力资源,项目周期,代码可维护性,性能等各个方面,去选择最适合业务场景的解法,而不一定要去找到那个最优解。

但是算法对于前端来说还是非常重要的,想要写出 bug free 的代码,在复杂的业务场景下也能游刃有余的想出优化复杂度的方法,学习算法是一个非常棒的途径,这也是工程师必备的素养。

推荐JavaScript经典实例学习资料文章《可视化的 js:动态图演示 Promises & Async/Await 的过程》

《原生JS封装拖动验证滑块你会吗?「实践」》

《如何实现高性能的在线 PDF 预览》

《细说使用字体库加密数据-仿58同城》

《Node.js要完了吗?》

《Pug 3.0.0正式发布,不再支持 Node.js 6/8》

《纯JS手写轮播图(代码逻辑清晰,通俗易懂)》

《JavaScript 20 年 中文版之创立标准》

《值得收藏的前端常用60余种工具方法「JS篇」》

《箭头函数和常规函数之间的 5 个区别》

《通过发布/订阅的设计模式搞懂 Node.js 核心模块 Events》

《「前端篇」不再为正则烦恼》

《「速围」Node.js V14.3.0 发布支持顶级 Await 和 REPL 增强功能》

《深入细品浏览器原理「流程图」》

《JavaScript 已进入第三个时代,未来将何去何从?》

《前端上传前预览文件 image、text、json、video、audio「实践」》

《深入细品 EventLoop 和浏览器渲染、帧动画、空闲回调的关系》

《推荐13个有用的JavaScript数组技巧「值得收藏」》

《前端必备基础知识:window.location 详解》

《不要再依赖CommonJS了》

《犀牛书作者:最该忘记的JavaScript特性》

《36个工作中常用的JavaScript函数片段「值得收藏」》

《Node + H5 实现大文件分片上传、断点续传》

《一文了解文件上传全过程(1.8w字深度解析)「前端进阶必备」》

《【实践总结】关于小程序挣脱枷锁实现批量上传》

《手把手教你前端的各种文件上传攻略和大文件断点续传》

《字节跳动面试官:请你实现一个大文件上传和断点续传》

《谈谈前端关于文件上传下载那些事【实践】》

《手把手教你如何编写一个前端图片压缩、方向纠正、预览、上传插件》

《最全的 JavaScript 模块化方案和工具》

《「前端进阶」JS中的内存管理》

《JavaScript正则深入以及10个非常有意思的正则实战》

《前端面试者经常忽视的一道JavaScript 面试题》

《一行JS代码实现一个简单的模板字符串替换「实践」》

《JS代码是如何被压缩的「前端高级进阶」》

《前端开发规范:命名规范、html规范、css规范、js规范》

《【规范篇】前端团队代码规范最佳实践》

《100个原生JavaScript代码片段知识点详细汇总【实践】》

《关于前端174道 JavaScript知识点汇总(一)》

《关于前端174道 JavaScript知识点汇总(二)》

《关于前端174道 JavaScript知识点汇总(三)》

《几个非常有意思的javascript知识点总结【实践】》

《都2020年了,你还不会JavaScript 装饰器?》

《JavaScript实现图片合成下载》

《70个JavaScript知识点详细总结(上)【实践】》

《70个JavaScript知识点详细总结(下)【实践】》

《开源了一个 JavaScript 版敏感词过滤库》

《送你 43 道 JavaScript 面试题》

《3个很棒的小众JavaScript库,你值得拥有》

《手把手教你深入巩固JavaScript知识体系【思维导图】》

《推荐7个很棒的JavaScript产品步骤引导库》

《Echa哥教你彻底弄懂 JavaScript 执行机制》

《一个合格的中级前端工程师需要掌握的 28 个 JavaScript 技巧》

《深入解析高频项目中运用到的知识点汇总【JS篇】》

《JavaScript 工具函数大全【新】》

《从JavaScript中看设计模式(总结)》

《身份证号码的正则表达式及验证详解(JavaScript,Regex)》

《浏览器中实现JavaScript计时器的4种创新方式》

《Three.js 动效方案》

《手把手教你常用的59个JS类方法》

《127个常用的JS代码片段,每段代码花30秒就能看懂-【上】》

《深入浅出讲解 js 深拷贝 vs 浅拷贝》

《手把手教你JS开发H5游戏【消灭星星】》

《深入浅出讲解JS中this/apply/call/bind巧妙用法【实践】》

《手把手教你全方位解读JS中this真正含义【实践】》

《书到用时方恨少,一大波JS开发工具函数来了》

《干货满满!如何优雅简洁地实现时钟翻牌器(支持JS/Vue/React)》

《手把手教你JS 异步编程六种方案【实践】》

《让你减少加班的15条高效JS技巧知识点汇总【实践】》

《手把手教你JS开发H5游戏【黄金矿工】》

《手把手教你JS实现监控浏览器上下左右滚动》

《JS 经典实例知识点整理汇总【实践】》

《2.6万字JS干货分享,带你领略前端魅力【基础篇】》

《2.6万字JS干货分享,带你领略前端魅力【实践篇】》

《简单几步让你的 JS 写得更漂亮》

《恭喜你获得治疗JS this的详细药方》

《谈谈前端关于文件上传下载那些事【实践】》

《面试中教你绕过关于 JavaScript 作用域的 5 个坑》

《Jquery插件(常用的插件库)》

《【JS】如何防止重复发送ajax请求》

《JavaScript+Canvas实现自定义画板》

《Continuation 在 JS 中的应用「前端篇」》

作者:ssh前端

转发链接:://mp.weixin.qq.com/s/yT0D1qug4Q3YOrCCYf9nKA

本文标签:前端何用

原文链接:https://www.xgfox.com/bcrm/672.html

本文版权:如无特别标注,本站文章均为原创。