文档章节

位图排序算法的一个实践

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 721
阅读 9
收藏 0
点赞 0
评论 0
适应场景:
1,输入的数据限制在相对较小的范围内;2,数据没有重复;3,对于每条记录而言,除了单一整数外,没有任何其他相关联的数据。

2,要求
输入:一个最多包含n个正整数的文件F1,每个数小于n(n=1000000),而且整数没有重复;
输出:包含按升序排列的整数列表的文件F2;
约束:不超过1M的内存空间,运行时间10秒以内。

3,实现概要
可以用一个20位长度的0,1字符串来表示所有元素小于20的非负整数的集合。比如可以用下面的字符串来标示集合{1,2,3,5,8,13}:
S={0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 }
即S[1],S[2],S[3],S[5],S[8],S[13]都是1,其他的都是0.

利用上面的思想,可以用一个长度为n的字符串来表示文件F1里面的整数集合,然后遍历这个字符串,如果为1则输出下标的文件F2.
伪代码:
//初始化
for i=[0,n)
  bit[i]=0;
//扫描输入文件
for each i in F1
   bit[i]=1;
//输出
for each i=[0,n)
  if bit[i]==1
     write i to F2

我用java做了这个算法的实践,bit 数组采用的是JDK里面的BitSet,代码如下:
public static void main(String[] args) throws IOException {
		int n = 10000000;
		int k = 1000000;
		String srcFile = "/tmp/in.dat";
		String destFile = "/tmp/out.dat";
		long start = System.currentTimeMillis();
		genRandomNumbers2File(srcFile, n, k);
		sortAndSave2File(srcFile, destFile, n);
		long end = System.currentTimeMillis();
		System.out.println("Done in " + (end - start) + " ms");
	}

	/**
	 * 在文件fileName中生成一个所有元素互异且位于[0,n)之间的随机排列的整数序列,序列长度为k
	 * 
	 * @param fileName
	 * @param n
	 * @param k
	 * @throws IOException
	 */
	public static void genRandomNumbers2File(String fileName, int n, int k)
			throws IOException {
		File f = new File(fileName);
		if (!f.exists()) {
			f.createNewFile();
		}
		BufferedOutputStream bos = null;
		try {
			bos = new BufferedOutputStream(new FileOutputStream(f));
			int[] array = new int[n];// 定义初始数组
			for (int i = 0; i < n; i++)
				array[i] = i;
			Random random = new Random();
			for (int j = 0; j < k; j++) {
				int index = j + random.nextInt(n - j);// 生成一个[j,n)之间的随机数,作为数组下标
				// 交换array[j]和array[index],那么array[0..j]为已经获取到的随机数
				int temp = array[index];
				array[index] = array[j];
				array[j] = temp;
				// 把此次获取到的随机数存到rets里面
				bos.write(temp);
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (bos != null) {
				bos.close();
			}
		}
	}
	//从文件srcFile读取整数序列然后排序,并写到的destFile中
	public static void sortAndSave2File(String srcFile, String destFile, int n)
			throws IOException {
		File fsrc = new File(srcFile);
		File fdest = new File(destFile);
		if (!fdest.exists()) {
			fdest.createNewFile();
		}
		BufferedInputStream bis = null;
		BufferedOutputStream bos = null;
		try {
			bis = new BufferedInputStream(new FileInputStream(fsrc));
			BitSet bs = new BitSet(n);
			int read = 0;
			while ((read = bis.read()) != -1) {
				bs.set(read);
			}
			//
			bos = new BufferedOutputStream(new FileOutputStream(fdest));
			for (int i = 0; i < n; i++) {
				if (bs.get(i)) {
					// System.out.println(i);
					bos.write(i);
				}
			}

		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (bos != null) {
				bos.close();
			}
			if (bis != null) {
				bis.close();
			}
		}
	}


此博客的算法思想来源于《编程珠玑(第二版)》第一章


© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
编程珠玑--位图法排序

位图法是《编程珠玑》第一章中出现的磁盘排序算法。 题目:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7,且所有正整数都不重复。求如何将这n个正整数升序排列。 约束:最多有1MB...

王二狗子11
01/08
0
0
见山是山,见山不是山,见山只是山

“老僧三十年前未参禅时,见山是山,见水是水。及至后来,亲见知识,有个入处。见山不是山,见水不是水。而今得个休歇处,依前见山只是山,见水只是水。大众,这三般见解,是同是别?有人缁素...

mikelij
2008/10/28
0
0
Rxjs实践-各种排序算法排序过程的可视化展示

这几天学习下《算法》的排序章节,具体见对排序的总结,想着做点东西,能将各种排序算法的排序过程使用Rxjs通过可视化的方式展示出来,正好练系一下Rxjs的使用 本文不会太多介绍Rxjs的基本概念...

xiyuyizhi
2017/10/27
0
0
快排以及基于快排思想的topk 一锅端demo

算法不好,补补基本的排序算法,弄懂了快排,发现topK问题中也能用快排的思想所以写了一个demo 填坑解释法解释快排很形象,我是看这篇看懂快排的,这里推荐一下 http://blog.csdn.net/chengqi...

霁雪清虹
2017/11/10
0
0
《编程珠玑,字字珠玑》1234读书笔记——多路归并排序

写在前面的 2012年3月25日买下《编程珠玑》,很期待但不知道它能给我带来什么! 编程珠玑,字字珠玑。但是翻译有点拗口,有时候整句话读下来都不知道在讲什么,多少有点掩饰了珠玑的魅力,真...

xumaojun
04/09
0
0
请问有了解sample sort 和pthread的吗

最近想学学关于并行排序算法sample sort ,想利用pthread 来实践一下! 请各位前辈指教!

cwt1357
2012/11/07
55
0
算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于恨,是因为它在进行算法分析的时候所体现的数学思想...

chambai
2015/09/11
0
0
java代码排序实践

在java应用中,由于数据量少,所以排序算法很多时候我们都在用原始的方法:例如 double t;for (int i = 0; i < 2; i++)for (int j = i + 1; j < 3; j++)if (r[j] < r[i]) {t = r[i];r[i] = r......

hyssop
2015/11/30
34
0
OpenGL超级宝典笔记——位图

位图 最初的电子计算机,只能显示单色(绿色或琥珀色)图形,每一个像素只有两种状态打开和关闭。在计算器图形学前期,图像数据是用位图来表示的,位图就是一系列的0和1,表示打开或关闭的像...

Mario_Q
2013/10/28
0
2
bitmap图像介绍

典型的BMP图像文件由四部分组成:   1:位图文件头数据结构,它包含BMP图像文件的类型、显示内容等信息;   2:位图信息数据结构,它包含有BMP图像的宽、高、压缩方法,以及定义颜色等信...

技术小胖子
2017/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

shell及python脚本方式登录服务器

一、问题 在工作过程中,经常会遇见需要登录服务器,并且因为安全的原因,需要使用交互的方式登录,而且shell、python在工作中也经常用到,并且可以提供交互的功能。都是利用了expect、spawn...

yangjianzhou
11分钟前
0
0
upstream sent too big header while reading...

nginx 报错:1736 upstream sent too big header while reading response header from upstream 1. 一般处理 location ~ \.php$ { #增加下面两句 fastcgi_buffer_size 128k; ......

dubox
22分钟前
0
0
Python解析配置文件模块:ConfigPhaser

import configparser as pa# [SectionA]# a = aa# b = bb# c = cc# [SectionB]# optionint = 1# optionfloat = 1.1# optionstring = string#https://www.cnblogs.com/a......

易野
29分钟前
0
0
Java基础——面向对象

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 Object的方法: clone() Object 克隆 to Strin...

凯哥学堂
30分钟前
0
0
rabbitmq学习记录(八)消息发布确认机制

RabbitMQ服务器崩了导致的消息数据丢失,已经持久化的消息数据我们可以通过消息持久化来预防。但是,如果消息从生产者发送到vhosts过程中出现了问题,持久化消息数据的方案就无效了。 Rabbit...

人觉非常君
35分钟前
0
0
毕业5年,我是怎么成为年薪30W的运维工程师

#转载# 我在大学读的是计算机专业,但大学毕业之后,进入到一家私企进行工作,工作的内容类似于网管,会经常的去修电脑,去做水晶头等内容。刚开始工作,也没想太多,最想的是丰富自己的工作...

Py爱好
42分钟前
1
0
大数据基础知识,大数据学习,涉及的知识点

一、什么是大数据 一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合,具有海量的数据规模、快速的数据流 转、多样的数据类型和价值密度低四大特征。...

董黎明
57分钟前
0
0
Linux CentOS 7上安装极点五笔

话说几天前在新买的惠普笔记本上成功地安装了Linux CentOS 7操作系统、Nvidia Quandro P600驱动程序及X Window,并在VMware下安装Red Hat教学环境,彻底跳出Windows的苦海,但仍然有一件事不...

大别阿郎
今天
17
0
2018年7月20日集群课程

一、集群介绍 集群,简单地说是指一组(若干个)相互独立的计算机,利用高速通信网络组成一个较大的计算机服务系统,每个集群节点(即集群中的每台计算机)都是运行各自服务的独立服务器。 ...

人在艹木中
今天
0
0
spark开发机中调试snappy

目的 在Idea中的点击运行,使spark可以直接读取snappy 自己编译hadoop,以支持snappy的压缩。 自己编译的目的就是要得到支持snappy文件读写的动态链接库。如果可以在网上下载,可以跳过自行编...

benny周
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部