在 Swift 中使用 cmph

CMPH 的全稱是 ç最小完美哈希庫 ,是一個很著名的用 C 寫成的最小完美哈希庫,什麼是完美哈希?

完美哈希

這裡我們不講原理,你只需要知道傳統的哈希有衝突,我們需要靠各種算法來處理衝突就可以了,對於哈希,總是需要一個表,這個表裡預留了很多位置,然後計算出來的值就是這些位置的坐標,你可以把對應的數據放到坐標裡。

但這時候有一個問題,如果这个预先的表不够大或者说你的算法不够好就会发生所谓的聚集某一片区域值总是冲突而某一片区域的值则是空的,所以,你的表长度总是要大于 key 的数量来容纳这些空余

但如果你的算法足够牛逼那么你就能做到让表的长度n最少能够等于key的数量!

当这种情况达成那么我们就称这个哈希函数为最小完美哈希函数

CMPH

那么这种东西真的存在吗?当然CMPH 就是一个当然想要使用 CMPH 还是有一点前提的比如你的 key 得是不重复的key 的数量得是固定的静态的

比如说我的隐马尔可夫模型中的转移矩阵就满足这么一个需求

不過,cmph 是用 C 语言实现的我们需要把 C 桥接到 Swift 中

桥接

和桥接 oc 差不多你把下载好的cmph目录中的 src 目录里的源文件都拖到 Swift 项目中即可(记得选择拷贝而不是引用)如果是第一次拖入其他语言的内容Xcode 会自动提示你创建桥接文件然后你的项目中会有一个叫做 XXX-Bridging-.H 的文件,其中的xxx就是你的项目名字

在里边写 #include "cmph.h" 就好了,这样你就把 cmph 的函数暴露给了 Swift

整理项目

直接导入的 cmph 源代码不能直接在 Swift 项目里使用如果你空项目编译会遇到“多个 main 函数”的错误去 cmph 源文件中,刪除 主要.C bm_numbers.C bm_bumbers.H 现在再编译试试如果还报错那么就删除那个包含 main 函数的源码即可我们只用函数

編譯

cmph 其实是库和工具套装——这也是为什么源码里包含了 main 函数我们进入下载的 cmph 目录里执行如下命令进行编译

这下你就可以在终端执行命令 CMPH 了:

创建哈希表

使用工具创建哈希表而不是代码因为它需要key是静态的所以要事先准备key的文本列表要求是纯文本文档一行一个 key 即可最大千万也妥妥的

编码是utf8

根据命令提示我们直接在目录里执行 CMPH -g keys.文本 即可,如果你想要指定算法(具体的算法种类和特性可以见官网)比如我的数据库肯定是用在外存的就用专门对外存做优化的 brz 算法,那么命令就变成了这样 CMPH -g -一個 brz keys.文本

执行完毕后会在当前目录下生成 keys.文本.mph ,為了方便,我把它改为 keys.mph

驗證

要看到对应的结果我们可以再来一个文本文件格式与 key 的列表的格式相同里边写入你想要查询的 key比如我命名为 keysq.文本这时候我们用 debug 模式输出查询结果

获得结果

現在,我们可以用同样的方法把所有的 key 查一遍就能得到每一个 key 对应的坐标了!

获得了结果我们就可以根据位置来生成一个对应的文件我用自己的编码方式编译了一个之际的二进制数据库但位置根据 CMPH 的坐标来对应这样数据和位置就可以做到一一对应了查询的速度是o(1).

在 Swift 中查询

現在,我们可以把生成的 mph 文件导入 Swift 项目备用了——当然还有对应次序的数据库文件以便查找

在 Swift 中使用 C 的函数还是挺有难度的

首先你要有一个类型为不可表达指针类型的变量来存哈希表对象

在初始化器里我们来用 c 函数加载哈希表

这样哈希表就加载成功了

假定我们要查的值是一个 UInt32的 的数字编码那么我们需要先把它转为 cmph 函数所接受的 char* 指標,那么可以借助 的NSString 来实现

雖然 Swift 开发者文档中说 Swift 的 String 自动映射了 NSString 的方法,但顯然,它并没有

这样id变量就是一个Int类型的坐标了返回值的类型 Swift 编译器自动帮你映射了

總結

cmph 的原理很复杂但这并不影响我们使用它。值得一提的是,它使用 LGPL 授权也就是说你可以自由地使用它

使用 Swift 可以完美地桥接 C 语言但由于 Swift 本身并不鼓励开发者这么做导致一堆“unsafe”看着有种惊心动魄的感觉

 

anyShare分享到:

發表評論

您的電子郵件地址不會被公開. 必填字段標 *