二叉堆计算动态中位数

要求

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

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

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

[……]

阅读全文

SOCKS5 协议解析

意图

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

代理

根据 HTTP 1.1 的定义,proxy 是[……]

阅读全文

goroutine, channel 和 CSP

引子

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

CSP 模型

Tony Hoare - Communicating Sequential ProcessesCSP 描述这样一种并发模型:多个Process 使用一[……]

阅读全文