`
evasiu
  • 浏览: 169489 次
  • 性别: Icon_minigender_2
  • 来自: 广州
博客专栏
Fa47b089-e026-399c-b770-017349f619d5
TCP/IP详解卷一>阅读...
浏览量:12549
社区版块
存档分类
最新评论

编程珠玑 -- bitSort

阅读更多

<C专家编程>看完了。受益最大的应该就是对声明部分的理解吧,特别是函数指针什么的。通过函数指针,可以实现一个自动机。我是这么想的。另外就是因此而学会了使用vi进行编程。接下来想学写makefile文件,不然文件一多调试修改后又要重新编译好几个文件。

 

回到编程珠玑上。第一篇描述了这样一个问题:在一定的内存限定下(内存大概有1MB)对一个包含有K个小于n (n=10^7)的数据的文件进行排序,可以保证,这K个数据没有一个是重复的(其实就是电话号码)。

 

qsort只能对内存中的数据进行排序,也就是说,要对文件遍历40次,每次读取一定范围的数到内存中,然后进行排序。(如,第一次,读取0~249,999范围内的数据到内存,qsort后输出到新的文件,然后再从文件中读取250,000~499,999的数据。。)这样的话,必须对文件遍历40次。

 

mergeSort只读取一次源文件,但是要开辟很多个临时文件进行辅助排序。

 

有什么办法可以只读一次源文件,写一次output,又不需要临时文件的辅助呢?

 

这个问题有三个特征是一般排序问题不具备的:

1。 数据范围比较小(<10^7)

2。 没有重复数据

3。 每个数据都很独立,没有其他相联的数据。

 

由于数据没有重复,同时所有数据都小于10^7,我们可以用每个bit来代表一个数据是否存在源文件中(由这些bit组成的表大概需要1.25MB),一边读取文件的时候一边设置相应的位,最后输出的时候检查相应的位是否为1,为1则输出该数字。如果内存严格要求1MB的话,可以分成两次读取。

 

我在实现的时候,写了三个函数,一个用于产生K个不重复的随机数,一个用于设置相应位,一个用于打印由map得到的排序后的结果。总之写了挺长的代码。。大概有100行了,后来看了后面的solution,不禁汗颜,,果然字字珠玑啊,10几行代码就把整个精华都写出来了,贴在这里给大家看看吧:

 

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1+N/BITSPERWORD];

void set( int i ){ a[i>>SHIFT] |= (1<<(i&MASK)); }

void clear( int i ){ a[i>>SHIFT] &= ~(1<<(i&MASK)); }

int test( int i ){ return (a[i>>SHIFT] & (1<<(i&MASK))); }

main(){
	int i=0;
	int j=0;
	for( i=0; i<N; i++ )
		clear(i);
	FILE* fp = fopen( "sortData", "r" );
	if( fp != NULL ){
		while( fscanf( fp, "%d", &i ) != EOF )
			set(i);
		for( i=N-1; i>=0; i-- ){
			if( test(i) ){
				j++;
				printf( "%d: %d\n", j, i );
			}
		}
	}
}

 

再看看我自己写的三个函数:

setMapAtK跟他的set基本是一样的,可是与起来远不如人家紧凑:

//这里考虑到我同时还要利用这个函数来产生不重复的随机数,所以选择了使用返回值
int setMapAtK( int gen, int* map ){
	int num = gen >> 5;
	int bit = gen & 31;
	if( map[num] & (1 << (bit)))
		return 1;
	map[num] = map[num]|(1 << (bit));
	return 0;
}

 printMap就很悲惨了,不过可取的一点是,我是对每个整数进行的操作,当取完最后一个为1的位后该整数就为0,也就是说,没有必要再对这个整数后面的位了。对于稀松集,这样效率是会提高一点的。

void printMap( int* map ){
	int r = 1;
	int i=MAXINT_TEMP-1;
	int size = MAXINT_TEMP>>5;
	int left = MAXINT_TEMP & 31;
	//这里主要考虑到最大整数可能并不是32的整数(虽然在我们的例子中n=10^7是)
	if( left > 0 ){
		int j = left-1;
		unsigned int num = (1<<j);
			int t = map[size];
			while(j>=0 && t ){
				if( map[size]& num ){
					t = (t & (num^(0xFFFF)));
					printf( "%d: %d\n", r++, i );
				}
				j--;
				i--;
				num = (num>>1);
			}
			i -= (j+1);
	}
	int k;
	//这里是主要循环
	for( k=size-1; k>=0; k-- ){
		int j=32;
		unsigned int num = 0x80000000;
			int t = map[k];
			while( j && t ){
				if( map[k] & num ){
					t = (t& (num^(0xFFFFFFFF)));
					printf( "%d: %d\n", r++,i );
				}
				j--;
				i--;
				num = (num>>1);
			}
			i -= j;
	}
}

 试验的结果我的时间是要比它少5、6秒(k=10^6),不过随着k逐渐增大,这样的优势自然就不存在了。

分享到:
评论

相关推荐

    ASP.NET\ASP.NET 2.0编程珠玑--来自MVP 2.0编程珠玑--来自MVP的权威开发指南

    《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》一书深入探讨了ASP.NET 2.0的核心概念和技术,旨在帮助开发者熟练掌握这一平台。 在ASP.NET 2.0中,控件是构建用户界面的关键组件。它们包括服务器控件和HTML控件,...

    编程珠玑-[美]乔恩美特利.mobi

    编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版

    编程珠玑-中文第二版

    ### 编程珠玑-中文第二版 #### 知识点概述 《编程珠玑-中文第二版》是一本在计算机科学领域内享有极高声誉的经典著作。本书虽然篇幅不长,但却以其深刻的见解和丰富的内涵深受广大程序员和技术爱好者的推崇。通过...

    asp.net 2.0编程珠玑--来自mvp的权威开发指南

    《ASP.NET 2.0编程珠玑--来自MVP的权威开发指南》是一本深入探讨ASP.NET 2.0技术的专业书籍,由该领域的专家,即微软最有价值专家(MVP)撰写。这本书旨在帮助开发者充分理解和掌握ASP.NET 2.0的核心概念,提升其在...

    ASP.NET 2.0编程珠玑--来自MVP的权威开发指南

    这本书“ASP.NET 2.0编程珠玑--来自MVP的权威开发指南”深入讲解了这个框架的关键特性和最佳实践,旨在帮助开发者充分利用其功能。 在ASP.NET 2.0中,最重要的改进之一是页面生命周期管理。与前一版本相比,2.0版...

    编程珠玑--算法

    编程中的一本关于算法的好书。

    编程珠玑-第2版-修订版

    《编程珠玑(第 2版·修订版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员...

    编程珠玑-英文版+中文版+source code

    《编程珠玑》一书,由Jon Bentley 编著,不仅是计算机科学领域的一本经典之作,更是一本深受初学者和有经验的开发者喜爱的宝典。该书以其深入浅出的方式探讨了程序设计中的核心问题,特别是如何有效地处理和存储大量...

    ASP.NET+2.0编程珠玑--开发指南

    本书“ASP.NET+2.0编程珠玑--开发指南”是针对这个版本的专业指南,由MVP(Microsoft最有价值专家)撰写,旨在帮助开发者深入理解和掌握ASP.NET 2.0的核心概念和技术。 书中可能涵盖了以下关键知识点: 1. **ASP...

    编程珠玑-第2版

    无书签,

    ASP.NET+2.0编程珠玑--来自MVP的权威开发指南(无密码)

    此压缩包文件提供的"ASP.NET+2.0编程珠玑--来自MVP的权威开发指南"是一本深入探讨ASP.NET 2.0技术的书籍,可能包含了以下关键知识点: 1. **ASP.NET 2.0概述**:ASP.NET 2.0在ASP.NET 1.x的基础上进行了许多改进,...

    编程珠玑-pdf

    编程珠玑,第二版,高清版,带目录,对学习编程有一些帮助

    编程珠玑 -- swap section

    NULL 博文链接:https://philoscience.iteye.com/blog/1010964

Global site tag (gtag.js) - Google Analytics