哈希表施用实例 - ext4 delalloc相干 - HTC one/M7电信802d 毒蛇ViperOne2.1.0/高级毒蛇工具/圆满root,精简/更多自定义,稳定,流畅ROM

当前位置: 编程技术>移动开发

本页文章导读:

▪哈希表施用实例哈希表应用实例struct数据结构算法 1：问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2：.........

▪ ext4 delalloc相干 ext4 delalloc相关ext4文件系统delayed allocation相关研究最近在一个项目上测试录音时，发现有丢数据的现象。通过串口发现打出了很多overrun的log。 overrun是驱动层给上层应用的一个通知，告诉上.........

▪ HTC one/M7电信802d 毒蛇ViperOne2.1.0/高级毒蛇工具/圆满root,精简/更多自定义,稳定,流畅ROM HTC one/M7电信802d 毒蛇ViperOne2.1.0/高级毒蛇工具/完美root,精简/更多自定义,稳定,流畅ROM ROM版本 HTC One/M7 802d ROM作者雪狼团队·大盛 http://weibo.com/DaShengdd Android版本 Android 4.2.2 创.........

[1]哈希表施用实例

来源: 互联网发布时间: 2014-02-18

哈希表应用实例

struct数据结构算法

1：问题描述

针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

2：基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。

3：数据结构设计

[cpp] view plaincopyprint?

#ifndef _HashTest_H_

#define _HashTest_H_

#define NAME_NO 30

#define HASH_LENGTH 50

#define M 50;

typedef struct

{

#ifndef _HashTest_H_
#define _HashTest_H_

#define NAME_NO 30
#define HASH_LENGTH 50
#define M 50;

typedef struct      
{

[cpp] view plaincopyprint?

char *py; //名字的拼音

	char *py;      //名字的拼音

[cpp] view plaincopyprint?

int k; //拼音所对应的整数

}NAME;

typedef struct //哈希表

{

char *py; //名字的拼音

int k; //拼音所对应的整数

	int k;         //拼音所对应的整数
}NAME;

typedef struct         //哈希表
{   
	char *py;     //名字的拼音
	int k;        //拼音所对应的整数

[cpp] view plaincopyprint?

int si; //查找长度

}HASH;

#endif

	int si;       //查找长度
}HASH;

#endif

4：主要算法设计

（1）姓名（结构体数组）初始化

名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。

[cpp] view plaincopyprint?

void InitNameList()

{

char *f;

int r,s0,i;

NameList[0].py="chenliang";//陈亮

NameList[1].py="chenyuanhao";//陈元浩

NameList[2].py="chengwenliang";//程文亮

NameList[3].py="dinglei";//丁磊

NameList[4].py="fenghanzao";//冯汉枣

NameList[5].py="fuzongkai";//付宗楷

NameList[6].py="hujingbin";//胡劲斌

NameList[7].py="huangjianwu";//黄建武

NameList[8].py="lailaifa";//赖来发

NameList[9].py="lijiahao";//李嘉豪

NameList[10].py="liangxiaocong";//梁晓聪

NameList[11].py="linchunhua";//林春华

NameList[12].py="liujianhui";//刘建辉

NameList[13].py="luzhijian";//卢志健

NameList[14].py="luonan";//罗楠

NameList[15].py="quegaoxiang";//阙高翔

NameList[16].py="sugan";//苏淦

NameList[17].py="suzhiqiang";//苏志强

NameList[18].py="taojiayang";//陶嘉阳

NameList[19].py="wujiawen";//吴嘉文

NameList[20].py="xiaozhuomin";//肖卓明

NameList[21].py="xujinfeng"; //许金峰

NameList[22].py="yanghaichun";//杨海春

NameList[23].py="yeweixiong";//叶维雄

NameList[24].py="zengwei";//曾玮

NameList[25].py="zhengyongbin";//郑雍斌

NameList[26].py="zhongminghua";//钟明华

NameList[27].py="chenliyan";//陈利燕

NameList[28].py="liuxiaohui";//刘晓慧

NameList[29].py="panjinmei";//潘金梅

for(i=0;i<NAME_NO;i++)

{

s0=0;

f=NameList[i].py;

for(r=0;*(f+r)!='\0';r++)/*将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字*/

s0=*(f+r)+s0;

NameList[i].k=s0;

}

void InitNameList()          
{   
    char *f;
    int r,s0,i;
    NameList[0].py="chenliang";//陈亮
    NameList[1].py="chenyuanhao";//陈元浩
    NameList[2].py="chengwenliang";//程文亮
    NameList[3].py="dinglei";//丁磊
    NameList[4].py="fenghanzao";//冯汉枣
    NameList[5].py="fuzongkai";//付宗楷
    NameList[6].py="hujingbin";//胡劲斌
    NameList[7].py="huangjianwu";//黄建武
    NameList[8].py="lailaifa";//赖来发
    NameList[9].py="lijiahao";//李嘉豪
    NameList[10].py="liangxiaocong";//梁晓聪
    NameList[11].py="linchunhua";//林春华
    NameList[12].py="liujianhui";//刘建辉
    NameList[13].py="luzhijian";//卢志健
    NameList[14].py="luonan";//罗楠
    NameList[15].py="quegaoxiang";//阙高翔
    NameList[16].py="sugan";//苏淦
    NameList[17].py="suzhiqiang";//苏志强
    NameList[18].py="taojiayang";//陶嘉阳
    NameList[19].py="wujiawen";//吴嘉文
    NameList[20].py="xiaozhuomin";//肖卓明
    NameList[21].py="xujinfeng"; //许金峰
    NameList[22].py="yanghaichun";//杨海春
    NameList[23].py="yeweixiong";//叶维雄
    NameList[24].py="zengwei";//曾玮
    NameList[25].py="zhengyongbin";//郑雍斌
    NameList[26].py="zhongminghua";//钟明华
    NameList[27].py="chenliyan";//陈利燕
    NameList[28].py="liuxiaohui";//刘晓慧
    NameList[29].py="panjinmei";//潘金梅
    for(i=0;i<NAME_NO;i++)
	{   
		s0=0;
        f=NameList[i].py;
        for(r=0;*(f+r)!='\0';r++)/*将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字*/
			s0=*(f+r)+s0;
        NameList[i].k=s0;
	} 
}

(2) 建立哈希表

用除留余数法构建哈希函数，用伪随机探测再散列法处理冲突

[cpp] view plaincopyprint?

void CreateHashList()

{

int i;

for(i=0; i<HASH_LENGTH;i++)

{

HashList[i].py="";

HashList[i].k=0;

HashList[i].si=0;

}

for(i=0;i<HASH_LENGTH;i++)

{

int sum=0;

int adr=(NameList[i].k)%M;//哈希函数

int d=adr;

if(HashList[adr].si==0)//如果不冲突

{

HashList[adr].k=NameList[i].k;

HashList[adr].py=NameList[i].py;

HashList[adr].si=1;

}

else//冲突

{

d=(d+NameList[i].k%10+1)%M;//伪随机探测再散列法处理冲突

sum=sum+1; //查找次数加1

}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;

HashList[d].py=NameList[i].py;

HashList[d].si=sum+1;

}

void CreateHashList() 
{	
	int i;
    for(i=0; i<HASH_LENGTH;i++) 
	{  
		HashList[i].py="";
		HashList[i].k=0;
		HashList[i].si=0;
	}
    for(i=0;i<HASH_LENGTH;i++)
	{   
		int sum=0;
        int adr=(NameList[i].k)%M;//哈希函数
        int d=adr;
        if(HashList[adr].si==0)//如果不冲突
		{  
			HashList[adr].k=NameList[i].k;
			HashList[adr].py=NameList[i].py;
			HashList[adr].si=1;
		}
		else//冲突  
		{ 
			do
			{   
				d=(d+NameList[i].k%10+1)%M;//伪随机探测再散列法处理冲突    
				sum=sum+1;                 //查找次数加1    
			}while (HashList[d].k!=0);
			HashList[d].k=NameList[i].k;
			HashList[d].py=NameList[i].py;
			HashList[d].si=sum+1;
		}
	}
}

(3) 查找哈希表

在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度

[cpp] view plaincopyprint?

void FindList() //查找

{

char name[20]={0};

int s0=0,r,sum=1,adr,d;

printf("请输入姓名的拼音:");

scanf("%s",name);

for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)

s0+=name[r];

adr=s0%M; //使用哈希函数

d=adr;

if(HashList[adr].k==s0) //分3种情况进行判断

printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);

else if (HashList[adr].k==0)

printf("无此记录!");

else

{

int g=0;

{

d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突

sum=sum+1;

if(HashList[d].k==0)

{

printf("无此记录! ");

g=1;

}

if(HashList[d].k==s0)

{

printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);

g=1;

}

}while(g==0);

}

void  FindList() //查找    
{	
	char name[20]={0}; 
	int s0=0,r,sum=1,adr,d;
    printf("请输入姓名的拼音:");     
    scanf("%s",name); 
    for(r=0;r<20;r++)   //求出姓名的拼音所对应的整数(关键字)
        s0+=name[r]; 
    adr=s0%M;   //使用哈希函数
    d=adr;
    if(HashList[adr].k==s0)          //分3种情况进行判断
		printf("\n姓名:%s   关键字:%d   查找长度为: 1",HashList[d].py,s0); 
    else if (HashList[adr].k==0) 
		printf("无此记录!");
    else
	{   
		int g=0;
		do
		{   
			d=(d+s0%10+1)%M;       //伪随机探测再散列法处理冲突                     
			sum=sum+1;
			if(HashList[d].k==0)
			{  
				printf("无此记录! ");  
				g=1;     
			}
			if(HashList[d].k==s0)
			{  
				printf("\n姓名:%s   关键字:%d   查找长度为:%d",HashList[d].py,s0,sum); 
				g=1;  
			}
		}while(g==0);   
	}  
}

(4) 显示哈希表

[cpp] view plaincopyprint?

void Display()

{

int i;

float average=0;

printf("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式

for(i=0; i<50; i++)

{

printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",HashList[i].k%30);

printf("\t %s ",HashList[i].py);

printf("\n");

}

for(i=0;i<HASH_LENGTH;i++)

average+=HashList[i].si;

average/=NAME_NO;

pri

void Display()       
{	
	int i;
	float average=0;
	printf("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式
	for(i=0; i<50; i++)
	{   
		printf("%d ",i); 
		printf("\t%d ",HashList[i].k);
		printf("\t\t%d ",HashList[i].si);
		printf("\t\t%d ",HashList[i].k%30);
		printf("\t %s ",HashList[i].py);		
		printf("\n");
	}
	for(i=0;i<HASH_LENGTH;i++)
		average+=HashList[i].si; 
	average/=NAME_NO;
	pri

(5) 主函数

[cpp] view plaincopyprint?

void main()

{

char ch1;

InitNameList();

CreateHashList ();

{

printf("D. 显示哈希表\nF. 查找\nQ. 退出\n请选择： ");

cin>>&ch1;

switch(ch1)

{

case 'D':Display(); cout<<endl;break;

case 'F':FindList();cout<<endl;break;

case 'Q':exit(0);

}

cout<<"come on !(y/n):";

cin>>&ch1;

}while(ch1!='n');

}

void main()
{	
	char ch1;
	InitNameList();                                
	CreateHashList (); 
	do	
	{	
		printf("D. 显示哈希表\nF. 查找\nQ. 退出\n请选择： ");
		cin>>&ch1;
		switch(ch1)
		{
			case 'D':Display(); cout<<endl;break;
			case 'F':FindList();cout<<endl;break;
			case 'Q':exit(0);
		}
		cout<<"come on !(y/n):";
		cin>>&ch1;
	}while(ch1!='n'); 
}

[2] ext4 delalloc相干

来源: 互联网发布时间: 2014-02-18

ext4 delalloc相关

ext4文件系统delayed allocation相关研究

最近在一个项目上测试录音时，发现有丢数据的现象。通过串口发现打出了很多overrun的log。
overrun是驱动层给上层应用的一个通知，告诉上层数据取的太慢了，buffer被塞满了。
如果buffer塞满之后，上层仍不能及时取走数据，自然会导致数据丢失。

上层应用取数据过慢，能想到的有两个原因：
1、cpu繁忙，录音进程不能及时抢占到cpu。
2、录音进程写文件时速度过慢。

通过top命令，发现cpu并不繁忙，排除了第一种可能。

分析第二种可能。如果是写文件过慢，换一种介质是不是会有所不同。
最初是将录音文件写到nand flash上，有overrun错误和丢数据现象。
将录音文件保存到sd卡上，发现overrun错误没了，丢数据现象也没了。
基本上可以肯定是写文件过慢导致的了。

既然是文件写入过慢导致，那就比较比较nand flash与sd卡文件写入速度的差别。
使用命令：
sync; date; dd if=/dev/zero of=/data/xxx bs=4096 count=40960; sync; data
sync; date; dd if=/dev/zero of=/sdcard/xxx bs=4096 count=40960; sync; data
data是nand flash上一个分区。
测试发现，写入160M数据，nand flash耗时35s-45s不等，而sd卡耗时在20s左右。
会不会是其他进程也在访问nand flash导致？
打开blok_dump开关：echo 1 > /proc/sys/vm/block_dump，
通过命令while true; do dmesg -c; sleep 1; done发现有几个进程会经常访问nand flash。
将那几个进程干掉。
重新测试，发现nand flash速度依然如故。
有点费解，难道是什么地方设置或者其他进程影响？
为了尽可能减少其他进程影响，进入到recovery模式进行测试。
recovery模式下没有mount nand flash分区，手动mount:
mount -t ext4 /dev/block/mmcblk0px /data
然后进程测试。
sd卡的速度与正常模式下基本相同，nand flash速度大幅提升30%左右。
那就看看recovery模式下与正常模式下nand flash有什么差别。
recovery模式下，nand flash分区是通过命令：
mount -t ext4 /dev/block/mmcblk0p8 /data
挂载的。
正常模式下，是通过init.rc中的命令挂载的。
比较两处命令的差别，发现init.rc中的mount命令多了几个参数。
通过排除发现是参数nodelalloc的影响。
在recovery模式下，如果mount时加上nodelalloc，速度基本上与正常模式下相同。
正常模式下，去掉nodelalloc，速度也上去了。

delalloc是何方神圣？
原来是ext4引入的新技术。
以下是kernel中ext4文档中的介绍：
delalloc        (*)     Defer block allocation until just before ext4
                         writes out the block(s) in question. This
                         allows ext4 to better allocation decisions
                         more efficiently.

nodelalloc              Disable delayed allocation. Blocks are allocated
                         when the data is copied from userspace to the
                         page cache, either via the write(2) system call
                         or when an mmap'ed page which was previously
                         unallocated is written for the first time.
通过上面的介绍，基本上知道delalloc是什么。
但为什么会有delalloc的诞生，还需要继续研究。

通过ext4 wiki (参考[1])，找到关于ext4相关介绍(参考[2])。
其中对delay allocation的说明如下：
2.6. Delayed allocation
Delayed allocation is a performance feature (it doesn't change the disk format) found in a few modern filesystems such as XFS, ZFS, btrfs or Reiser 4, and it consists in delaying the allocation of blocks as much as possible, contrary to what traditionally filesystems (such as Ext3, reiser3, etc) do: allocate the blocks as soon as possible. For example, if a process write()s, the filesystem code will allocate immediately the blocks where the data will be placed - even if the data is not being written right now to the disk and it's going to be kept in the cache for some time. This approach has disadvantages. For example when a process is writing continually to a file that grows, successive write()s allocate blocks for the data, but they don't know if the file will keep growing. Delayed allocation, on the other hand, does not allocate the blocks immediately when the process write()s, rather, it delays the allocation of the blocks while the file is kept in cache, until it is really going to be written to the disk. This gives the block allocator the opportunity to optimize the allocation in situations where the old system couldn't. Delayed allocation plays very nicely with the two previous features mentioned, extents and multiblock allocation, because in many workloads when the file is written finally to the disk it will be allocated in extents whose block allocation is done with the mballoc allocator. The performance is much better, and the fragmentation is much improved in some workloads.

通过上述说明可知，将Delayed allocation与Extents、Multiblock allocation结合，可以大幅提升alloc的性能，并能改善碎片的问题。

接下来就该看看delayed allocation是怎样工作的。
同样在ext4 wiki (参考[1])中有个连接: Life of an ext4 write request(参考[3])。
其中对delayed allocation情况下的write请求进行了分析。
其中有一点要特别说明下，如果disk上的空间过少时，应该关闭delayed allocation功能。
因为delayed allocation的情况下，block是在真正写数据的时候才申请，而不是在上层应用调用write请求时。
如果在申请block时发现空间不足，导致写入失败，此时上层的write请求已经返回，所以没办法将错误通知给上层，最终导致上层应用认为写成功了，而实际没写入到介质中。
详细见下面说明：
In ext4_da_write_begin(), there's a potential fallback to nodelalloc mode. That happens if we are low on space (and possibly low on quota; but not sure). That's because when we estimate how much space is needed, we can guess wrong, especially as it comes to metadata allocation. We tend to guess high, because in particular for ENOSPC, we don't want to run out of space when we need to allocate an extent tree block. That's because in the delalloc write request, we don't actually do the block allocation until the writeback time --- and at that point we can't return an error to userspace. If we fail to allocate space at writeback time, data can potentially be lost without the calling application knowing about it. This is not the case for direct I/O, of course, since it doesn't use the writeback; but delalloc is all about what happens for buffered writes.) So when we come close to running out of disk space, we will turn off delayed allocation.

delayed allocation还有一个弊端，就是可能导致某一次的写入延迟特别长(参考[4])。
原因是，既然allocation都被delay了，肯定在writeback的时候要多花费时间。
writeback时会申请一把锁，上层应用write请求时也会申请这把锁。
如果上层应用write请求时刚好遇到writeback占用了锁，并进行了很长时间的操作，这个时候，上层应用的write请求只能等着了。

[1] https://ext4.wiki.kernel.org/index.php/Main_Page
[2] http://kernelnewbies.org/Ext4
[3] https://ext4.wiki.kernel.org/index.php/Life_of_an_ext4_write_request
[4] http://blog.tao.ma/?p=58

[3] HTC one/M7电信802d 毒蛇ViperOne2.1.0/高级毒蛇工具/圆满root,精简/更多自定义,稳定,流畅ROM

来源: 互联网发布时间: 2014-02-18

HTC one/M7电信802d 毒蛇ViperOne2.1.0/高级毒蛇工具/完美root,精简/更多自定义,稳定,流畅ROM

ROM版本

HTC One/M7 802d

ROM作者

雪狼团队·大盛
http://weibo.com/DaShengdd

Android版本

Android 4.2.2

创建日期

2013.09.05

ROM大小

850M

MD5验证码

3359CB4E8D456C685705A7112635D0DC

适用机型

HTC One（802d）国行电信版

QQ群

QQ： 177061373

            ROM简介：

      声明：该版本只针对HTC one国行电信版本，其他版本请勿刷！
从上次发布的国际版的毒蛇相关ROM：http://www.wanjiquan.com/thread-1469989-1-1.html的反应和反馈情况来看，大家多毒蛇工具绝大部分的很赞同的，不过也有网友反应毒蛇工具功能太多，有些根本用不到，也许这样才可以满足更多用户的需要，这也就是所谓的：不让网友来适应ROM，而是更多的让ROM功能适应用户。
再次重申：该版本是针对国行电信版本的HTC one其他版本请勿刷！该ROM不是完全汉化版本的ViperOne2.1.0ROM，但是功能完全不少，是考虑既要保证原工具的原滋原味，又要符合的用户习惯。更多的功能在这里不再赘述，更多的体验还得自己来体验，再次声明该版本ROM不是纯粹的汉化国外毒蛇团队的ROM。
  鸣谢：大款小总、玩机圈iKira、WinerisMY的汉化支持与参考。

         功能介绍：

※ 针对国行电信HTC One
※ 最新ViperOne2.1.0毒蛇工具
※ 新版本的毒蛇侧边栏工具以及毒蛇市场
※ 加入更多电池资源选项
※ 个性的MIUI电量条以及色彩调整
※ 添加最新来去电归属地数据库文件
※ 采用最新版本国行内核
※ 全新图标样式的快捷按钮systemUI
※ 修复桌面天气更新延迟的问题
※ 进一步优化系统UI更加稳定快捷
※ 加固侧向桌面工具的稳定流畅
※ 支持天气显示开关
※ 默认加载全部快捷开关
※ 支持快捷开关的增删
※ 更多实体键短按和长按菜单
※ 添加HTC 小Hi助手
※ 添加高级设置菜单
※ 加入最新国内新闻源
※ 更新微博至最新版本
※ 加入通话录音
※ 添加最新短信亮屏开关
※ 去除还带条的显示开关
※ 添加状态栏的电池、时钟、图标自定义设置
※ 添加系统桌面4x2模式的时钟插件、天气插件
※ 添加音量上下键唤醒屏幕开关
※ 添加无线扫描间隔选项
※ 电源键选项开关
※ 自定义通知栏快捷开关的选项
※ 修复偶尔不能更新国内新闻源的问题
※ 更新相关应用到目前最新的版本

更新内容：
更多更新内容如上所述，这里不再赘述...

                     同时期待您的反馈和建议...

截图展示：

了解更多：点击打开链接