位图排序算法的一个实践
位图排序算法的一个实践
BlackJoker 发表于2年前
位图排序算法的一个实践
  • 发表于 2年前
  • 阅读 8
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

适应场景:
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();
			}
		}
	}


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


  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 1
博文 17
码字总数 9270
×
BlackJoker
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: