Introduction

运行效率在Python中一直倍受诟病，但是作为[胶水语言]，除了具有自身逻辑快速实现能力，还能够很容易将复杂运算抽象到其他平台上去，比如C .

这是由一个 [Probabilistic Counting]问题。在大数据量的情况下，又转化为基数估计问题(见[基数估计算法概览])。
业务层面是需要解决某个站点访问用户总数，这里用Python表示

counting = defaultdict(int)
for site_id, user_id in logs:
    counting[site_id] += 1

pprint(len(counting)) #Total User
pprint(len(counting)) #Users per site

大量的数据情况下，counting自身容量会面临严重考验，假设每项数据在字典中的大小均等(Key: 8 * 38 byte per String , Value: 28 byte per Long)，那么在百万项时，关统计就需要 332 * 1000000 / 1024 /1024 bytes = 316 MB，问题是去重免不了维护整个统计记录，捉襟见肘的内存很难维护这么大一个列表，这是难免拆分日志，合并统计，但是其中存储结构等等又是何其繁琐。

在大量数据的情况下，准确度未必会要求地很严格，所以基数估计应运而生。
这里直接给出几个已有的实现，具体原理请翻阅[Reference]。

• [Stream-lib] Java版本的基数估计实现，提供了Couting,TopN方法的实现
• [ccard-lib] 参照[Stream-lib]给出的C实现，由淘宝的chaoslawful同学维护，该同学还是另外一个开源项目[nginx-lua]的作者

Python C extension

我的目标平台是Python，对于Java版本的类库就不做考虑了，所以直接拿来[ccard-lib]，编译获得动态链接库后，开始编写Python拓展。

关于Python拓展，isnowfy同学有一个简易的介绍。
这里我就地使用[ctypes]实现，这里有一篇很好的教程([ctypes tutorial])。

声明

为了建立Python接口和C接口的联系，我们需要再次定义C中*.h文件里的声明。

from ctypes import *

class Ctx(Structure):
    _fields_ = [
        ("err", c_int),
        ("k", c_int8),
        ("m", c_int32),
        ("Ca", c_double),
        ("Rsum", c_int32),
        ("b_e", c_int32),
        ("hf", c_int8),
        ("M", c_int8*1),
    ]

f = 'libccard-lib.0.1.dylib'
cdll.LoadLibrary(f)
api = CDLL(f)
api.adp_cnt_init.argtypes = [c_void_p, c_uint32, c_uint8]
api.adp_cnt_init.restype = Ctx

我定义这些后，运行api.adp_cnt_init(None, 16, 1)，获得了一个Ctx对象，但是在余下的接口声明，以及人肉切换C类型和Python类型的工作中，让我抓狂，其中调试时的段错误，更是添油加醋。

作为懒惰的本能，这种机械工作应该都会有自动mapping的工具，在PYPI中找到了今天的主角[ctypesgen]。

ctypesgen

安装简单，直接通过Pip

pip-2.7 install ctypesgen

然后通过它生成ctypes映射文件

$ ctypesgen.py -a -l libccard-lib.0.1.dylib -i include/*.h -o ccard_head.py

接下来就可以通过和ccard C库一样名称的API使用ccard-lib。

import random
from ccard_head import *
ctx = adp_cnt_init(None, 16, CCARD_HASH_MURMUR)
for i in xrange(500000):
    ci = c_int(i)
    rs = adp_cnt_offer(ctx, byref(ci), sizeof(ci))

esti = adp_cnt_card(ctx)
print esti # Target Count

但是作为一个类库，这样的API显然是不达标的，所以需要加一层封装，使之变得友好。

Conclusion

ctypes的优势是作为内置库，无需安装第三方拓展，但这里有个前提，我们是针对需要编译后的链接库进行封装，所以这个“无需安装第三方拓展”也仅仅是针对Python包装而言，如果真的应用在项目里，必然涉及编译。

另外对比Python C Extension，ctypes的包装开销也不得不考虑，在ctype performance benchmark中给出一个评测结果，ctypes拓展的时间开销是Python C Exetension的2~3倍。
这在一些效率敏感的地方是致命的，不过对于快速实现，或者较少的交互调用（ctypes的主要开销，来自C对象和Python对象的转换），ctypes 和ctypesgen不失为一种便捷选择。

如果你想快速实现，Python已经提供了原生实现的基数估计包[hyperloglog(http://pypi.python.org/pypi/hyperloglog/0.0.2)，可以直接通过PIP进行安装。
经本机测试，[hyperloglog]的时间开销比ctypes包装的[ccard-lib]多2~3倍。

Reference

• 胶水语言
• 基数估计算法概览
• Stream-lib
• ccard-lib
• ctypes
• ctypes tutorial
• ctypesgen
• Probabilistic Data Structures for Web Analytics and Data Mining