对 ANS 算法的简单介绍

ANS 算法来自于 Jagiellonian University 的 Jarek Duda 在 2014 年发表的一篇论文:Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding。
从标题来看,ANS 算法是一个既有 AC 算法的压缩率又有 Huffman 算法的压缩速度的无损压缩算法。我最近一直在研究怎么优化用户在移动端加载 3D 模型的体验。如果 ANS 算法所言非虚,那么我就可以通过不多的 CPU 资源(解压时间)来换大量的流量资源(下载时间),从而降低用户在手机端加载模型的时间。
事实证明 ANS 算法确实很厉害,在权衡流量和 CPU 资源后,我们使用 ANS 把模型体积压缩到了上一代模型格式的 25%。20 万面的模型体积从 4 M(gzip后) 降低到了 1 M,在高通 610 CPU 的手机上,用微信浏览器解压大概需要 1.5~2 秒( 660 为 1秒)。也就是用 6 秒 的下载时间(根据我们的统计用户手机普遍下载速度为 500k/s) 换取了 2 秒的解压时间。而这只是非常低配的 610 处理器上面的表现。而且 CPU 性能的稳定性比网络性能的稳定性高得多。
在体验到 ANS 的巨大威力后,我实在按捺不住自己的好奇心,想去探究一下它的基本原理。

Read More

为什么要有那么多种 3D 格式?

STL、PLY、AMF、3MF、OBJ、FBX、DAE、VRML、X3D、IEGS、STEP、JT…… 目前已发布的 3D 格式文件数量,往少了说至少有二三十种。
如果我们打算写一个能同时处理这许多种 3D 格式的程序,要怎么做?
办法有很多种,但是直接扎到各种文件的文档(Specification)里面去抓取细节肯定是不对的。埋头猛干写出来的程序,往往由于缺少宏观取舍而疲于兼容各种特性,并时常处于面对未知情况的被动状态。再考虑到产品需求变更的情况,结局总是不稳定的程序表现、层出不穷的意外、举步维艰的项目进度以及经常加班、随时 on call 的泥淖。
这种焦头烂的忙碌是没有尽头的,或许直到有一天我们终于受不了了,问出了那个早就该问的问题:为什么要有这么多种不同的 3D 格式?
这是一个不可回避的问题,尽早回答它可以帮助我们对这几十种 3D 文件格式的特性和来龙去脉有一个整体把握,以“上帝视角”来设计我们的程序,夺回主动权。
通过对十多种最流行的 3D 格式做了一些调查,我发现大量规范和特性各异的 3D 格式共存的原因可以归纳于三点:

  1. 不同的应用领域孵化了少数简单但是理念各异的初始 3D 格式
  2. 不断产生的新需求导致了基于几种初始格式的衍变格式
  3. 组织之间的博弈造成解决同种需求的多种“竞争”格式共存

Read More

C 拓展 Python 实战(四)—— 类的高级属性

在之前的示例中我们使用了大量的 Py_INCREFPy_DECREF 来管理 Python Object 的引用计数。 Emptyvalue_setter 里也使用了一种非常啰嗦的语法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static int record_object_set_value(record_object *self, PyObject *value, void *closure) {
PyObject *tmp;
if (value == NULL) {
PyErr_SetString(PyExc_TypeError, "Cannot delete value");
return -1;
}

// 使用了一个非常啰嗦的临时变量
tmp = self->value;
Py_INCREF(value);
self->value = value;
Py_DECREF(tmp);

return 0;
}

这一切都是为了内存管理。
本章我们将回顾 Python 的垃圾回收机制,包括引用计数、循环检测和弱引用这些概念;
在这个基础上,我们再来讨论在设计我们的类的时候要如何做才能避免内存泄漏;
接着,我们给类添加继承和被继承的功能,并展示如何复写特定的属性和函数;
最后,我们给类添加那些锦上添花的高级功能,比如静态属性、静态方法、类方法,以及一些 __magic_function__

Read More

C 拓展 Python 实战(三)—— 类的基本属性

我们将用两章探索如何实现内置的 Python 类,并尝试去了解一些 Python 编程语言的底层实现。
和之前一样,我们先从一个简单的例子开始,再逐步添加更多的特性。
我们要实现的第一个类为 Empty,就像它的名字一样,这个类没有任何 membermethod。在实现这个类的过程中我们将学习到创建一个类的基本流程。
我们要实现的第二个类为 Record, 它有两个成员属性 name(公开,string) 和 __value(私有,任意值), 以及 printset_value 两个成员方法,并且有一个 value property
由于 Recordvalue 可以设置为任意值(包括自己),我们就得再深入考虑一下引用计数、deallocweak refrence 这些涉及到内存管理的问题。
接着我们给 Record 添加类方法(class method) get_count、静态方法(static method) get_purpose 以及 __repr__, __str____eq__
最后,我们创建一个 StringRecord 类,它是 Record 的子类,但是它的 value 只能是 str 类型的数据。

本章我们先掌握类的基本属性。

Read More

红黑树

一、红黑树是什么

红黑树是允许节点里包含最多两个 Node 的二叉树。

二、红黑树要解决什么问题

普通二叉树最大的问题在于,插入有序的序列会使二叉树会成为 N 的深度。
红黑树允许每个节点上最多挂两个 Node, 每当第三个 Node 插入的时候, 把中间值的 Node 往上冒泡。
如果在 root 上有三个 Node, 把中间的 Node 上冒做为新的 root。
由此可见,红黑树的深度是通过 root 往上冒增加的, 从而保证了每条路径到 root 的深度一致为 lg N (黑 Node 数量一致)。

Read More

Python 的赋值和作用域

一、Python 中的赋值

1.1 Python 中万物皆对象

1
print(type(1))  # <class 'int'>

1.2 Python 中赋值的意义
2.1 如果 = 号右边是对象, 则让 = 号左边的变量指向该对象, 成为对该对象的一个 引用
2.2 如果 = 号右边是变量, 则让 = 号左边的变量指向右边变量所指的对象, 成为那个对象的 引用
2.3 通过其它表达式而不是等号进行赋值的操作, 意义与上面相同

Read More

Tornado 实现 decorator 路由

我也实现了一个 Flask decorator 风格的 Tornado 路由,实现的方式极大地参考了 Flask 的过程(add_url_rule 和 Blueprint)。
Tornado 在新建 Application 的时候, 需要传入一个 handlers 参数, 原本这个 handlers 需要自己手动构建: 收集各个 RequestHandler,给他们分配路径,组成一个 handlers tuple。 这样维护起来非常麻烦。
我实现的功能是:

  1. 通过 decorator 给每个 RequestHander 即时分配 url pattern;
  2. 支持根据 API 版本和 Resource 类型自动给 url pattern 添加前缀;
  3. 可以通过 RequestHander 的类名反向查出 url。
    功能一点都不复杂, 实现起来也简单, 不到 100 行代码。下面是我的实现过程。

Read More