XGBoost 是陈天奇(怪)领衔开发的一套 Gradient Boost 算法实现,比如我会用到它做 LambdaMART 的实验。如果要给它一个评价,那应该是:好用、耐操。

不过,也有甜蜜的烦恼。XGBoost 在每轮迭代后,能够贴心地给出模型在数据集上的指标。比如我会关心 NDCG 指标。然而,这里列印出来的指标,会比事后用标准算法计算出来的值要高不少。

阅读全文 »

所谓字符串匹配,就是拿着一个字符串(也称为模式串),去到另一个字符串(母串)里去查找完全相同的子串的过程。显然,只要能定义相等关系,那么字符串匹配算法可以扩展到任意的序列匹配算法。因此,这会是一类用途很广的算法。

解决字符串匹配问题,最朴素的办法就是拿着模式串逐字符地沿着待匹配的串去比对,每次向前移动一个字符,直到完全匹配或者找不到匹配。显然,这个算法的复杂度是 $O(n\cdot m)$($n$ 表示母串的长度,$m$ 表示模式串的长度),是比较高的。

这里介绍的 KMP 算法,能够在 $O(n)$ 时间内完成任务,它是由 Donald Knuth/James H. Morris/Vaughan Pratt 发明的。当然,你也可以称之为「看毛片算法」——你高兴就好。

阅读全文 »

在软件工程课中,有一个经典的作业题:实现一个小学四则运算器。当然,它有不少变种,比如要求学生预先生成合规的四则运算题目。但不论如何变形,此类问题都绕不开 Dijkstra 提出的调度场算法。

阅读全文 »

今天有人在群里讲,大意是「我就喜欢 CJK,不喜欢 CTeX 宏集,不够通用」。我对此的评价是「啥也不懂,瞎搞胡搞」,然后摘了龚自珍的「病梅馆记」中的一段话作为评论。

梅以曲为美,直则无姿;以欹为美,正则无景;以疏为美,密则无态。

后有人惊奇,曰:「这么偏的中学古文,你居然还记得」。答曰:「大约因为吾与龚自珍同类也」。

阅读全文 »

最近在改 XGBoost 的代码。XGBoost 在代码中使用了很多来自 C++11 标准中的特性,让我比较好奇和困惑的,就有其中关于右值引用的部分。涉及到代码里,有比较明显的两类用法:

std::move
1
std::move(foo)
std::unique_ptr
1
std::vector<std::unique_ptr<T>>

前者是使用 std::move 返回 foo 的右值引用;后者则在容器 std::vector 中放入了不可复制只能移动的类的实例(智能指针 std::unique_ptr),当你尝试用常规方法将整个 std::vector 中的元素依次加入另一个 std::vector 的时候,编译器就会报错,提示 std::unique_ptr 的拷贝构造函数是被删除的。

因为好奇和困惑,所以想要把它们搞清楚,于是有了这篇文章。

阅读全文 »