Electronic Trading Challenge 酱油记

上个周末刚参加了 Jane Street 举办的 Electronic Trading Challenge Tsinghua Event。三只大三狗,大作业的汪洋大海之中。成绩是 19 支队伍的第 11。本文也很水,预警一下( ̄(工) ̄)

## 体验

简言之就是新奇、有趣。我都想开个户玩真的了。

还有便是认识到了差距,感觉自己好菜啊( ̄(工) ̄)

## 比赛概况

编写程序在虚拟市场里交易。市场上有 4 支个股、2 个基金,还有国库券。除了参赛队之外,市场里还有做市商。交易所提供每种证券的订单簿和订单成交信息。每个交易日持续 5 分钟,每天都是两手空空从头开始,每天结束后系统按照某种公允价值计算盈亏积分。比赛从上午九点持续到晚上九点,划分为一个一个 5 分钟,选手可以随时修改程序,加入或退出市场。

## 我们队的套利策略

我们首先花了点时间通读文档。叶曦在根据交易所的协议编写 API,我和江昊琛先开始研究怎么赚钱。因为暂无 API 可用,我们就用 nc 命令强行手动下单,结果一单亏了 2 块钱,这 2 块钱使我们队一连几个小时都以负的积分排名垫底……好气哦。

基金可以和对应篮子直接互相兑换,无论价格如何,只收固定的手续费。我们首先看到了这里面的套利机会。例如,X 能兑换 2 A + 3 B + 2 C。某一时刻 X 的买入价是 9,A 的卖出价是 2、B 的卖出价是 1、C 的卖出价是 3。那么我就可以花 9 元买入一个 X,兑换成 2 个 A、3 个 B、2 个 C,然后分别卖出去,得到 2 x 2 + 3 x 1 + 2 x 3 = 11 元。从左手搬到右手,9 元就变成了 11 元,只要兑换的手续费低于 2 元,我就赚了。

实际的价格并不是常数,而是数量的一个分段线性的函数。这个函数可以根据订单簿计算出来。对于买方报价,各段斜率是递减的;对于卖方报价,各段斜率是递增的。

Buys         Sells
Price Volume Price Volume
8     3      9     4 
7     2      11    3
6     2      12    4
4     4

随便编了个数字例子。对于给定的证券,买方报价总是低于卖方报价的,否则就直接成交了。X 的价格满足这个关系,ABC 的价格(A、B、C 的价格的加权和)也满足这个关系,但是 X 的价格和 ABC 的价格之间就不一定了。它们都会波动,很可能存在某些时刻,X 的价格和 ABC 的价格不匹配,这叫市场的瞬时无效性。

ABC 组合的曲线是用 A、B、C 的三条曲线按比例叠加得到的。

上图示意的情况下,我们可以买入 A、B、C,卖出 X,赚取差价。阴影部分就是机会啦。在横轴上找到一点,使买入 ABC 的总价与卖出 X 的总价之间的差额最大。如果这个差值大于手续费,我们就可以动手啦。同时还要关注反方向 X Sells 和 ABC Buys 两条曲线,以发现反方向的机会。

为完成这样的交易,需要同时盯着 4 组订单簿,随时更新 10 个总价格函数。每次操作要同时下 5 个订单。价格差转瞬即逝,这种事情显然只有程序能做。

说实在的,策略很简单,模型也很简单,但我们实在是太菜了。大概上午十一点开始写,晚上五点才把它调试好上线。

说实在的,策略很简单,模型也很简单,但我们实在是太菜了。大概上午十一点开始写,晚上五点才把它调试好上线。在此之前我们队只是简单地倒卖国库券,每个交易日的收益徘徊于两位数;后来叶曦做了几个我搞不懂的策略,提高到几百,但是波动似乎很大。等到这个套利策略上线,收益就稳定在 1000 元左右了。

## 差距

凭着这个套利策略,在比赛的最后几个小时,我们的排名上升了 3 位。后来我们了解到,前几名的队伍每个交易日的收益都在 10000 元以上。数量级上的差距,确实难以望其项背。

## 收获

打了一整天酱油,反正三顿饭都很不错。连续十个小时写代码,感觉很爽的。要说收获,也就是见了见世面吧,体验了一下 Hackathon 这种形式,对证券市场有了些感性认识。

(本文首发于知乎

学习构建之法(1):写个微信抢票

历时 5 周,历经 Alpha、Beta 两次迭代,终于把软件工程这门课的两人项目做完交付了(?)

粗略计算,与我同组的刘斌同学在这个项目上花费了百余个小时的时间。我本人则少一些,未作确切统计。从截止日期临近时另一专业课 13 / (~60) 的出勤率、去校外咖啡馆刷夜的人数、汇报展示现场主讲教师建群发红包“熬夜辛苦,中午吃好点”的情景,可见这项作业的工作量之大(?)

这个项目最主要完成的是测试环节,至于需求分析、软件设计、团队流程等则涉及较少。

根据课程要求,撰写一篇博客。择其重点,总结一下主要的收获。

  • 设计实现
    • 体会到 Web 应用开发时前后端分离的好处
    • 再次体验了给助教华榕大帝改 bug
  • 团队合作
  • 软件测试
    • 认识了 django 测试框架、浏览器自动化工具 selenium 和 PhantomJS
    • 知道了编写单元测试的基本方法
    • 了解了编写功能测试的基本方法
    • 了解了评价测试的主要指标——覆盖率
  • 性能调优,相关博文:django 性能调优手记
    • 性能测试
      • 认识了性能测试工具 JMeter
      • 了解了评价性能的主要指标——吞吐量、错误率、响应时间等
    • 部署和运维
      • 认识了众多 Linux 系统参数、uWSGI 参数、nginx 参数
      • 尝试了基于 docker 的自动化部署
    • 性能优化
      • 体会到若干因素对性能的影响

未完待续

我以为自己发现了 clang 的一个 bug……

摘要:完成体系结构课程作业时遇到 gcc 和 clang 的行为不一样。确切地说是 clang -O1 及以上会得到意外的结果。以为自己搞了个大新闻,结果发现是自己写了 ub(未定义行为,undefined behavior)。

代码如下。

#include <stdio.h>
#include <limits.h>
int test(int x, int n)
{
  int y = (1 << (n - 1)) - 1;
  int le = (x <= y);
  printf("%d, %d, %d\n", x, y, le);
  return 0;
}

int main(){
  int n = sizeof(int) * 8;
  test(INT_MIN, n);
  return 0;
}

gcc 版本:gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
输出的结果是:

$ gcc bar.c -O1 -o g && ./g
-2147483648, 2147483647, 1

clang 版本:Ubuntu clang version 3.4-1ubuntu3 (tags/RELEASE_34/final) (based on LLVM 3.4)
输出的结果是:

$ clang bar.c -O1 -o c && ./c
-2147483648, 2147483647, 0

 

好奇怪啊,明明一个正数、一个负数,怎么 clang -O1 就负数更大了呢???

是不是 clang 编译优化的 bug?

——我也以为自己搞了个大新闻。仔细研究一番便发现,这里并不能怪编译器:1 << 31 已经发生了溢出;即使得到了负值 INT_MIN,在其上再减去 1,再次发生溢出。对于有符号整数运算溢出,尽管很常见的做法是截断取模,但实际上标准并没有作出规定。因此,从这一行起,编译器做什么都是符合标准的( ̄(工) ̄)

ub 很可能直接被编译器优化掉[1]。此处就是这样。可以从汇编码看出,开启编译优化时,clang 把 le 参数直接优化掉了,大意如此:

printf("%d, %d, %d\n", x, y, le); //clang -O0
printf("%d, %d, %d\n", x, y, 0);  //clang -O1

完。

django 性能调优手记

最近在做一项课程作业,是基于 django 框架的一个抢票系统。项目的特点是逻辑比较简单、并发要求高。要求支持 1000 个用户并发访问,响应时间小于 5 秒,错误率 0。

    1. 首先我们知道,python manage.py runserver 是肯定不行的,测试表明支持并发数小于 10。
    2. 使用 uWSGI + nginx。基本配置下,支持并发数达到 120。
    3. 调大系统 net.core.somaxconn 值。
    4. 调整 uWSGI 配置参数,此时支持并发数达到 380。
        • 以 IPC socket 取代 TCP socket,节约协议栈开支:socket chmod-socket,对应修改 nginx 配置文件中 uwsgi_pass
        • socket 队列大小:listen
        • 进程数:processes,大致和 CPU 核心数匹配
        • 线程数:enable-threads threads
        • 关闭日志:disable-logging
        • Python 解释器优化级别:optimize

      至此,我们的 nginx 配置大致是

      server {
          listen 80;
          server_name wx.nullspace.cn;
          location ~ ^/(wechat|api|admin|accounts){
              include uwsgi_params;
              uwsgi_pass unix:///tmp/wechatticket.sock;
          }
          location / {
              root /home/justin/WeChatTicket-1611/static/;
          }
      }

      uWSGI 配置大致是

      [uwsgi]
      chdir=/home/justin/WeChatTicket-1611/
      module=WeChatTicket.wsgi:application
      master=True
      max-requests=65535
      socket=/tmp/wechatticket.sock
      chmod-socket=666
      optimize=2
      processes=2
      threads=2
      listen=65535
      disable-logging=True
      enable-threads=True
    5. JMeter 显示并发数更高时会出现很多错误,尽管响应时间是比较低的。查看 nginx 的错误日志发现全部是 socket() failed (24: Too many open files)。后来又出现了worker_connections are not enough while connecting to upstream,为此魔改了一批参数:
      1. nginx 配置 worker_rlimit_nofile
      2. nginx 配置 worker_connections
      3. 修改 /etc/security/limits.conf
      4. 编辑 /etc/sysctl.conf 修改 fs.file-max 值
    6.  优化数据库锁操作
      • 检查余量、减库存的操作是需要加锁的,代码片段原先是这样的:
        # 减库存
        with transaction.atomic():
            activity = Activity.objects.select_for_update().get(id=actId)
            remainTickets = activity.remain_tickets
            if remainTickets <= 0:
                return self.reply_text("没票了,你来晚啦 :(")
            activity.remain_tickets = remainTickets - 1
            activity.save()

        reply_text 是阻塞的 I/O 操作,将其挪到 transaction.atomic() 作用域外:

        # 减库存
        with transaction.atomic():
            activity = Activity.objects.select_for_update().get(id=actId)
            remainTickets = activity.remain_tickets
            if remainTickets > 0:
                activity.remain_tickets = remainTickets - 1
                activity.save()
        if remainTickets <= 0:
            return self.reply_text("没票了,你来晚啦 :(")

        由此可以减少数据库锁的持续时长。测试表明:此处仅稍稍调整了语句的顺序,便使平均响应时间下降了 20%。

      • 顺便指出,如果去掉锁,可以再下降 40% ( ̄(工) ̄)
      • 可考虑使用 django.db.models.F 表达式代替数据库存取和锁
    7. 优化数据库索引
      • 给“票”表增加了一个字段的索引,去掉了一个字段的索引
    8. 避免 SELECT *,减少数据库查询字段数
      • django.db.models.QuerySet.only 方法

 

文中的测试数据是在一台单核 CPU、 768MB 内存、运行 Ubuntu 16.04 系统的 VPS 上,利用 JMeter 取得的。

“结对编程”初体验

本学期选修了清华大学软件学院刘强老师主讲的《软件工程》课程。近期完成了该课程的一项作业——体验结对编程(Pair programming)。本文谈谈个人体验。

我们实现了该课程的作业“紫荆之声——基于微信公众平台的票务管理系统”的一个功能单元:一个事件处理器 Handler,当用户在微信公众号点击“抢啥”菜单项时,返回近期可以抢票的活动列表。这是我们在该项目开发过程中编写的第一个 Handler。至于为什么这个看似简单的小任务花了30分钟之久,大概是因为我们事先毫无准备,两台笔记本搬过来,装上录屏软件就开始了,什么都还没配置呢( ̄(工) ̄)

总的来说,我扮演了驾驶员的角色,刘斌同学扮演了导航员的角色。我的手放在键盘上实际编写代码。同伴则负责进行审查、解答我提出的各种问题、跟我讨论实现上的细节,比如我们应该用请求体的什么参数来识别这是“抢啥”事件?这个地方写得对不对?是否有库函数完成这个操作?这个异常是怎么回事?返回给用户的活动列表应该怎么过滤、怎么排序?他利用另一台笔记本电脑,有时去查阅文档、有时搜索爆栈网、有时打个断点跑起来试试看。有时充当小黄鸭的角色。

相比两人分工各写各的,我感受到的好处主要有几点:不再有冲突合并的麻烦;一个人写另一个人就同时检查了,省去了一些调试查错的时间,也省去了代码审查的时间;沟通成本降低。缺点也有,比如总的工时数似乎并不会下降,而且约时间、找地点有额外的成本。

 

浅尝现代前端开发

“Web 前端技术实训课程”感想(一)

在苹果电脑早已全线标配 NVMe 固态硬盘的当下,我看到有些课程还在讲解磁带。教师自然会有一万种理由来辩解这并不是什么“不思进取”,但作为学生还是总觉得不痛快。

在这样的背景下,Web 前端技术实训课程不可不谓激动人心。该课程由清华大学软件学院刘强老师开设,在该校所谓的夏季小学期展开,历时两周半。邀请到来自知名互联网企业的工程师登台讲解,配合独具特色、实践性极强的“大作业”,有望接触到工业界最新潮流,实在是令人期待。

从今开始在这里分享参与该课程的感想,同时也是为了应对其作业——“在个人网站中发布一些个人日志”。

更新 2016-9-26:就这一篇,并没有后续- –

本博客改名称、换域名啦!

nullspace,数学名词,见于线性代数课程中,对应中文“化零空间”、“零空间”、“核空间”等。

null 和 space 两个词同时出现,是不是很有 geek 科技范?

我的博客的新的地址,是 nullspace.cn(白菜价的 .cn 域名←_←),请大家更新收藏夹~

原域名 200404.xyz 将保持使用直到2016年2月。当然新浪云提供的二级域名 200404.sinaapp.com 会一直可用。更新 2016-9-26:已从新浪云迁出,目前放在 Vultr 提供的 VPS 服务器上。

(完)

如何进行算术表达式的求值

问题:对一个形如“(2!)^(cos(0)+(-2))”的算术表达式求值。

最近《数据结构》课程讲到堆栈的应用,碰到了这个经典的问题:数学表达式的求值。

众所周知,双目运算符有中缀式(自然形式)、前缀式(波兰表达式)、后缀式(逆波兰表达式)三种表示方法,其中后两种易于求值(只需顺序扫描一遍即可)。一种典型的想法是,先把中缀式转换为后缀式(如果利用堆栈,大致是线性时间、线性空间),然后对后缀式求值(线性时间)。

但是这种方法看起来只对二元运算符有效。如果出现了一元运算符,比如 “-1”,这里这个表示一元“取反”运算的负号,需要被转化成 “0-1”,变成二元“减法”运算的减号,方可用前缀式或后缀式求值。除了出现在运算数前面,一元运算符还可以出现在运算数后面,比如阶乘。更甚者,一元运算符可以以“函数”的形式出现,引入更多的括号,比如下式:

(2!)^(cos(0)+(-2))

实际上我们可以认为 f(x),fx,xf 是一元运算符的三种形式。

问题:对一个含有一元运算符、二元运算符、括号的自然形式的算术表达式求值。其中一元运算符的形式包括 “sin(233)”、“-233”、“233!”。

本文将给出一种处理以上问题的有效算法。这一算法在表达式的自身形式上进行迭代,近似具有平方(表达式长度 x 运算符个数)的时间复杂度。可改用栈结构避免重复扫描查找括号,可降低时间复杂度,但将需要线性的额外空间。

1 顺序扫描,查找最内层的一对括号(最靠右的“(”和相应的“)”)

2 查找括号内是否有运算符
    2.1 如果有,对括号内的部分进行求值(子问题)
    2.2 如果没有,检查括号左侧是否有函数名
        2.2.1 如果有,求值
        2.2.2 如果没有,去掉括号

3 重复以上步骤,直到找不到任何括号

其中调用了一个子问题:对不含括号的表达式求值。这时候只有 fx 和 xf 两种形式的一元运算符,且识别起来相当容易:与其他运算符相邻的运算符就是一元运算符。可以先将所有一元运算符求值,然后按正常二元运算符表达式的方法求值。

以下是该算法作用于上例的过程。为避免二义性,以 @ 表示“表示数值的负号”,与运算符“-”区分。

(2!)^(cos(0)+(-2))
(2!)^(cos(0)+(@2))
(2!)^(cos(0)+@2)
(2!)^((1)+@2)
(2!)^(1+@2)
最内层 (1+@2)
最内层 @1
(2!)^(@1)
(2!)^@1
最内层 (2!)
最内层 2
(2)^@1
2^@1
最内层 (2^@1)
最内层 0.5
0.5

以下链接是我(/*于一年前←_←*/)按照该算法写的 C 语言程序,它可以处理前置的一元运算符“-”(取负)、后置的一元运算符“!”(阶乘),可以处理十二种函数 {“cos”,”sin”,”tg”,”ctg”,”abs”,”sign”,”sqrt”,”ln”,”sinh”,”cosh”,”tanh”,”coth”},可以处理五种二元运算符 {‘+’, ‘-‘, ‘*’, ‘/’, ‘^’},可以正确处理括号,同时还实现了一部分大数计算。

https://github.com/lizy14/C-assignments/blob/master/expressionCALC.cpp

(完)

清华校园网免流量上网方法综述

“哪些地方的入校流量不计费?”

本文的分类依据是——“哪些地方的入校流量不计费?”

第一类方法:利用 IPv6

目前校园网 IPv6 出入流量是不计费的。这可能是因为基于对 IP 地址进行认证的计费系统尚未升级,也可能是出于政策上对 IPv6 的推广。
这一类方法都要求你有 IPv6 的接入。反正在我宿舍里是可以的,而到了某些教学楼就不行了。

1. 访问 IPv6 站点或 BT 服务

这是唯一不需要在校外做任何部署的方法,缺点是能访问的站点范围十分有限。这也是目前最广为人知的方法。比如大家都知道从北邮人、六度空间下东西不要流量,可以修改 hosts 文件上 YouTube 等。

2. 利用 IPv6 隧道的代理

这也是用的比较多的方法。你需要在校外有代理服务器,然后通过 IPv6 和代理服务器通信。比如我协就有 Shadowsocks 服务开放给大家使用,部署在校外支持 IPv6 的 VPS 上。想自己搞一个的话可移步参考资料[1]。

第二类方法:利用可从校外访问的校内站点

为方便师生,有一些校内常用站点是可以从校外访问的,包括网络学堂、图书馆、清华邮箱等。我相信这些服务器的 IP 是在计费系统的白名单里的。

1. 清华邮箱

这种方法的实时性较差,很难用于在线浏览,可能只能用来下载文件了。当你需要下载一个大文件的时候,第一步,用一个校外的服务器下载指定的文件。第二步,把它作为附件发到自己清华邮箱。第三步,在校内登录邮箱下载这个文件。

由于邮件附件大小有限制,我们需要把文件分段。这个过程是可以自动化的。曾有同学用此法实现了一个 demo,请围观参考资料[2]。

当然,直接支持通过邮箱下载文件的网站也是有的。

2. 网络学堂

网络学堂有个讨论区,讨论区是可以上传自己的文件的。其实和利用清华邮箱差不多,把第二步改成“把它作为附件上传到网络学堂某个课程的讨论区上”就是了。我最近在做这样一个 demo,尚很粗糙,但基本的功能已经可以了。

第三类方法:SSL VPN 系统

SSL VPN 系统允许你在校外访问校内任意 IP,这也是一个流量不计费的地方。可以利用它做代理隧道。

前不久试了一下,在宿舍里开个 FTP 服务器,然后用家里的电脑连上 SSL VPN 往这个 FTP 上传文件。轻松加愉快。

第四类方法:DNS 的 UDP 53 端口

参考资料[3]是北邮一同学的 demo,还放到乌云上了←_← 据说我校 UDP 53 端口也是开放的,可以 DNS tunnel 绕开计费。

参考资料

[1]如何用20G过完一个月. 岳大禹.
[2][脑洞]关于从校内免流量下载文件的实验. 汪芃.
[3][DNS tunnel实例]北京某大学网关计费系统可被绕过. lxj616.

Visual Studio 配置 OGDF 图布局算法库

项目主页:http://www.ogdf.net/

开源 (GNU/GPL),有不错的示例、文档(都是英文的←_←)

主要步骤:下载源码, 编译安装, 配置工程, have fun!

Step1>>下载源码

  • http://www.ogdf.net/doku.php/tech:download
  • Current Release: v. 2015.05 (Baobab) [5.4 MB]

Step2>>编译安装

  • 执行 makeVCXProj.py 脚本:生成 VS 工程 ogdf.vcxproj, coin.vcxproj 和解决方案 ogdf.sln。不需要 cmake,但是……好像需要个 python 解释器
  • 用 VS 打开 ogdf.sln,“生成解决方案”。
  • 你会得到一些 lib、obj 文件。我的在 OGDF\Win32\Debug 目录下

Step3>>配置工程

  • 添加包含目录、库目录
    • 在解决方案管理器中右击你的工程,属性。配置属性>VC++目录:
    • 在“包含目录”中添加 OGDF\include
    • 在“库目录”中添加 ogdf.lib、coin.lib这两个文件所在的目录(上一小步中的 OGDF\Win32\Debug)
    • 也可以将以上路径添加到相应环境变量中
  • 为链接器附加库 ogdf.lib、coin.lib
    • 还在工程属性对话框中,配置属性 > 链接器 > 输入,在“附加依赖项”中添加“ogdf.lib;coin.lib;”。
    • 也可写在源代码文件里,
      #pragma comment(lib,"C:/blablabla/ogdf.lib")
      #pragma comment(lib,"C:/blablabla/coin.lib")

Step4>>hello world

#include 
using namespace ogdf;

int main(){
Graph G;
node a = G.newNode(); 
node b = G.newNode(); 
node c = G.newNode();
G.newEdge(a, b); 
G.newEdge(b, c); 

GraphAttributes GA(G);

FMMMLayout fmmm; 
fmmm.call(GA);

cout << GA.x(a) << ", " << GA.y(a) << "; \n";
cout << GA.x(b) << ", " << GA.y(b) << "; \n";
cout << GA.x(c) << ", " << GA.y(c) << "; \n";
return 0;
}
//代码很丑陋,这只是个hello world,莫吐槽

一次运行的结果:

25, 25;
59, 60;
93, 93;
请按任意键继续. . .

(完)