霍夫曼树和霍夫曼编码

一、定义

霍夫曼树

又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为 WPL =(W1*L1 + W2*L2 + W3*L3 +...+ Wn*Ln)N个权值 Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为 Li(i=1,2,...n)。可以证明霍夫曼树的 WPL 是最小的。

Huffman tree & encoding

霍夫曼编码

是一种基于霍夫曼树的用于无损数据压缩的熵编码(权编码)算法。

由于霍夫曼树具[……]

阅读全文

二叉堆计算动态中位数

要求

最近在刷算法,遇到一个有意思的题,要求如下:

设计一个数据结构,可随时插入节点,且随时查询节点集合的中位数,要求插入节点的时间复杂度为 O(logN),查询中位数的时间复杂度为 O(1)。

中位数定义:节点个数为奇数个时,为有序情况下集合的中间节点;偶数时,为中间两节点的平均值。

分析

求中位数,直觉的做法是先排序,然后根据数组的长度算出中位数,根据算法不同时间复杂度从 O(n) ~ O(NlogN) 不等。但这只适用于元素数目不变的情况,对可动态添加节点的情况,需要做到:

  1. 在插入时便进行重排序,时间复杂度为 O(logN)
  2. 不论节点个数奇偶,查中位数时间复[……]

阅读全文

岁末总结

岁末将至,且参照 去年 的格式,炮制一篇年度总结:

  • 看了 71 部电影,比上一年减少了 41 部
  • 看了书 21 本,比上一年增加了3本
  • 听了 299 张专辑,比一年增加了144张(大部分是古典 🙂

生活就似这浮浮沉沉的数据,不算太好,也没有更糟。

大的收获:

  • 我和孙老师正式结合成为了夫妻
  • 蜜月我第一次出国,目的地东京,非常美妙的旅程

大的调整:

  • 毅然放弃了舒适的工作环境,去到一家更为初创的公司,出任技术负责人

满打满算,我到这家初创 k12 公司,足有三个月,我以一个技术人的思维和韧劲,对这支半自动化的技术队伍进[……]

阅读全文

SOCKS5 协议解析

意图

SOCKS5 是一个代理协议,旨在为位于 Intranet 防火墙后的用户提供访问 Internet 的代理服务(Intranet,你没听错,这是个有一定年头的协议,其 RFC 提案的时间比 HTTP 1.0 还要早两个月)。

代理

根据 HTTP 1.1 的定义,proxy 是:

An intermediary program which acts as both a server and a client for the purpose of making requests on behalf of other clients. Requests are servic[……]

阅读全文

应用 Locust 快速上手写压测

引子

locust_logo 做为一个压测工具(库),locust 其实解决这么一个问题:AB 之类压测工具不能编写复杂的因果逻辑,而现实场景中,待压的服务往往是有一套完整执行流程的,比如 APP 要访问一个 API,是需要先鉴权(验明不是非 APP 访问),再登录换 Token,然后才是 API 调用……

这一切,在 locust 中都很容易实现,本质上,应用 locust 做压测,就是在写 Python 程序,只是它集成了一套不错的 UI,外加并发的benchmark功能。

至于写个压测为什么要用Python,是因为:这玩意心智负担低,你谷歌SO复制粘贴一把梭,直接上手就能写,大脑无需切换cont[……]

阅读全文

goroutine, channel 和 CSP

引子

老听 clojure 社区的人提起 core.async ,说它如何好用,如何简化了并发编程的模型,不由得勾起了我的好奇心,想了解一番其思想的源头:CSP 模型及受其启发的 goroutine 和 channel 。

CSP 模型

Tony Hoare - Communicating Sequential ProcessesCSP 描述这样一种并发模型:多个Process 使用一个 Channel 进行通信,  这个 Channel 连结的 Process 通常是匿名的,消息传递通常是同步的(有别于 Actor Model)。

CSP 最早是由 Tony Hoare 在 1977 年提出,据说老爷子至今仍在更新这个理论模型,有兴趣的朋友可以自行查阅电子版本:http:[……]

阅读全文

在 Node.js 中提供 gRPC 服务

引子

Web APP 的大行其道导致了 API 架构的流行,大量站点及服务使用基于 HTTP 1.1 的API 进行交互。这一类文本传输型 API 的优点很突出:易于编写和理解;支持异构平台的沟通。缺点也很明显:基于文本从而导致API传输内容过于庞大;存在客户端易感知的延迟。

如果对性能有所要求,不妨试试基于二进制传输的RPC框架,比如:

gRPC

gRPC 是一个高性能、开源的、通用的、面向移动端的 RPC 框架,传输协议基于 HTTP/2,这意味着它支持 双向流、流控、头部压缩、单 TCP 连接上的请求多路复用 等特性。

接口层面,gRPC默认使用 Protocol Bu[……]

阅读全文

WebSocket 的鉴权授权方案

引子

WebSocket 是个好东西,为我们提供了便捷且实时的通讯能力。然而,对于 WebSocket 客户端的鉴权,协议的 RFC 是这么说的:

This protocol doesn’t prescribe any particular way that servers can
authenticate clients during the WebSocket handshake. The WebSocket
server can use any client authentication mechanism available to a
generic HTTP server,[……]

阅读全文

算法复杂度和大O表示法

概念

SICP算法复杂度是算法分析里的概念(对应到SICP里的增长阶),是衡量计算资源消耗数量(例如计算时间,存储器使用等)的指标。

算法的复杂度在理论上表示为一个函数:其定义域是输入数据的长度(通常考虑任意大的输入,没有上界),值域通常是执行步骤数量(时间复杂度)或者存储器位置数量(空间复杂度)。

这个函数形如:

R(n) = Θ(f(n)) 亦可记做 O(f(n))

f(n) 就是被度量的算法主体;算法的复杂度标记就是大O(Θ读做theta),这种记法称为大O表示法

常见复杂度级别

  • Θ(1) 常数级别
  • Θ(log(n)) 对数级别
  • Θ(n) 线性级别
  • [……]

阅读全文

八皇后问题的Julia实现

问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?

尝试使用Julia实现一个回溯解:

实现

回溯法进行暴力查找:

很可惜,我的代码高亮插件不支持Julia的语法 🙁

输出