step by step

 

散列3

  散列这是最后一章了,快毕业了,这几天赶快把论文写完,到回家还不到两个月,答应张老师再去实验室把做的东西总结一下,其实打算在实验室再呆两个月,腊月底再回,想写的东西嘛,我想研究一下opencv的内存管理机制,结合我买的那本Applied C++,顺便推销一下这本书,这本书很薄,两百多页,介绍如何应用c++来解决开发商业软件时所固有的问题,最难能可贵的是,从头至尾提供了一个图像处理框架,对于想在数字图像处理,机器视觉方向深入探究(不是具体算法,而是整个软件架构)有挺大的启发意义的(虽然网上评价不是太好,可能比较牛的人看不上吧,也有可能这本书比较偏重于数字图像领域),还想学的东西呢,年前和年后几个月的时间Bjarne Stroustrup的那本c++,Mark Allen Weiss的那本数据结构,Jon Kleinberg 的那本算法设计,后两本书是俺在图像室的图书角找到的,非常的不错哦,可惜毕业前就要还,正好督促我赶紧看,在联合书城看到Richard Johnsonbaugh的Discrete Mathematics,竟然是第七版了,只能怪我资质太差看不懂knuth的那三本圣经,只好咬着牙买下来先琢磨琢磨了算是打基础了,公司有项目做嵌入式平台上的编译器,要是有时间的话看看嵌入式操作系统和编译原理吧,很想写个编译器,这么多好书要看,有时候真不想回家过年了,嘿嘿,说着玩的,到时候家里肯定杀猪了,不回去真是太可惜了。

1.再散列
   其实就是前两篇中有提到的rehash了,对于使用平方探测的开放定制散列法,如果表的元素填得太满,那么操作的运行时间将开始消耗过长,且插入操作可能失败。这可能发生在有太多删除和插入混合的场合。此时,一个解决方法是建立另外一个大约两倍大的表(而且使用一个相关的新散列函数),扫描整个原始散列表,计算每个(未删除的)元素的新散列值并将其插入到新表中。整个操作成为再散列(rehashing)。这显然是一种非常昂贵的操作;其运行时间为O(N),因为有N个元素要再散列而且表的大小约为2N,不过,因为不是经常发生,所以实际效果并没有这么差。特别是,在最后的再散列之前已经存在N/2次插入,因此添加到每个插入上的花费基本是一个常数开销。如果这种数据结构是程序的一部分,那么其影响是不明显的。另一方面,如果再散列作为交互系统一部分运行,那么其插入引起再散列的用户将会感到速度减慢。
    再散列可以用平方预测以多种方法实现。一种做法是只要表满一半就再散列。另一种极端的方法是只有当插入失败时才再散列。第三种方法即途中(middle-of-the-road)策略:当表到达某一个装填因子时进行再散列。由于随着装填因子的增加,表的性能的确在下降,因此,以好的截至点实现的第三种策略,可能是最好的策略。
 1//对探测散列表和分离链接散列表的再散列
 2void rehash()
 3{
 4    vector<HashEntry> oldArray = array;
 5    array.resize( nextPrime( 2* oldArray.size() ) );
 6    forint j = 0; j<array.size(); j++ )
 7        array[j].info = EMPTY;
 8    currentSize = 0;
 9    forint i = 0; i<oldArray.size(); i++ )
10        if( oldArray[i].info == ACTIVE )
11            insert( oldArray[i].element );
12}

13
14void rehash()
15{
16    vector<list<HashedObj> > oldLists = theLists;
17    theLists.resize( nextPrime( 2* theLists.size() ) );
18    forint j = 0; j<theLists.size(); j++ )
19        theLists[j].clear();
20    currentSize = 0;
21    forint i = 0; i<oldLists.size(); i++ )
22    {
23        list<HashedObj>::iterator itr = OldLists[i].begin();
24        while ( itr != oldLists[i].end() )
25            insert( *itr++ );
26    }

27}


2.标准库中的散列表
    标准库中不包括set和map的散列表实现。但是,许多的编译器提供具有与set和map类相同的成员函数的hash_set和hash_map.
    要使用hash_set和hash_map,就必须有相应的包含指令,而且,可能也需要相应的命名空间。这两者都是和编译器相关的。接下来还必须提供相应的类型参数来说明
hash_set和hash_map。对于hash_map,这些类型参数包括键的类型,值的类型,散列函数(返回无符号整数)和一个相等性操作符。遗憾的是,至于键和值的类型参数如何
表示还是编译器相关的。
    下一次c++的较大的修订将不可避免地包括这些hash_set和hash_map中的一个。

3.可扩散列
    最后讨论数据量太大以至于装不进主存的情况,此时主要考虑的是检索数据所需的磁盘存取次数。假设在任意时刻都有N个记录要存储,N的值随时间而变化。此外,最多可把M个记录放入一个磁盘区块,设M=4,如果使用探测散列或分离链接散列,那么主要的问题在于,即使是理想分布的散列表,在一次查找操作中,冲突也可能引起对多个区块的访问。不仅如此,当表变得过慢的时候,必须执行代价巨大的再散列这一步,它需要O(N)的磁盘访问。
    一种聪明的选择成为可扩散列(extendible hashing),它允许用两次磁盘访问执行一次查找。插入操作也需要很少的磁盘访问.
   Extendible hashing from Wikipedia
   Extendible hashing
is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

   

This is a more simplistic example from Fagin et al. (1979).

Assume that the hash function h(k) returns a binary number. The first i bits of each string will be used as indices to figure out where they will go in the "directory" (hash table). Additionally, i is the smallest number such that the first i bits of all keys are different.

Keys to be used:

h(k1) = 100100
h(k2) = 010110
h(k3) = 110110

Let's assume that for this particular example, the bucket size is 1. The first two keys to be inserted, k1 and k2, can be distinguished by the most significant bit, and would be inserted into the table as follows:

 directory
---------
|    0    |-----------> Bucket A (contains k2)
|---------|
|    1    |-----------> Bucket B (contains k1)
---------

Now, if k3 were to be hashed to the table, it wouldn't be enough to distinguish all three keys by one bit (because k3 and k1 have 1 as their leftmost bit. Also, because the bucket size is one, the table would overflow. Because comparing the first two most significant bits would give each key a unique location, the directory size is doubled as follows:

  directory
----------
|    00    |-----\
|----------|      ----------> Bucket A (contains k2)
|    01    |-----/
|----------|
|    10    |-----------> Bucket B (contains k1)
|----------|
|    11    |-----------> Bucket C (contains k3)
----------

And so now k1 and k3 have a unique location, being distinguished by the first two leftmost bits. Because k2 is in the top half of the table, both 00 and 01 point to it because there is no other key to compare to that begins with a 0.

4.小结
    散列表可以用来以常数平均时间实现insert和contains操作。当使用散列表时,注意诸如装填因子这样的细节是特别重要的,否则时间界将不再有效。当键不是短字符串或整数时,仔细选择散列函数也是很重要的。
    对于分离链接散列法,虽然装弹因子不大时性能并不明显降低,但装填因子还是应该接近于1,对于探测散列,除非完全不可避免,否则装填因子不应该超过0.5,如果使用线性探测,那么性能随着装填因子接近于1而急速下降。再散列运算可以通过使表增长(或收缩)来实现,这样可以保持合理的装填因子。对于空间紧缺并且不可能声明巨大散列表的情况,这是很重要的。
    二叉查找树也可以用来实现insert和contains操作。虽然平均时间界为O(logN),但是二叉查找树也支持那些需要排序的例程,从而功能更强大,使用散列表不可能找出最小元素。除非准确知道一个字符串,否则散列表也不可能有效地查找它。二叉查找树可以迅速找到一定范围内的所有项,散列表却做不到。不仅如此,因为查找树不需要乘法和除法,O(logN)这个时间界也不必比O(1)大那么多。
    另一方面,散列的最坏情形一般来自于实现错误,而有序的输入却可能使二叉树运行得很差。平衡查找树实现的代价相当高。因此,如果不需要排序的信息或者不确定输入是否已经排序,那么就应该选择散列这种数据结构。
    散列的应用很广。编译器使用散列表跟踪源代码中声明的变量,这种数据结构叫做符号表(symbol table)。散列表时这种问题的理想选择。标识符一般都不长,因此散列函数能够迅速完成运算。此外,按字母顺序排序变量通常也是不必要的。
    散列表适用于任何其节点有实名而不是数字名的图论问题。这里,当输入被读入的时候,定点则按照它们出现的顺序从1开始指定为一些整数。再有,输入很可能有一组按字母顺序排列的项。例如,顶点可以是计算机。此时,如果一个特定的计算中心把它的计算机列表成ibm1,ibm2,ibm3...那么,若使用查找树则在效率方面很可能会有戏剧性的结果。
   散列表的第三种常见的用途实在为游戏编制的程序中。当程序搜索游戏的不同的运动路径时,它通过计算基于位置的散列函数而跟踪一些已知的位置(并把对于该位置的移动存储起来)。如果同样的位置再次出现,程序通常通过简单的移动变换来避免昂贵的重复计算。游戏程序的这种一般特点叫做置换表(transposition table).
   散列的另一个用途是在线拼写检查程序。如果拼写检查程序的主要功能是检查拼写错误(而非纠正错误),那么可以预先将整个词典进行散列,这样就可以在常数时间内检查单词拼写。散列表很适合这项工作,因为以字母顺序排列单词并不重要,而以它们在文件中出现的顺序显示错误拼写当然也是可以接受的。

posted on 2009-11-27 17:14 小罗罗 阅读(881) 评论(7)  编辑 收藏 引用

评论

# re: 散列3 2009-11-27 18:34 OwnWaterloo

研究opencv的内存管理? 如果是为了使用opencv,可以去研究。

如果是为了研究内存管理…… opencv的内存管理其实很磋……
当然,opencv可能只是为了开发一个足够库自身使用的内存管理与动态数据结构而已。就这个需求来说,opencv是达到了。


但"足够库自身使用"不一定就能满足用户的所有需求。
而opencv也不提供任何方法让用户扩展它的库。
从这方面来说,opencv是相当的鼠目寸光。


比如opencv提供的CvCapture。其内部是有一个C实现的capture接口与capture工厂。
可是它不将接口定义暴露给用户。
用户需要自己的capture时怎么办? 等着opencv去支持吗? 那是不可能的。只能自己动手。
这个需求还好, 大不了让自己的capture返回image(image or matrix),然后丢给opencv去处理就可以了。
image的格式opencv还算厚道,暴露出来了。
用户如果想要实现得好一些,更capture无关,就需要自己再抽象一个capture接口,然后将opencv的capture包含进去 —— 基本就是将CvCapture的代码再实现一遍 —— 因为那短视的opencv没将这个可扩展点暴露出来。



如果用户不满意CvMemStorage和CvSeq的行为,哼哼……
必须屈服,除非用户想自己重写opencv —— 换句话说,就是放弃opencv。

CvMemStorage实现的是一个"多次取、整体放"的策略。
所有的动态数据结构都将数据存放在CvMemStorage分配的内存上。
没有单独释放数据结构中某个元素的方式,只能释放整个Storage。
可是opencv没有定义出一个接口,作为CvMemStorage和CvSeq之间的中间层,而是CvSeq直接使用CvMemStorage。

CvMemStorage本身也不咋嘀。甚至还有一个单次分配大小的上限……

一句话,opencv需要输出动态数据结构的算法和CvSeq绑死了,CvSeq又和CvMemStorage绑死了,而CvMemStorage又实现得不咋嘀……
你要使用opencv吗?请忍受CvMemStorage……
相比CvCapture可以绕过去;这个问题几乎无解。

  回复  更多评论   

# re: 散列3 2009-11-27 20:41 小罗罗

@OwnWaterloo
谢谢您指点,因为我以前只是用过opencv里的函数,从没有关心它的实现,我的打算是通过学习它的内存机制来加深对它内部结构的了解,并且我现在还在用一个叫mil的库,它不是开源的,相比较而言,我就选择opencv来学习,不管怎样,我觉得opencv还是值得我现在的水平拿来学习的,只有真正学过了,才有资格评论,是吧?  回复  更多评论   

# re: 散列3 2009-11-27 20:56 OwnWaterloo

@小罗罗
只看源码很枯燥,而且有些细节很难理解。
看这本书吧:《C语言接口与实现:创建可重用软件的技术》
http://www.china-pub.com/14974

里面的arena,思想和CvMemStorage是一样的"零取整放"。
CvMemStorage比arena多一些功能。

书里将arena的同时,会把内存分配器的一些细节说清楚,这些可能是看源代码多遍都看不出来的。
反正arena章节也不多……

  回复  更多评论   

# re: 散列3 2009-11-27 23:44 小罗罗

看了简介,很不错的样子,好的,听你的,豁出去了,买了  回复  更多评论   

# re: 散列3 2009-11-27 23:50 OwnWaterloo

@小罗罗
这…… 那链接上不是说已经绝版了吗?
  回复  更多评论   

# re: 散列3 2009-11-27 23:52 OwnWaterloo

http://download.csdn.net/source/747860

扫描版的,凑合着看吧……
源代码在这里:
http://code.google.com/p/cii/downloads/list

  回复  更多评论   

# re: 散列3 2009-11-28 00:00 小罗罗

OwnWaterloo ,我下载下来了,现在开始看。


  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜