一种节省空间的基于递归的线段树实现

使用先序遍历的节点访问顺序重新给左右儿子编号,大大节省了空间

自古以来,实现线段树所需要的数组空间大小有着比较激烈的争论。一种基于递归的线段树实现认为至少需要 $\mathcal {O}(4n)$ 的空间,而另一种基于直接循环的方法认为其实只需要 $2n-1$ 的空间。关于为什么基于递归的方法需要 $\mathcal {O}(4n)$ 的严格证明可以去网上搜索,或者 这里 提供了一个简易的证明方法。总的来说,基于递归的线段树实现起来更加直观,但由于 dummy node 的存在造成了空间的浪费。而基于直接循环的方法对实现的要求更高。本文介绍了一个基于递归的线段树实现,通过改变每个节点的左右儿子的编号高效的利用了空间,使得基于递归的线段树也只需要 $2n-1$ 的空间。另外,关于基于循环的线段树实现方法,可以参考 这篇博客

阅读更多

折腾 Hexo 第三弹 —— 集成一个自制插件,并使用 CI 实现自动升级主题,自动部署

探索折腾博客的终极意义

折腾博客的意义是什么?这两天看到群里有个人说的很对:虽然明知没人来看自己博客,但是折腾起来就是很爽。就像虽然看起来我像是博客 3 个多月没更新了,但实际上实际上我网站已经折腾了好几个月了,只是没有新写文章而已。总的来说,我把我原来对 NexT 主题的修改重新集成为一个 npm 插件,方便其他人使用。另外我添加了更多自动化的操作,不但以后只需要 push 新的文章,CI 就能自动更新网站。并且,Travis 的定时运行任务功能可以方便地自动拉取主题的最新代码,自动更新主题版本,从此再也没有主题过时的烦恼,简直爽歪歪。

阅读更多

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

学习一下 SOTA 语言模型

这篇文章可以称得上是 2018 年 NLP 方面一个里程碑式的论文了。当时,BERT 模型在 GLUE 评测榜上横扫其他所有模型,在 11 个 NLP 任务上达到最高。尽管这篇论文的阅读笔记在各种博客、论坛等地方都能看到,但我觉得仍然有必要仔细的阅读一遍原文。一来可以加深对论文的理解,二来通过阅读笔记的形式可以更好地记忆这篇文章的细节,不容易忘记。BERT 这篇文章通俗易懂,整体结构完整,条理非常清晰,适合所有学习 NLP 的人阅读。但阅读前需要对 Transformer 有所了解。

阅读更多

A Convolutional Neural Network for Modelling Sentences

使用 DCNN 对语言进行建模

概述

使用 CNN 进行语言建模已经取得了较广泛的应用。本文作者提出了一个动态卷积网络 DCNN,这是一个针对卷积神经网络的扩展,不需要依赖语法树,并且作者提出了许多比较新颖的概念,比如宽卷积、动态 k-max pooling,这些特性使得 DCNN 可以捕获长短依赖,并且丰富了 DCNN 提取的特征。

阅读更多

Convolutional Neural Networks for NLP Classification

今天的论文来自于较老的几篇论文,使用 CNN 进行文本分类。

CNN 最早被成功运用在图像处理中,因为图像的位置不变性、大小不变性使得 CNN 处理图像再适合不过。而将 CNN 运用于文本分类流行于 2014-2015 年左右,大概处于在 NLP 被 RNN 统治的前几年,因此虽然这些论文年代已经相对比较久远,但仍然值得一读,因为通过对这些论文的阅读,还能大致了解为什么 CNN 在 NLP 领域也能取得成功,CNN 在 NLP 领域存在什么问题,以及在 NLP 领域 CNN 的使用是如何慢慢过渡到 RNN 的使用的。

阅读更多

PyTorch 学习笔记

使用 PyTorch 的一些笔记,以防写完就忘,看完 API 又想起来,长此以往。

torch.nn

torch.nn.LSTM

LSTM 中的 hidden state 其实就是指每一个 LSTM cell 的输出,而 cell state 则是每次传递到下一层的「长时记忆」,我总觉得这个名字起的特别别扭,所以总不能很好的理解。下面这张图能更好的说明这些变量的意义。

LSTM

再来简单的回顾一下 LSTM 的几个公式

其中 $h_t$ 和 $c_t$ 就是所谓的 hidden statecell state 了。可以看到 LSTM 中所谓的 output gate,即 $o_t$ 其实是中间状态,它和 cell state 经过 $\tanh$ 相乘,得到了 hidden state,也就是输出值。

PyTorch 中 LSTM 的输出结果是一个二元组套二元组 (output, (h_n, c_n))。第一个 output 是每一个 timestamp 的输出,也就是每一个 cell 的 hidden state。第二个输出是一个二元组,分别表示最后一个 timestamp 的 hidden statecell state。因此,如果把 h_nc_n 记录下来,就可以保留整个 LSTM 的状态了。

PyTorch 中可以通过 bidirectional=True 来方便的将 LSTM 设置为双向,此时 output 会自动把每一个 timestamp 的正向和反向 LSTM 拼在一起。而 h_nc_n 的第一维长度会变为 2(单向是长度为 1)。而且此时有

即正向 output 的最后一个 timestemp(对应 LSTM 的最后一个 cell)的输出和正向的 hidden state 相同,反向 output 的最后一个 timestamp(对应 LSTM 的第一个 cell)的输出和反向的 hidden state 相同。

此外,在 PyTorch 中,LSTM 输出的形状和别的框架不太一样,它是序列长度优先的,(seq_len, batch_size, hz),如果觉得不习惯,可以通过 batch_first=True 来设定为 batch_size 优先。

[算法笔记 3] Codeforces - 1139 D. Steps to One

如何求出 1-n 每个数的全部因子?
在继续往下阅读之前,请先想一想,如果给定一个 $n,n\leq100000$,让你求出 1~n 的全部因子,你需要如何实现?要编写多少行代码?复杂度如何?

可能会这么考虑,如果对于每个数 $x$,枚举 1~n 逐一判断每个数是否是 $x$ 的因子,复杂度为 $\mathcal {O}(n^2)$,显然是不可接受的,即使枚举到 $\sqrt n$,复杂度也有 $\mathcal {O}(n \sqrt n)$,依然太大,有没有更好的办法?

阅读更多

[算法笔记 2] 动态规划

关于动态规划的一些新感悟。
自从这学期学校开设了算法课之后,受到算法课老师的鼓励我突然又有了写算法题的动力。特别是老师第一节课重新回顾的动态规划算法,使我对动态规划有了一些新的理解。

其实之前我一直对动态规划有一种说不出来的敬而远之地感受。我最早接触动态规划算法可以追溯到高中的时候了,那个时候去少年宫学各种算法 (顺便和小伙伴们愉快的玩耍),记得学到最短路径的 dijkstra 算法,当时学了之后不由感叹,哇!还能想出这样的算法,也太强了吧!这怎么想得出来嘛!所以从那个时候起我每次知道某道题要用动态规划去求解时总会不由自主地头大。因此其实很长一段时间以来,我的动态规划的水平仅仅停留在最粗浅的三角形路径最大问题上 (就是那个很 naive 的给一个三角形让你求一条路径使得从左上角到右上角权值和最大)。

阅读更多

使用腾讯云对象存储 COS 和亚马逊 CloudFront 部署 Hexo,开启自定义 HTTPS 域名

使用对象存储部署静态网站,并通过亚马逊 CDN (CloudFront) 大大加快网站的访问速度

我原来的 Hexo 博客部署在 GitHub Pages 上,因为 GitHub Pages 在国外,所以为了加快访问速度,我做了很多优化的工作。然而,连接的响应延迟实在是不能忍,初次打开网站的时间有时候可能要半分钟之久,另外 GitHub Pages 无法被百度访问到,因此百度也不会收录 GitHub Pages 部署的网站,所以我最近在不断寻找其他的代替方案。

阅读更多

进一步优化 Hexo 博客的访问速度

用尽各种手段,进一步将网站的传输开销缩短 70% 以上!

去年的 一篇文章 提到,把图片以及绝大部分的第三方 JS 和 CSS 文件转移到 CDN 加速服务上,源站的总传输大小从 500 多 KB 缩短到了 110KB,大约节省了 80% 的传输开销。今天,我又进一步优化了整个网站,最终测试下,首页仅有 33.3KB 的数据来自于源站,相比之前的约 110KB 又进一步节省了 70% 的大小。

阅读更多