摸鱼儿

摸鱼儿 查看完整档案

北京编辑  |  填写毕业院校  |  填写所在公司/组织 segmentfault.com/u/moyuer 编辑
编辑

渺万里层云,千山暮雪,何不去摸鱼!

个人动态

摸鱼儿 赞了文章 · 3月7日

如何用 JS 实现二叉堆

这是第 90 篇不掺水的原创,想获取更多原创好文,请搜索公众号关注我们吧~ 本文首发于政采云前端博客:如何用 JS 实现二叉堆

如何用 JS 实现二叉堆

前言

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点、分支节点、叶子节点组成,如下图所示。每个分支节点也常常被称作为一棵子树,而二叉堆是一种特殊的树,它属于完全二叉树。

二叉树与二叉堆的关系

在日常工作中会遇到很多数组的操作,比如排序等。那么理解二叉堆的实现对以后的开发效率会有所提升,下面就简单介绍一下什么是二叉树,什么是二叉堆。

二叉树特征

  • 根节点:二叉树最顶层的节点
  • 分支节点:除了根节点以外且拥有叶子节点
  • 叶子节点:除了自身,没有其他子节点

在二叉树中,我们常常还会用父节点和子节点来描述,比如上图中左侧节点 2 为 6 和 3 的父节点,反之 6 和 3 是 2 子节点。

二叉树分类

二叉树分为满二叉树(full binary tree)和完全二叉树(complete binary tree)。

  • 满二叉树:一棵深度为 k 且有 2 ^ k - 1个节点的二叉树称为满二叉树
  • 完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉树结构

从图中我们可以看出二叉树是从上到下依次排列下来,可想而知可以用一个数组来表示二叉树的结构,从下标 index( 0 - 8 ) 从上到下依次排列。

3

  • 二叉树左侧节点表达式 index * 2 + 1。例如:以根节点为例求左侧节点,根节点的下标为0,则左侧节点的序数是1 ,对应数组中的值为1
  • 二叉树右侧节点表达式 index * 2 + 2。例如:以根节点为例求右侧节点,根节点的下标为0,则右侧节点的序数是2 ,对应数组中的值为 8
  • 二叉树叶子节点表达式 序数 >= floor( N / 2 )都是叶子节点(N是数组的长度)。例如:floor( 9 / 2 ) = 4 ,则从下标 4 开始的值都为叶子节点

二叉堆特征

二叉堆是一个完全二叉树,父节点与子节点要保持固定的序关系,并且每个节点的左子树和右子树都是一个二叉堆。

4

从上图可以看出

  • 图一:每个父节点大于子节点或等于子节点,满足二叉堆的性质
  • 图二:其中有一个父节点小于子节点则不满足二叉堆性质

二叉堆分类

​ 二叉堆根据排序不同,可以分为最大堆和最小堆

  • 最大堆:根节点的键值是所有堆节点键值中最大者,且每个父节点的值都比子节点的值大
  • 最小堆:根节点的键值是所有堆节点键值中最小者,且每个父节点的值都比子节点的值小

Untitled Diagram (1)

如何实现二叉堆

通过上面的讲述想必大家对二叉堆有了一定的理解,那么接下来就是如何实现。以最大堆为例,首先要初始化数组然后通过交换位置形成最大堆。

初始化二叉堆

从上面描述,我们可以知道二叉堆其实就是一个数组,那么初始化就非常简单了。

class Heap{
  constructor(arr){
    this.data = [...arr];
    this.size = this.data.length;
  }
}

父子节点交换位置

图一中 2 作为父节点小于子节点,很显然不符合最大堆性质。maxHeapify 函数可以把每个不符合最大堆性质的节点调换位置,从而满足最大堆性质的数组。

5

调整步骤:

1.调整分支节点 2 的位置(不满足最大堆性质)

2.获取父节点 2 的左右节点 ( 12 , 5 ) ,从 ( 2 , 15 , 5 ) 中进行比较

3.找出最大的节点与父节点进行交换,如果该节点本身为最大节点则停止操作

4.重复 step2 的操作,从 2 , 4 , 7 中找出最大值与 2 做交换(递归)

maxHeapify(i) {
  let max = i;

  if(i >= this.size){
    return;
  }
  // 当前序号的左节点
  const l = i * 2 + 1;
  // 当前需要的右节点
  const r = i * 2 + 2;

  // 求当前节点与其左右节点三者中的最大值
  if(l < this.size && this.data[l] > this.data[max]){
    max = l;
  }
  if(r < this.size && this.data[r] > this.data[max]){
    max = r;
  }

  // 最终max节点是其本身,则已经满足最大堆性质,停止操作
  if(max === i) {
    return;
  }

  // 父节点与最大值节点做交换
  const t = this.data[i];
  this.data[i] = this.data[max];
  this.data[max] = t;

  // 递归向下继续执行
  return this.maxHeapify(max);
}

形成最大堆

我们可以看到,初始化是由一个数组组成,以下图为例很显然并不会满足最大堆的性质,上述 maxHeapify 函数只是对某一个节点作出对调,无法对整个数组进行重构,所以我们要依次对数组进行递归重构。

6

1.找到所有分支节点 Math.floor( N / 2 )(不包括叶子节点)

2.将找到的子节点进行 maxHeapify 操作

rebuildHeap(){
  // 叶子节点
  const L = Math.floor(this.size / 2);
  for(let i = L - 1; i >= 0; i--){
    this.maxHeapify(i);
  }
}

生成一个升序的数组

B9AA42A8-8E58-4729-BF07-5164559E33BD

1.swap 函数交换首位位置

2.将最后一个从堆中拿出相当于 size - 1

3.执行 maxHeapify 函数进行根节点比较找出最大值进行交换

4.最终 data 会变成一个升序的数组

sort() {
  for(let i = this.size - 1; i > 0; i--){
    swap(this.data, 0, i);
    this.size--;
    this.maxHeapify(0);
  }
}

插入方法

Insert 函数作为插入节点函数,首先

1.往 data 结尾插入节点

2.因为节点追加,size + 1

3.因为一个父节点拥有 2 个子节点,我们可以根据这个性质通过 isHeap 函数获取第一个叶子节点,可以通过第一个叶子节点获取新插入的节点,然后进行 3 个值的对比,找出最大值,判断插入的节点。如果跟父节点相同则不进行重构(相等满足二叉堆性质),否则进行 rebuildHeap 重构堆

isHeap() {
  const L = Math.floor(this.size / 2);
  for (let i = L - 1; i >= 0; i--) {
    const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
    const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;

    const max = Math.max(this.data[i], l, r);

    if (max !== this.data[i]) {
      return false;
    }
    return true;
  }
}
insert(key) {
  this.data[this.size] = key;
  this.size++
  if (this.isHeap()) {
    return;
  }
  this.rebuildHeap();
}

删除方法

delete 函数作为删除节点,首先

1.删除传入index的节点

2.因为节点删除,size - 1

3.重复上面插入节点的操作

delete(index) {
  if (index >= this.size) {
    return;
  }
  this.data.splice(index, 1);
  this.size--;
  if (this.isHeap()) {
    return;
  }
  this.rebuildHeap();
}

完整代码

/**
 * 最大堆
 */

function left(i) {
  return (i * 2) + 1;
}

function right(i) {
  return (i * 2) + 2;
}

function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}

class Heap {
  constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
    this.rebuildHeap = this.rebuildHeap.bind(this);
    this.isHeap = this.isHeap.bind(this);
    this.sort = this.sort.bind(this);
    this.insert = this.insert.bind(this);
    this.delete = this.delete.bind(this);
    this.maxHeapify = this.maxHeapify.bind(this);
  }

  /**
   * 重构堆,形成最大堆
   */
  rebuildHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i--) {
      this.maxHeapify(i);
    }
  }

  isHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i--) {
      const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
      const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;

      const max = Math.max(this.data[i], l, r);

      if (max !== this.data[i]) {
        return false;
      }
      return true;
    }
  }

  sort() {
    for (let i = this.size - 1; i > 0; i--) {
      swap(this.data, 0, i);
      this.size--;
      this.maxHeapify(0);
    }
  }

  insert(key) {
    this.data[this.size++] = key;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  /**
   * 交换父子节点位置,符合最大堆特征
   * @param {*} i
   */
  maxHeapify(i) {
    let max = i;

    if (i >= this.size) {
      return;
    }

    // 求左右节点中较大的序号
    const l = left(i);
    const r = right(i);
    if (l < this.size && this.data[l] > this.data[max]) {
      max = l;
    }

    if (r < this.size && this.data[r] > this.data[max]) {
      max = r;
    }

    // 如果当前节点最大,已经是最大堆
    if (max === i) {
      return;
    }

    swap(this.data, i, max);

    // 递归向下继续执行
    return this.maxHeapify(max);
  }
}

module.exports = Heap;

示例

相信通过上面的讲述大家对最大堆的实现已经有了一定的理解,我们可以利用这个来进行排序。

const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7];
const fun = new Heap(arr);
fun.rebuildHeap(); // 形成最大堆的结构
fun.sort();// 通过排序,生成一个升序的数组
console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15]

总结

文章中主要讲述了二叉树、二叉堆的概念,然后通过代码实现二叉堆。我们可以通过二叉堆来做排序和优先级队列等。

推荐阅读

前端异常的捕获与处理

编写高质量可维护的代码:组件的抽象与粒度

招贤纳士

政采云前端团队(ZooTeam),一个年轻富有激情和创造力的前端团队,隶属于政采云产品研发部,Base 在风景如画的杭州。团队现有 40 余个前端小伙伴,平均年龄 27 岁,近 3 成是全栈工程师,妥妥的青年风暴团。成员构成既有来自于阿里、网易的“老”兵,也有浙大、中科大、杭电等校的应届新人。团队在日常的业务对接之外,还在物料体系、工程平台、搭建平台、性能体验、云端应用、数据分析及可视化等方向进行技术探索和实战,推动并落地了一系列的内部技术产品,持续探索前端技术体系的新边界。

如果你想改变一直被事折腾,希望开始能折腾事;如果你想改变一直被告诫需要多些想法,却无从破局;如果你想改变你有能力去做成那个结果,却不需要你;如果你想改变你想做成的事需要一个团队去支撑,但没你带人的位置;如果你想改变既定的节奏,将会是“5 年工作时间 3 年工作经验”;如果你想改变本来悟性不错,但总是有那一层窗户纸的模糊… 如果你相信相信的力量,相信平凡人能成就非凡事,相信能遇到更好的自己。如果你希望参与到随着业务腾飞的过程,亲手推动一个有着深入的业务理解、完善的技术体系、技术创造价值、影响力外溢的前端团队的成长历程,我觉得我们该聊聊。任何时间,等着你写点什么,发给 ZooTeam@cai-inc.com

查看原文

赞 16 收藏 10 评论 2

摸鱼儿 发布了文章 · 2月26日

神经网络处理啥

我们经常听说,图像识别或图像生成需要用到神经网络。

也经常听说,神经网络就是将大数据分类的一个技术,利用原始数据进行模型训练,直至生成可靠的分类器。

而这模型的基础架构就是利用,对基础输入,进行卷积计算,与“线性”权重组合而成的神经网络。

此后,利用对测试集的相似度对比,即距离,得到一个是非集。

可是,卷积到底卷得啥?这是个仁者见仁,智者见智的问题。

对于深度学习中图像处理相关的课题,目前主流科研及应用技术,大多卷积其实是卷的图像原始数据,比如说,一张10*10的黑白图像,输入即长度为100,值为0或1的数据。

我们可以用笨方法来,对每个值进行一个权重。也就得到了一个长度为100的权重w数组。
然后将通过卷积计算模型的output,通常为一个实数,与数据库中的已有图像进行对比,算出一个距离d,当d满足阈值时,就可以出结果了。

这时候你会迷惑,在不断通过模型的过程中,我要如何调整权重,以达到逐渐逼进的效果呢?这要利用梯度函数,找到极值,来判断应该下降还是上升权重。这时候我们不妨定义错误结果和正确结果之间的差距是一个损失函数,通过对权重们求导判断当前结果在通常为二次函数的曲线上是在哪个位置,由于要最小化loss,所以需要往极值处努力。

这只是个抽象的思路,我看过的书目中讲述得也不是很具体。所以算法很可能彻底弄反了。但我认为这才是其中的精粹的部分。具体实现原理我会在后期对比书目去写,就不在这空谈误国了。

查看原文

赞 0 收藏 0 评论 0

摸鱼儿 发布了文章 · 2月26日

神经网络是个啥?

我知道一个半径r作为参数,希望生成一张好看的脸。

我的脑容量里有10张图,分别是,猥琐男,大美女,技术宅,小萝莉,小正太,老奶奶,恐龙妹,高富帅,老夫子,凤凰男。

这时候,用户说,这些都不好看,我来画一个,你照着我的“超好看”风格,把这十种头像都给我画出来!

首先,我利用半径r,生成了一个圆圆的脑袋,然后,将用户画风提取出一个digest,再然后,从这个圆圆的脑袋不断地绘画,直到画出一个分类器认可是相应分类图像的图,也就完成了任务。

这是一个很复杂的脑力活,太累了,所以要借助一些仿生技术,即简单模仿人脑的神经网络来进行生成。

所以,神经网络是个啥?由于笔者要趁热吃眼前香喷喷的牛蛙,于是乎,且听下回分解!

查看原文

赞 0 收藏 0 评论 0

摸鱼儿 关注了问题 · 2019-09-15

m3u8前10秒画面卡顿

我有个m3u8的资源.每次播放的时候前10秒画面会卡住,声音正常.播放之后拖动到第0秒也会卡住
用的ffmpeg+videojs (视频经过一次转码的 所以codec是copy)

command.addAll(Arrays.asList("ffmpeg", "-y"));
command.addAll(Arrays.asList("-i", file));
command.addAll(Arrays.asList("-codec", "copy"));
command.addAll(Arrays.asList("-hls_time", "10"));
command.addAll(Arrays.asList("-threads", "8"));
command.addAll(Arrays.asList("-hls_key_info_file", keyInfoPath));
command.addAll(Arrays.asList("-hls_playlist_type", "vod"));
command.addAll(Arrays.asList("-hls_segment_filename", pathFile.getAbsolutePath()+"/index%d.ts"));
command.add(convertPath);

在线测试地址

https://www.m3u8play.com/?play=https://cdn.zhixueyun.com/default/M00/05/C9/CqJGV10v5NyECg5jAAAAAKnCCyI547_t/index.m3u8

关注 2 回答 1

摸鱼儿 回答了问题 · 2019-09-15

m3u8前10秒画面卡顿

谢邀……具体问题我不太清楚啦,但是要进一步测试的话,用node在后端可以把m3u8文件拆解,m3u8文件实质上就是一系列ts文件,印象里ts文件是可以直接转码播放的。另外m3u8在不同浏览器里支持程度不一样,出问题很正常。我之前因工作中需要调研m3u8格式的VR视频播放器,一些比较成熟的播放器框架,在浏览器兼容以及播放效果上的完善也都只是起步阶段。

关注 2 回答 1

摸鱼儿 关注了标签 · 2019-09-15

一起分享你的故事

SegmentFault思否征文 | 一起分享你的编程故事吧~

关注 12

摸鱼儿 关注了收藏夹 · 2019-03-05

带你入门 gRPC

关注 225

摸鱼儿 关注了收藏夹 · 2018-12-24

带你入门 gRPC

关注 225

摸鱼儿 发布了文章 · 2017-04-03

Node + FFmpeg 实现Canvas动画导出视频

导言

Canvas为前端提供了动画展示的平台,随着现在视频娱乐的流行,你是否想过把Canvas动画导出视频?目前纯前端的视频编码转换(例如WebM Encoder Whammy)还存在许多限制,较为成熟的方案是将每帧图片传给后端实现,由后端调用FFmpeg进行视频转码。整体流程并不复杂,这篇文章将带大家实现这个过程。

整体方案

  • 由前端记录Canvas动画的每帧图像,以base64字符串形式传给后端

  • 利用node fluent-ffmpeg模块,调用FFmpeg将图片合并成视频,并将视频存储在server端,并返回相应下载url

  • 前端通过请求得到视频文件

前端部分

每帧图片生成

图片生成可以通过canvas原生接口toDataURL实现,最终返回base64形式的图像数据。

generatePng () {
  ...
  var imgData = canvas.toDataURL("image/png");
  return imgData;
}

动画录制与图片流传输

动画的记录与传送是个异步过程,这里返回一个Promise,等待后端处理完毕,收到回应后,即完成此异步过程。

以下代码将canvas每帧动画信息存入一个图片数组imgs中,将数组转成字符串的形式传给后端。注意这里contentType设置为“text/plain”。

generateVideo () {
  var that = this;
  return new Promise (
    function (resolve, reject) {
      var imgs = [];
      ...
      window.requestAnimationFrame(that.recordTick.bind(that, imgs, resolve, reject));
    }
  )
}
recordTick (imgs, resolve, reject) {
  ...//每帧动画的记录信息,如时间戳等

  if (...) {//动画终止条件
    this.stopPlay();
    imgs.push(this.generatePng());
    $.ajax({
      url: '/video/record',
      data: imgs.join(' '),
      method: 'POST',
      contentType: 'text/plain',
      success: function (data, textStatus, jqXHR) {
        resolve(data);
      },
      error: function (jqXHR, textStatus, errorThrown) {
        reject(errorThrown);
      }
    });
  } else {
    ...//每帧动画展示的代码

    imgs.push(this.generatePng());
    window.requestAnimationFrame(this.recordTick.bind(this, imgs, resolve, reject));
  }
}

视频下载

上一节代码中,动画停止时,会通过post请求给后端传送所有图片数据,后端处理完毕后,返回数据中包含一个url,此url即为视频文件的下载地址。

为了支持浏览器端用户点击下载,我们需要用到a标签的download属性,此属性可以支持点击a标签后下载指定文件。

editor.generateVideo().then(function (data) {
  videoRecordingModal.setDownloadLink(data.url, data.filename);
  videoRecordingModal.changeStatus('recorded');
});
setDownloadLink: function (url, filename) {
  this.config.$dom.find('.video-download').attr('href', url);
  this.config.$dom.find('.video-download').attr('download', filename);
}

后端部分

图片序列生成

接收到前端传送的图片数据后,我们首先需要将图片解析、存储在服务器中,我们建立以当前时间戳命名的文件夹,将图片序列以一定格式存储于其中。由于每张图片写入都是异步过程,为确保所有图片都已处理完毕后,才执行视频转码过程,我们需要用到Promise.all。

Promise.all(imgs.map(function (value, index) {
  var img = decodeBase64Image(value)
  var data = img.data
  var type = img.type
  return new Promise(function (resolve, reject) {
    fs.writeFile(path.resolve(__dirname, (folder + '/img' + index + '.' + type)), data, 'base64', function(err) {
      if (err) {
        reject(err)
      } else {
        resolve()
      }
    })
  })
})).then(function () {
  …//视频转码
})

其中decodeBase64Image函数参考这里

视频生成

视频生成利用FFmpeg转码工具。
首先确保server端安装了FFmpeg

brew install ffmpeg

在项目中安装fluent-ffmpeg,这是node调用ffmpeg的接口模块

npm install fluent-ffmpeg --save

结合上一节图片序列存储的代码,整个接口代码如下:

app.post('/video/record', function(req, res) {
  var imgs = req.text.split(' ')
  var timeStamp = Date.now()
  var folder = 'images/' + timeStamp
  if (!fs.existsSync(resolve(folder))){
    fs.mkdirSync(resolve(folder));
  }

  Promise.all(imgs.map(function (value, index) {
    var img = decodeBase64Image(value)
    var data = img.data
    var type = img.type
    return new Promise(function (resolve, reject) {
      fs.writeFile(path.resolve(__dirname, (folder + '/img' + index + '.' + type)), data, 'base64', function(err) {
        if (err) {
          reject(err)
        } else {
          resolve()
        }
      })
    })
  })).then(function () {
    var proc = new ffmpeg({ source: resolve(folder + '/img%d.png'), nolog: true })
      .withFps(25)
      .on('end', function() {
        res.status(200)
        res.send({
          url: '/video/mpeg/' + timeStamp,
          filename: 'jianshi' + timeStamp + '.mpeg'
        })
      })
      .on('error', function(err) {
        console.log('ERR: ' + err.message)
      })
      .saveToFile(resolve('video/jianshi' + timeStamp + '.mpeg'))
  })
})

视频下载

最终将视频文件传输给前端的接口代码如下:

app.get('/video/mpeg/:timeStamp', function(req, res) {
  res.contentType('mpeg');
  var rstream = fs.createReadStream(resolve('video/jianshi' + req.params.timeStamp + '.mpeg'));
  rstream.pipe(res, {end: true});
})

效果预览

图片描述

注:此功能是个人项目”简诗”的一部分,完整代码可以查看https://github.com/moyuer1992...

查看原文

赞 18 收藏 36 评论 3

摸鱼儿 关注了标签 · 2017-04-01

spark

Spark是一种基于内存的分布式大数据处理框架,提供scala、java、r、python的语音接口。

关注 448

认证与成就

  • 获得 47 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-01-04
个人主页被 1.4k 人浏览