xuhao 发布的文章

双向数据绑定原理分析

十几年前,前端还处于刀耕火种的时代,作为前端开发者,对于DOM的操作那是家常便饭了,可是当要修改的规模上升至一个很高的程度时,维护的成本就变得非常巨大,而消耗的性能也自然变得更大。这是不科学的,也是不太友好的。当前端进入到现代社会文明时,对于DOM的操作就变得慎之又慎,因此虚拟DOM就孕育而生。我们把所有的DOM节点抽象为DOM树的同时,也享受到了这样做带来的开发维护高效,以及页面相应的高性能体验。 双向数据绑定就是虚拟DOM的最大受益者。也很大程度上解放了前端的开发困境。下面我们对数据双向绑定(MVVM)进行原理探索。实现mini版本的双向数据绑定。

HTML片段

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
</head>
<body>
    <div id='app'>
        <h3>姓名</h3>
        <p>{{name}}</p>
        <h3>年龄</h3>
        <p>{{age}}</p>
    </div>
</body>
</html>

JS片段

<script>
document.addEventListener('DOMContentLoaded', function(){
    let opt = {el:'#app', data:{name:'填写中...', age:28}}
    let vm = new Vue(opt)
    setTimeout(() => {
        opt.data.name = '许浩'
    }, 2000);
}, false)
class Vue{
    constructor(opt){
        this.opt = opt
        this.observe(opt.data)
        let root = document.querySelector(opt.el)
        this.compile(root)
    }
    // 为响应式对象 data 里的每一个 key 绑定一个观察者对象
    observe(data){ 
        Object.keys(data).forEach(key => {
            let obv = new Observer() 
            data["_"+key] = data[key]
            // 通过 getter setter 暴露 for 循环中作用域下的 obv,闭包产生
            Object.defineProperty(data, key, {
                get(){
                    Observer.target && obv.addSubNode(Observer.target);
                    return data['_'+key]
                }, 
                set(newVal){
                    obv.update(newVal)
                    data['_'+key] = newVal
                }
            })
        })
    }
    // 初始化页面,遍历 DOM,收集每一个key变化时,随之调整的位置,以观察者方法存放起来    
    compile(node){
        [].forEach.call(node.childNodes, child =>{
            if(!child.firstElementChild && /\{\{(.*)\}\}/.test(child.innerHTML)){
                let key = RegExp.$1.trim()
                child.innerHTML = child.innerHTML.replace(new RegExp('\\{\\{\\s*'+ key +'\\s*\\}\\}', 'gm'),this.opt.data[key]) 
                Observer.target = child
                this.opt.data[key] 
                Observer.target = null
            }
            else if (child.firstElementChild) 
            this.compile(child)
        })
    }    
}
// 常规观察者类
class Observer{
    constructor(){
        this.subNode = []    
    }
    addSubNode(node){
        this.subNode.push(node)
    }
    update(newVal){
        this.subNode.forEach(node=>{
            node.innerHTML = newVal
        })
    }
}
</script>

一、冒泡排序(Bubble Sort)

作为最简单的排序算法之一 工作原理:它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

function bubbleSort(arr){
 var len = arr.length;
 for(var i=0; i<len; i++){
  for(var j=0; j<len-1-i; j++){
   if(arr[j]>arr[j+1]){ // 相邻元素两两对比
    var temp = arr[j+1]; // 元素交换
    arr[j+1] = arr[j];
    arr[j] = temp;
   }
  }
 }
 return arr;
}

- 阅读剩余部分 -

一、简单介绍

最大余额法,又称余额制。是比例代表制投票制度下,一种议席分配的方法,相对于最高均数方法。

二、该方案的优缺点

以最大余额方法分配议席不算复杂,一般选民应该能够理解运作方法。使用黑尔数额的最大余额方法,并不偏重得票率较多或较少的名单,好处在于能给出中立、但同时具广泛代表性的选举结果。最大余额方法能包容少数派,有利发展多党派的议会。这种制度也令选民不能投票给个别候选人;从正面的角度看,这代表选民会改以各份参选名单的政纲为投票考虑依据,加强选举的理性基础。不过,各个政党可能会有相应的“配票策略”,例如将同党候选人分拆在不同的名单,好让候选人能通过余额数当选。

三、主要解决问题:处理多个数据计算百分比之和不为100%的问题

我们在工作中会遇到一些需要计算的问题,在多个数据计算各自的百分比时候会有一些问题,比如因为数据精度的保留和取舍引起的个数据百分比只和不为100%的情况。而为了解决此类问题,我们就发现可以用最大余额法的思想去解决该问题。但是相应的也会损失部分数据的精度。下面就让我们用代码来对最大余额法的算法进行实现吧。

/*
 * @Author: xuhao 
 * @Description 最大余额法(解决:计算百分比的时候不能相加等于百分之百)
 * @Date: 2020-06-30 14:26:02 
 * @Last Modified by: xuhao
 * @Last Modified time: 2020-07-07 10:00:05
 */

export function getPercentValue(valueList, idx, precision) {
    // 判断是否为空
    if (!valueList[idx]) {
        return 0;
    }
    // 求和
    var sum = valueList.reduce(function (acc, val) {
        return acc + (isNaN(val) ? 0 : val);
    }, 0)
    if (sum === 0) {
        return 0;
    }
    // 10的2次幂是100,用于计算精度。
    var digits = Math.pow(10, precision);
    // 扩大比例100,
    var votesPerQuota = valueList.map(function (val) {
        return (isNaN(val) ? 0 : val) / sum * digits * 100;
    })
    // 总数,扩大比例意味的总数要扩大
    var targetSeats = digits * 100;
    // 再向下取值,组成数组
    var seats = votesPerQuota.map(function (votes) {
        return Math.floor(votes);
    })
    // 再新计算合计,用于判断与总数量是否相同,相同则占比会100%
    var currentSum = seats.reduce(function (acc, val) {
        return acc + val;
    }, 0)
    // 余数部分的数组:原先数组减去向下取值的数组,得到余数部分的数组
    var remainder = votesPerQuota.map(function (votes, idx) {
        return votes - seats[idx];
    })
    // 给最大最大的余额加1,凑个占比100%;
    while (currentSum < targetSeats) {
        //  找到下一个最大的余额,给其加1
        var max = Number.NEGATIVE_INFINITY;
        var maxId = null;
        for (var i = 0, len = remainder.length; i < len; ++i) {
            if (remainder[i] > max) {
                max = remainder[i];
                maxId = i;
            }
        }
        // 对最大项余额加1
        ++seats[maxId];
        // 已经增加最大余数加1,则下次判断就可以不需要再判断这个余额数。
        remainder[maxId] = 0;
        // 总的也要加1,为了判断是否总数是否相同,跳出循环。
        ++currentSum;
    }
    // 这时候的seats就会总数占比会100%
    return seats[idx] / digits
}

一、背景

在现代项目开发中,众所周知,对于excel的文件一般由后端开发人员做下载导出链接,进行导出功能的实现。而最近我在工作中遇到了这样的问题,就是表格的数据统计依赖总公司的综合数据,且数据类目庞大,因此后端查询接口在尽力优化下,每个接口也将近30s的反应时间,这对于用户来说是不友好的。而且页面呈现的数据报表已经等待了几十秒加载出来,如果在导出的时候还需要在进行等待重新访问接口,势必是对用户体验不太好。所以我决定通过前端来导出这些已经拿到的table数据。这样就可以节省二次访问时间啦~

二、依赖及解决的问题

依赖:element-ui-table + file-saver + xlsx 在项目中因为考虑到快速开发迭代的节奏,我们选用了Element-UI的Table组件。但是在导出excel的同时,也遇到了一些棘手的问题。

三、解决的问题

  1. 因为table组件中用到了fixed的属性,在过长的表格,用于对核心的数据列或数据表头进行固定。但是因为fixed的属性,在进行导出的时候会导出两个table。因为我们探究一下就可以发现,当table组件使用了fixed的属性时,对于固定单元和非固定单元是进行了不同table的拼接,因此我们在进行excel导出的时候要进行处理。 具体的处理方法是:在要导出时,先保存fixed的固定dom节点,然后删除它,进行数据导出以后,在进行append就好啦。
  2. 第二个问题是:在导出excel的时候,我们都知道,有sheet的分类,正常情况下是默认一个sheet的。但是如何在一个excel中导出含有多个sheet的文件呢。 具体的处理方法是:这个时候就要用到XLSX.utils.table_to_sheet()这个方法进行多sheet的拼接。
  3. 第三个问题是:导出的excel中如果是百分比的数据,导出的格式就是字符串形式,但是excel会有黄色的警告。其实对于这个问题也有解决。 具体的处理方法是:就是通过声明let xlsxParam = { raw: true } // 导出的内容只做解析,不进行格式转换。但是导出的时候确实数字了,不过就没有百分比的形式啦。举例:'80%' => 0.8 因此,这里我建议大家还是只做解析,不进行格式转换。
  4. 第四个问题就是对于excel的导出的兼容性和速度的取舍,涉及到这样一个属性bookSST: true。当bookSST为false就相应的降低了兼容性,但同时也提高了导出生成表格的速度。这里我考虑的是兼容性,因此我设置为true了。
/*
 * @Author: xuhao 
 * @Date: 2020-05-28 17:02:39 
 * @description: Table数据导出为excel文件,该导出为前端导出,依赖现有数据,少一次请求(部分请求最高达30s),节省用户等待时间。
 * @Last Modified by: xuhao
 * @Last Modified time: 2020-07-09 11:24:42
 */

//引入依赖
import FileSaver from 'file-saver';
import XLSX from 'xlsx';

// id为table的标示,title为table名称
export const exportExcel = (id, title) => {
  let ids, wbout;
  // 判断是否是含多sheet的excel
  if (id.includes(',')) { // 含多sheet的excel
    ids = JSON.parse(id)
    let workbook = XLSX.utils.book_new();
    let xlsxParam = { raw: true } // 导出的内容只做解析,不进行格式转换
    ids.forEach((item, index) => {
      let tableDom = document.querySelector(`#${item.key}`)
      let fix = document.querySelector(`#${item.key} .el-table__fixed`);
      if (fix) { // 如果存在固定列,防止导出的excel表格会重复两遍
        // workbook = XLSX.utils.table_to_sheet(dom, xlsxParam);
        XLSX.utils.book_append_sheet(workbook, XLSX.utils.table_to_sheet(tableDom.removeChild(fix), xlsxParam), item.name);
        tableDom.appendChild(fix)
      } else {
        XLSX.utils.book_append_sheet(workbook, XLSX.utils.table_to_sheet(document.querySelector(`#${item.key}`), xlsxParam), item.name);
      }
    })
    // bookSST 开启之后会降低导出速率,但是会提高兼容性
    wbout = XLSX.write(workbook, { bookType: 'xlsx', bookSST: true, type: 'array' });
  } else { // 单个默认sheet的excel
    ids = id
    /* generate workbook object from table */
    //  判断要导出的节点中是否有fixed属性(即,固定列)的表格,如果有,转换excel时先将该dom移除,然后append回去
    let fix = document.querySelector(`#${ids} .el-table__fixed`);
    let workbook;
    let xlsxParam = { raw: true } // 导出的内容只做解析,不进行格式转换
    if (fix) { // 如果存在固定列,防止导出的excel表格会重复两遍
      let dom = document.querySelector(`#${ids}`).removeChild(fix)
      workbook = XLSX.utils.table_to_book(dom, xlsxParam)
      document.querySelector(`#${ids}`).appendChild(fix)
    } else {
      workbook = XLSX.utils.table_to_book(document.querySelector(`#${ids}`), xlsxParam);
    }
    // bookSST 开启之后会降低导出速率,但是会提高兼容性
    wbout = XLSX.write(workbook, { bookType: 'xlsx', bookSST: true, type: 'array' });
  }
  /* get binary string as output */
  try {
    FileSaver.saveAs(new Blob([wbout], { type: 'application/octet-stream' }), title)
  } catch (e) {
    if (typeof console !== 'undefined') {
      console.log(e, wbout)
    }
  }
  return wbout
};

一、背景

在去年年底的时候,我的项目组开始了对于直播教学的开发和技术预研。我们都知道,直播教学中涉及到音频信号,视频信号,信令,以及师生笔记(Canvas的巨量Path数组)。因为在进行代码review的时候,我发现了,对于我们的实时师生笔记交互,信令因为也是实时传送的,因此会很高频,有时甚至遇到超频的问题被限制频率。所以我再想是不是可以对实时笔记的路径进行抽稀,这样我们传送的信令是不是就没那么多了。举例老师写了一个高中数学的公式,这个公式的JSON序列化队列假设是一个9000条的数组矩阵集合,那么我们运用抽稀算法,可以抽取其中的一些,是不是传送的信令就会变得少啦?性能是不是也就上来了?哈哈。等等,别急!!这个时候,有个问题我们应该注意了,就是你会疑惑抽稀以后笔记会不会失真呢?因为我们知道笔记的抽象就是和微积分的原理一样的,可以抽象为多个线段的集合拼接而成。因此如果没有章法的抽稀,势必会失真,那我们的优化也就失去了意义,不是吗?

二、解决方案

方案一: 这个时候我们可以想到著名的数学家D.Douglas和T.Peueker于1973年提出的道格拉斯—普克(Douglas一Peukcer)节点抽稀算法,简称D-P算法。 现有的线化简算法中,有相当一部分都是在该算法基础上进行改进产生的。它的长处是具有平移和旋转不变性,给定曲线与阂值后,抽样结果一定。本章线化简重点解说该算法。 算法的基本思路是: 对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax < D ,这条曲线上的中间点所有舍去;若dmax ≥D ,保留dmax 相应的坐标点,并以该点为界,把曲线分为两部分,对这两部分反复使用该方法。

算法的具体过程如下: (1) 在曲线首尾两点间虚连一条直线,求出其余各点到该直线的距离,如图3(1)。 (2) 选其最大者与阈值相比較,若大于阈值,则离该直线距离最大的点保留,否则将直线两端点间各点所有舍去,如图3(2),第4点保留。 (3) 根据所保留的点,将已知曲线分成两部分处理,反复第1、2步操作,迭代操作,即仍选距离最大者与阈值比較,依次取舍,直到无点可舍去,最后得到满足给定精度限差的曲线点坐标,如图3(3)、(4)依次保留第6点、第7点,舍去其它点,即完成线的化简。

方案二: 当我实现了第一种道格拉斯抽稀算法时,与我的项目结合完成时,我的脑子里灵光一现,好想有另一种方案。不知道大家还记得不记得我们上高中学习的等差数列。对等差数列的思路就是核心,抽象方法就是,进行整个线段的间隔性抽稀。就是下方CODE中的公差(抽稀程度)。举个例子,就是一条线段有100个点,我每隔4个点就抽取的话,就可以尽可能保证保真度的情况下进行抽稀动作。不得不承认,我比不过D.Douglas和T.Peueker两位老前辈

三、这就是无抽稀,道格拉斯抽稀,等差抽稀三种情况下的对比效果图

抽稀算法效果图.jpeg

四、代码实现(关于此篇文章,会后续继续完善,有很多想说的,相对比的还有待继续呈现...)

/*
 * @Author: xuhao 
 * @Date: 2019-12-30 15:01:14 
 * @Last Modified by: xuhao
 * @Last Modified time: 2020-03-09 00:56:41
 */

/*
* Desc: Performance Optimize For Live Class
* Function List: 
*    1.Arithmetic Progression Diluting Algorithm for Free Draw Path
*    2.Douglas Peucker Diluting Algorithm for Free Draw Path
*/

/*
 * 表现说明:目前来看,一般抽稀程度,等差数列抽稀算法所表现的抽稀后的轨迹更加清晰圆润,后期会继续优化。
 * 但极限抽取情况下,道格拉斯抽稀算法更胜一筹,总体轨迹不损。
*/

// 多维数组扁平化
const reduceDimension = (arr) => {
  return Array.prototype.concat.apply([], arr);
}

/*** 等差数列抽稀算法 Arithmetic-Progression-Diluting-Algorithm(creat by: xuhao)***/
// 数组等差分割函数【按(公差,即抽稀程度)进行)】
const splitArray = (tolerance, arr) => {
  let list = [],
    index;
  for (index = 0; index < arr.length;) {
    list.push(arr.slice(index, (index += tolerance)));
  }
  return list;
};

// 抽稀
const diluting = (arr) => {
  let vacuateArr = [];
  for (let i = 0; i < arr.length; i++) {
    let itemLen = arr[i].length;
    vacuateArr.push(arr[i][0]);
    // if(i!=0){
    //   vacuateArr.push(arr[i][Math.ceil((0+itemLen)/2)]);
    // }
    vacuateArr.push(arr[i][itemLen - 1]);
  }
  return vacuateArr;
};

/**
 *@param arr 原始轨迹Array
 *@param tolerance 抽稀程度系数,即 2/tolerance
 *@return rarefyingArr 抽稀后的轨迹
 */
// 等差数列抽稀 入口函数(后续会继续优化,取点算法)
const apDiluting = (arr, tolerance = 3) => {
  let arithmeticArr = splitArray(tolerance, arr);
  let rarefyingArr = diluting(arithmeticArr);
  return rarefyingArr;
}

/*** 道格拉斯-抽稀算法 Douglas-Peuker-Algorithm ***/
// 计算两点之间的距离
const calculationDistance = (point1, point2) => {
  // longitude,经度,即x轴上的值
  // latitude,纬度,即y轴上的值
  let lat1 = point1[point1.length - 1];
  let lat2 = point2[point2.length - 1];
  let lng1 = point1[1];
  let lng2 = point2[1];
  let radLat1 = (lat1 * Math.PI) / 180.0;
  let radLat2 = (lat2 * Math.PI) / 180.0;
  let a = radLat1 - radLat2;
  let b = (lng1 * Math.PI) / 180.0 - (lng2 * Math.PI) / 180.0;
  let s =
    2 *
    Math.asin(
      Math.sqrt(
        Math.pow(Math.sin(a / 2), 2) +
        Math.cos(radLat1) *
        Math.cos(radLat2) *
        Math.pow(Math.sin(b / 2), 2)
      )
    );
  return s * 6370996.81;
};

// 计算点pX到点pA和pB所确定的直线的距离
const distToSegment = (start, end, center) => {
  let a = Math.abs(calculationDistance(start, end));
  let b = Math.abs(calculationDistance(start, center));
  let c = Math.abs(calculationDistance(end, center));
  let p = (a + b + c) / 2.0;
  let s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
  return (s * 2.0) / a;
};

// 递归方式压缩轨迹
const compressLine = (coordinate, result, start, end, dMax) => {
  if (start < end) {
    let maxDist = 0;
    let currentIndex = 0;
    let startPoint = coordinate[start];
    let endPoint = coordinate[end];
    for (let i = start + 1; i < end; i++) {
      let currentDist = distToSegment(startPoint, endPoint, coordinate[i]);
      if (currentDist > maxDist) {
        maxDist = currentDist;
        currentIndex = i;
      }
    }
    if (maxDist >= dMax) {
      //将当前点加入到过滤数组中
      result.push(coordinate[currentIndex]);
      //将原来的线段以当前点为中心拆成两段,分别进行递归处理
      compressLine(coordinate, result, start, currentIndex, dMax);
      compressLine(coordinate, result, currentIndex, end, dMax);
    }
  }
  return result;
};

// 道格拉斯-抽稀 入口函数
/**
 *@param coordinate 原始轨迹Array
 *@param dMax 允许最大距离误差
 *@return douglasResult 抽稀后的轨迹
 */
const douglasPeucker = (coordinate, dMax = 10) => {
  if (!coordinate || !(coordinate.length > 2)) {
    return null;
  } else {
    coordinate.forEach((item, index) => {
      item['id'] = index;
    });
  }
  let result = compressLine(coordinate, [], 0, coordinate.length - 1, dMax);
  result.push(coordinate[0]);
  result.push(coordinate[coordinate.length - 1]);
  let resultLatLng = result.sort((a, b) => {
    if (a.id < b.id) {
      return -1;
    } else if (a.id > b.id) return 1;
    return 0;
  });
  resultLatLng.forEach(item => {
    item.id = undefined;
  });
  return resultLatLng;
};

export default {
  apDiluting,
  douglasPeucker,
  reduceDimension
}

参考文献