文章归档

数据结构接口对象化

c 语言适合平台及系统等一些的大型核心构架的开发,面向过程,不支持面向对象语义,

不过我始终认为,面向对象是一种思想,而不是指某种既定的技术,所以,OO 与语言没有关系,随便一种语言,一样可以写出面向对象的代码,OO 的思想绝对不只是继承,多态等那么简单,对于某些语言如 c++ 或者 Java,支持面向对象语义因而适合表达这种思想而已,况且 Java本身设计的出现就是为了解决面向语义的问题

做项目的时候,很头疼的问题就是关于接口命名的设计,包括内部接口和外部接口,小型的项目倒也罢了,如果构架过于庞大,就容易出现接口混乱的问 题,c 风格的代码并不像 c++ 或者 java 那样简单容易白,毕竟用 c 的都是写模块的多,功能越是复杂,函数的命名就越容易出现杂乱无章的情况,很难看出你在写什么,支持面向语义的编程语言,最大的优点就是,容易写出层次分 明,结构清晰的代码,但是像 c 这样的语言可不容易,所以,好的函数命名规范对项目来说很重要

回归正题,先说说什么是对象化技术,所谓数据结构对象化,就是一组结构有各自适合的管理接口,本质上是一样的,只是写法不同而已,以红黑树为例,看看内核是怎么实现的(部分接口):

C++代码

  1. /* Macros that define a red-black tree */
  2. #define RB_HEAD(name, type)
  3. struct name {
  4. struct type *rbh_root; /* root of the tree */
  5. }
  6. #define RB_INITIALIZER(root)
  7. { NULL }
  8. #define RB_INIT(root) do {
  9. (root)->rbh_root = NULL;
  10. } while (/*CONSTCOND*/ 0)
  11. #define RB_BLACK 0
  12. #define RB_RED 1
  13. #define RB_ENTRY(type)
  14. struct {
  15. struct type *rbe_left; /* left element */
  16. struct type *rbe_right; /* right element */
  17. struct type

    »» 继续阅读全文

文本压缩的思考

最近断断续续花了很多时间在研究文本压缩领域,没有说是数据而是文本,是因为文本在特定的场合和环境可以有更大的改进和性能提升,比如基于 ASCII码和Unicode的就可以设计得截然不同,仅用一种方案来对不同的场景产生应用,是要付出一定的代价的比如性能。而且,不同的语言又会有不一 样的表现形式,这对垂直式的压缩技术来说是一种新的挑战。

因为业务需要,我希望可以实现一种更快的压缩算法,尤其是在解码方面要有不俗的速度表现。

我尝试过对哈夫曼编码进行一些细节上的改进,但是效果不太明显,哈夫曼编码的特点就是即使极限情况下也是能够保证绝对的压缩,当然能压缩多少倒是不 一定。编码过程比较块,难点就是对于这种比特流的存储方式,解码时必须单个比特地亦步进行,耗时特别长,是我不能接受的。研究算法远不是纸上谈兵那么简 单,不是随便在纸上画一棵二叉树就能解决问题领悟到信息论的奥秘。离开实际的应用研究不存在太大的意义,所以我们要清楚面临的需求以及对算法作出何种改进

 

lz77算法比传统的范式哈夫曼可能花费的时间更长一些,毕竟哈夫曼编码只需执行一次遍历就可以统计出编码模型而lz77则需要花费更多的时间在建 立字典和回溯检索上面。不过,lz77最大的特色就是解码特别的快,与其他编码相比解码速度完全不在一个数量级上面。lz77及其变种大部分的实现都是等 长编码,是建立在字节级别上的,不是比特流,本质上速度就有很大的优势。更重要的是,lz77每解码一个字符只需向前查看一次滑动缓冲区,总的时间复杂度 是Θ(n),线性

Gzip就是lz77很成功的一个例子,不过,网上说的那点也太简单了简直不值一谈,Gzip精妙的地方在于对算法做了很多有利的改进,我猜的,因为不管我怎么设计,以及优化,总是赶不上gzip的速度,事实证明,gzip真的很优秀

在滑动窗口也就是字典的设计上,我没有使用哈稀表而是用了一个二维数组来对任意字符进行索引,一方面我懒得搞那么复杂,而且二维数组似乎更加直观因为我主要基于单字。数组保存了对在滑动窗口里出现的所有字符的索引,而且采用了插入排序来改善查询的性能

到目前为止,整个实现最值得探讨的问题,在于滑动窗口的大小以及设计能够匹配的最大的长度,是关乎压缩效果最重要的一方面

从语言的角度来看,中文又不同于英文,英文里最常见的字符如 the,of,to,and 等在极短的滑动窗口里也可以有很好的匹配效果,但是中文就不一样了,还要取决于不同字符集的实现,滑动窗口要更大一些。这里就回出现一个性能项瓶的问题, 窗口规模与匹配的最大长度是成线性比例关系的,如果滑动窗口设计的太大,即使能匹配到好的长度,程序也要花费太多的时间在Match上面,而且大量的数据 可以表明,不是所有的字符串都能够找到最优匹配的,很多情况是,在小的窗口模式下,比如31或者63,能匹配成功的平均长度是1到2位左右,也就是说,2 个比特就足以完成保存匹配长度的工作,默认我设置了3bit,是因为我发现3bit的长度和31的窗口更有压缩上的优势

最终的测试结果是,相比较gzip的实现,压缩大约80M的文本语料库,平均时间为 1.413s,解压为 0.248s,压缩率是48.5%,而gzip的测试结果是,平均时间为 0.998s,解压为 0.131s,压缩率达到25%

我一直很好奇gzip是怎么做到的,如果我用多线程的话效果是不是会好一点。

目前所知,硬件层来说使用磁盘阵列可以提高io的效率,对压缩也是有好处的。

块排序压缩的数学原理

也叫 BWT 转换,严格来说不属于一个压缩算法,是压缩领域的辅助技术,BWT 的目的仅仅是将信息转换得更加适合压缩而已。BWT 巧妙的地方在于,只要精心设计,除了增加少额的计算量外,没有任何其他的开销。因为他的输出仅仅是将原有字符的排列顺序作了特定的安排

为了描述方便,举个简单点的例子,比如,即将处理的序列是 S = abraca ,S 的长度 N = 6,将 S 向右旋转一位,S 的末尾移动到 S 的首部,形成一个新的序列 S’ ,再将 S’ 向右移动一位再次产生新的序列 S”,重复这个步骤,直到得到一个 N*N 的矩阵 M,对 M 按字典排序,得到 M’ ,取矩阵 M’ 的最后一列作为输出,如下:

注意上面红色的 # 号,是一个辅助转换的结束符号,目的是为了标记原序列 S 属于 M’ 中的第几行,这个很重要,如果不使用结束标记符,就必须另外维护一个索引值,排序结果也会不一样,但是最终还原的字符序列是相同的。

逆转的过程更有意思,也非常简单,我们知道输出的序列 L=#rcaaba,L是表示矩阵 M’ 的最后一个序列,同理,F 是第一个,逆转的过程是从 L 恢复到整个 M’ 的过程,#号所在的 Row 就是原字符序列 S,因为 M’ 经过字典排序,自然 F 也是有序的

定理:对于包含 N 个字符的任意序列 S,按照 BWT 规则产生矩阵 M,对 M’ 进行字典排序得到 M’,假设 F 是 M’ 的第一列字符,L 是 M’ 的最后一列字符,若 F 是有序的,则 L 是唯一的。

从转换的过程我们知道,对于矩阵 M’ ,每行,每列所包含的元素都是相同的,也就是说,不考虑字典序,F 与 L 中的所有字符都存在一一对应的关系 T,在这里 L=#rcaaba ,所以 F=aaabcr#,则 T={6,5,4,0,1,3,2}

T 的计算过程有个需要注意的地方,L 与 F 中不是每个字符都是唯一的,也许有 N 个字符 value 相同,但是其实 index 不一样,L

»» 继续阅读全文

格式化字符串

这是在 mozilla open source 代码里发现的一个问题,目前还不确信是不是个BUG

c99引入了uintptr_t,uintmax_t 这样的标准数据类型,我们知道 printf() 函数对于常见的数据类型都有一个对应的 length modifier 用于格式化输出,int 的是 d,ptrdiff_t 的是 t,但是对于非标准的 pid_t,uintmax_t 等就没有对应的 length modifier 了。在c89的世界里,解决这种问题的常规化方案是强制类型转换到尽可能大的整数类型,比如这个 pid_t,POSIX 只要求它是一个 signed integer type,所以转化成 long 就OK了:

C++代码

  1. pid_t pid;
  2. printf("%ldn", (long )pid);

不过,c99新引了另一种方式,就是使用宏来替代 length modifier,例如 uint32_t,uintmax_t 可以使用 PRIu32 和 PRIuMAX,这些宏可以在 <inttypes.h> 中看到其定义(在 glibc 源代码中对应 sysdeps/generic/inttypes.h)。有兴趣的可以直接去看一下源代码,其实就是对已有的 format conversion 进行的宏封装。显然,第二种方式更优雅,但最近发现了一种更加优秀的方式,虽然看起来绕了一些弯路

C++代码

  1. /* Make sure BUFSIZE is large enough. */
  2. #define UMAX2S_BUFSIZE 21
  3. static char *
  4. umax2s(uintmax_t x, char *s)
  5. {
  6. unsigned i;
  7. /* LINTED */
  8. assert(sizeof(uintmax_t) <= 8);
  9. i = UMAX2S_BUFSIZE - 1;
  10. s[i] =

    »» 继续阅读全文

深入浅出c指针

指 针(pointer)是对“数据对象或函数”的一种引用,它记录了一个“对象或函数”的“内存地址和类型”。通俗地说,指针是一个变量,为了区分普通的变 量(普通的变量内存空间存储的是数值,而指针存储的却是计算机内存空间的某个地址),网络上很多资料对这个概念的叫法不一,有时叫指针,有时叫指针变量, 实质上都是同一个东西,指针本身就是一个变量,指针变量从语法的角度上看算不算重复累赘?

指针有很多用处,灵活性极强,比如,在C里,如果需要处理大量的数据的话,使用指向数据的指针比直接处理数据本身更经济和高效,又比如,你不需要移动内存中的数据就能对大量的记录进行排序,此外,利用指针,还能实现各种甚至非常复杂动态数据结构等等

声明指针

通常来说,指针的指向一般有几种:非数组对象,数组对象,函数,我们后面会更进一步地讨论“指向数组和函数”的指针,现在首先来看看,如何声明一个“指向非数组对象”的指针,语法描述如下:

C++代码

  1. type * [类型的限定符] 名称 [=初始值]

在 声明中,type * 不同于 type,type 表示需要声明的是一个普通变量,而 type * 声明的是一个指针,该指针指向 type类型的对象 ;[]表示参数具有可选性,比如 [=初始值] 表示在声明对象的同时初始值是可有可无的;类型的限定符,一般有const,volatile,restrict 等,关于指针类型的限定符,可以自行参考,这里不做详细描述;名称被声明为一个指针对象,其数据类型为 type * ;

举个例子,声明一个指针p和变量k: int *p; 在上面这个声明里,我们可以得出很多有用的信息:

  1. p是指针,而不是 *p
  2. int * 是指针的类型,而 int 是指针所指向的类型,int * 的意思是说,我所指向的对象的数据类型必须为 int (当类型不一样时,某些编译器可能会进行隐式转换)
  3. 指针p 是一个变量,在32位机里,有4字节长的内存空间

在讲解指针的之前,我们先来解释一下有关指针的几个重要而且容易混乱的概念:

  1. 指 针:指针是一种非常特殊的变量,特殊的地方在于,一方面指针的内存空间并非用来保存有效数据,而是存储着另外一个对象或者函数的内存地址;另外一方面,不 管指针所指向的对象类型是什么,指针作为变量,自身的内存空间大小是一样的,换句话说,char * 型和 int *型的指针所占用的空间大小相同,在32位的计算机上,通常是4个字节长,刚好32位
  2. 指针的类型:既然指针也是变量,自然有自己的数据 类型,不同的是,普通变量的类型描述是 type ,而指针的类型描述是 type * ,指针的类型只有一个作用,它给计算机指出了自己所指向的必须是什么类型的对象,事实上,如果你强行将int *类型的指针指向一个 char 类型的对象,那么编译器会发生隐式类型转换
  3. 指针所指向的类型:如果这个指针是指向对象的,那么指针所指向的类型就是该对象的类型;如果这个指针是指向一个函数的,那么这个指针所指向的类型就是该函数的返回值类型
  4. * :要区别 * 的两种用法,在表达式里,* 是间接运算符,比如,对于指针 p ,那么*p的运算结果就是指针 p 所指向的对象的值(计算机是这样计算的,遇到 *p 指令时,p是指针,然后读取变量 p 的值,把这个值作为一个内存地址,寻址到这个值所在的内存区域,再读取出这个区域所存储的数据 β,那么 β 就是指针 p 所指向的对象的值);而在指针声明里,* 并不是运算符,而是声明符的一部分,它给计算机指出:我要声明的是指针而不是普通变量
  5. & :取址运算符,意思就是说,可以取得一个对象的内存地址,但是也有值得注意的地方,比如:假定变量 k 的数据类型是 char ,那么 &k 的结果产生一个 char

    »» 继续阅读全文

第 4 页,共 4 页1234