一些鲜为人知却非常实用的数据结构

-
 
 

Oen 通过 Google 阅读器发送给您的内容：

 
 

于 13-5-27 通过 博客园_256code, 生活与技术 作者：Haippy

作为程序猿（媛），你必须熟知一些常见的数据结构，比如栈、队列、字符串、链表、二叉树、哈希，但是除了这些常见的数据结构以外，还有没有其他不是很有名，但却非常实用的数据结构呢，有人在 stackoverflow 上问了这样一个问题，得到了很多热心观众的回答，我们今天就来看看那些鲜为人知却非常实用的数据结构吧。

首先，维基百科上的一个页面列举了常见的数据结构，你可以先去那个页面看看。下面我们就来看看一些不是很常见的数据结构吧：

 

 

 

本文链接


 
 

可从此处完成的操作：

 
 

评论

发表评论

此博客中的热门博文

浅析Linux Kernel 哈希路由表实现(一)

-
    Han 通过 Google 阅读器发送给您的内容：     浅析Linux Kernel 哈希路由表实现(一) 于 11-3-13 通过 basic coder 作者：levin 1. 路由表 目前Linux内核中支持两种路由表，一种是Hash路由表，另一种是Trie路由表，Trie算法查找效率很高，但它也因极其消毫内存资源而闻名，因此一般用在大型机上，否则在路由项过多时很可能造成内存的耗尽。在一般的机器上最好还是使用Hash路由表，之前有争论说Linux使用Hash路由表相比于二叉树效率太低，不适合商用，其实只要设计良好的哈希算法，尽量减少哈希碰撞，Hash路由表的查找效率也是很高的，在最好的情况下算法复杂算可以达到O(1)，当然，最差也不过是O(n)，我们有理由相信Linux中存在各种优秀的哈希算法，这些都是值得我们学习的。 Linux内核中IPv4路由表采用了分层的结构，第一层是是fib_table，表示路由表，最多可以支持256张路由表，用户可以根据策略路由的需求来创建自己的路由表，系统默认的两张路由表为RT_TABLE_LOCAL和RT_TABLE_MAIN。下面是系统保留的路由表标识符： enum rt_class_t { RT_TABLE_UNSPEC = 0 , /* User defined values */ RT_TABLE_COMPAT = 252 , RT_TABLE_DEFAULT = 253 , RT_TABLE_MAIN = 254 , RT_TABLE_LOCAL = 255 , RT_TABLE_MAX = 0xFFFFFFFF } ; 下面是路由表的定义： struct fib_table { struct hlist_node tb_hlist ; /* 路由表的标识，即为上面提到的类型 */ u32 tb_id ; /* 该路由中默认路由条目在哈希路由表中的索...
阅读全文

通过blktrace, debugfs分析磁盘IO

-
    Han 通过 Google 阅读器发送给您的内容：     通过blktrace, debugfs分析磁盘IO 于 12-11-14 通过 Linux Kernel and Tao 作者：admin 前几天微博上有同学问我磁盘util达到了100%时程序性能下降的问题，由于信息实在有限，我也没有办法帮太大的忙，这篇blog只是想给他列一下在磁盘util很高的时候如何通过blktrace+debugfs找到发生IO的文件，然后再结合自己的应用程序，分析出这些IO到底是谁产生的，最终目的当然是尽量减少不必要的IO干扰，提高程序的性能。 blktrace是Jens Axobe写的一个跟踪IO请求的工具，Linux系统发起的IO请求都可以通过blktrace捕获并分析，关于这个工具的介绍请自行google之，这里推荐我们部门的褚霸同学的 blog ，里面有好几篇文章分别介绍了blktrace, blkparse以及blkiomon等工具的使用。 debugfs是ext2, ext3, ext4文件系统提供的文件系统访问工具，通过它我们可以不通过mount文件系统而直接访问文件系统的内容，它是e2fsprogs的一部分，默认应该都是安装的，详细的说明可以通过man debugfs得到。 下面我来演示一下如何通过这两个工具的配合来找到磁盘IO的源头。 先看一个简单的例子： 在一个终端会输入如下命令： while [ 1 ];do dd if=/dev/zero of=test_file bs=4k count=20 seek=$RANDOM oflag=sync;done 随机的在test_file里面写数据造成较大的IO压力，现在看看如何通过blktrace和debugfs抓到它。 1. 通过iostat观察到有很大的磁盘压力 Device: rrqm/s wrqm/s r/s w/s rsec/s wsec/s avgrq-sz avgqu-sz await svctm %util sdb ...
阅读全文

ext4 bigalloc 答疑

-
    Han 通过 Google 阅读器发送给您的内容：     ext4 bigalloc 答疑 于 13-2-20 通过 斯巴达第二季 问题都来自 pamirs 的信，感谢他对bigalloc特性的关注。 问：文件分配的时候，ext4文件系统请求的时候是按照blocks来请求,但是ext4文件系统自己会按照cluster来分配（这个的理解是否正确呢？） 答：应该说，不太准确，事实上, ext4文件系统请求分配磁盘空间的时候也是按照cluster来请求的了，ext4_ext_map_blocks() 函数是用来检查文件的逻辑位置对应的物理块的，里面申请新磁盘空间的调用是：         ar.len = EXT4_NUM_B2C(sbi, offset+allocated);         ......         newblock = ext4_mb_new_blocks(handle, &ar, &err); ar.len的单位是cluster，所以实际上申请空间就是以cluster为单位 问：如果cluster为32K(8个blocks), 那么对于一个3k的文件来说,一次就分配了一个cluster,这样就有7个blocks不能在被其他文件使用了。group desc中的block_bitmap中将cluster对应的bit位置1，那么后续这个文件在增加的时候,是否按照增加的blocks数量,以及当前该文件占用的cluster,计算出已经占用的cluster中有多少blocks是空闲的,还可以继续分配呢? 答：是的，需要一些琐碎的计算，这些计算的代码都放在了函数get_implied_cluster_alloc()里 问：ext4_group_desc中的bg_free_blocks_count_lo字段表示当前group中有多少空闲的blocks,使用了bigalloc之后,该字段的意义并没有发生变化吧?好像没有看到有新增一个字段来表示free_clusters数量,这个是否不需要保存这样的变量?通过bitmap查询得知呢? 答：bg_free_blocks_coun...
阅读全文